Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Swapping CodeChef Solution
Problem -Swapping CodeChef Solution
“This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Swapping CodeChef Solution in C++14
“/* u cant evr win if u alwys defend.To win ,u have to ATTACK !! */
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define count_1(n) __builtin_popcountll(n)
#define lsb(n) __builtin_ctzll(n)
#define pb push_back
#define fr(a,b) for(int i =a ;i <b ;i++)
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
#define pint pair<int,int>
typedef long long ll;
typedef long double ld;
const int N = 1e9 + 7 ;
#define inf (1LL<<62)
template <typename T>istream &operator>>(istream &istream, vector<T> &vec){for (auto &a : vec)cin >> a;return istream;}
template <typename T>ostream &operator<<(ostream &ostream, const vector<T> &vec){for (auto &a : vec)cout << a << " ";return ostream;}
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
#define int long long
vint dx = {0,+1,0,-1} ;
vint dy = {1,0,-1,0} ;
int root(int x) {
int y = sqrtl(x) + 2;
while(y * y > x) --y;
return y;
}
bool cOmP(pair<int,int> a , pair<int,int> b){
return (a.second < b.second) ;
}
int n ;
int ans;
int dp[200005] ;
vint v ;
int solve(int ind){
if(ind >= n)return 0 ;
if(dp[ind]!= -1)return dp[ind] ;
int hash = v[ind]*(ind+1)+ solve(ind+1) ;
int hash2 = LLONG_MIN ;
if(ind+1 < n)hash2= v[ind+1]*(ind+1) + v[ind]*(ind+2)+solve(ind+2) ;
return dp[ind] = max(hash,hash2) ;
}
signed main() {
FAST
ll t ;
t=1;
cin >>t ;
while(t--){
memset(dp,-1,sizeof(dp)) ;
cin >>n ;
v.resize(n) ;
cin >>v ;
cout << solve(0) <<endl;
}
return 0;
}
//T*ink 2*x c*de 1*x
// 48-57 -> 0-9
// 65-90 -> A-Z
// 97-122 -> a-z
//llround( double )
//fermats little theorme - fr vp(P (a^(p-1))%p =1
/*RRESIZE AND ASSIGN FOR ALL TC
Parent info ke lie its better to use dfs
Return in build base biro :)
10^9 is within integer limits
string c1(1,s1[0]) ;
cout<<setw(2)<<setfill('0')<<a;
*/
/*void dfs(int vertex){
TAKE ACTION ON VERTEX AFTR ENTERING THE VERTEX
for(auto child : adj[node]){
TAKE ACTION ON CHILD BEFORE ENTERING THE CHILD
dfs(child) ;
TAKE ACTION ON CHILD AFTER EXITING CHILD
}
TAKE ACTION ON VERTEX BEFORE EXITING VERTEX
}
*/
/* //DIJKSTRAS ;
vector<pair<int,int>> g[n+1] ;
vector<int> lev(n+1,INF) ;
for(int i=0;i<m;i++){
int x,y ;
cin >> x >> y ;
g[x].push_back({y,0}) ;
g[y].push_back({x,1}) ;
}
lev[1] =0 ;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q ;
q.push({0,1}) ;
while(!q.empty()){
int wt = q.top().first ;
int x = q.top().second ;
q.pop() ;
if(lev[x] < wt )continue ;
for(auto cur : g[x]){
int c=cur.first ;
int d= cur.second ;
if(lev[c] > wt+d){
lev[c] = wt+d ;
q.push({lev[c],c}) ;
}
}
}
*/
/*int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1) {
int q = a / m;
int t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
*/
/* //BL & LCA
vint adj[200005] ;
int depth[200005] ;
int parent[30][200005] ;
void dfs(int node, int par){
for(auto child : adj[node]){
if( child != par){
parent[0][child] = node ;
depth[child] = depth[node] +1 ;
dfs(child , node) ;
}
}
}
int raise(int x , int y){
int z =0 ;
while(y > 0){
if(y&1) x = parent[z][x] ;
y >>= 1 ;
z++ ;
}
return x ;
}
int lca(int x , int y){
if(depth[x] > depth[y]) swap(x,y) ;
int z = depth[y] - depth[x] ;
y = raise(y,z) ;
if(x== y) return x ;
for(int i =29 ;i >= 0 ;i--){
if(parent[i][x] != parent[i][y]){
x = parent[i][x] ;
y = parent[i][y] ;
}
}
return parent[0][x] ;
//HMMMMMMMMMMMMMMMMMMMMMMMMM
fr(0,n-1){
int a, b ;
cin >> a >> b ;
adj[a].pb(b) ;
adj[b].pb(a) ;
}
dfs(1,0) ;
fr(1,30){
for(int j = 1 ; j <= n ;j++){
parent[i][j] = parent[i-1][parent[i-1][j]] ;
}
}
}
*/
/*
struct segmenttree {
int n;
vector<int> st;
void init(int _n) {
this->n = _n;
st.resize(4 * n, 0);
}
void build(int start, int ending, int node, vector<int> &v) {
// leaf node base case
if (start == ending) {
st[node] = v[start];
return;
}
int mid = (start + ending) / 2;
// left subtree is (start,mid)
build(start, mid, 2 * node + 1, v);
// right subtree is (mid+1,ending)
build(mid + 1, ending, 2 * node + 2, v);
st[node] = st[node * 2 + 1] ^ st[node * 2 + 2];
}
int query(int start, int ending, int l, int r, int node) {
// non overlapping case
if (start > r || ending < l) {
return 0;
}
// complete overlap
if (start >= l && ending <= r) {
return st[node];
}
// partial case
int mid = (start + ending) / 2;
int q1 = query(start, mid, l, r, 2 * node + 1);
int q2 = query(mid + 1, ending, l, r, 2 * node + 2);
return q1 ^ q2;
}
void update(int start, int ending, int node, int index, int value) {
// base case
if (start == ending) {
st[node] = value;
return;
}
int mid = (start + ending) / 2;
if (index <= mid) {
// left subtree
update(start, mid, 2 * node + 1, index, value);
}
else {
// right
update(mid + 1, ending, 2 * node + 2, index, value);
}
st[node] = st[node * 2 + 1] + st[node * 2 + 2];
return;
}
void build(vector<int> &v) {
build(0, n - 1, 0, v);
}
int query(int l, int r) {
return query(0, n - 1, l, r, 0);
}
void update(int x, int y) {
update(0, n - 1, 0, x, y);
}
};
*/
/*
class DSU{
public:
vector<int>parent;
vint siz ;
DSU(int n) { parent.resize(n+1); for(int i=0;i<=n;i++) parent[i]=-1;
siz.resize(n+1); for(int i=0;i<=n;i++) siz[i]= 1 ;
}
int find_set(int x) { return parent[x]<0?x:parent[x]=find_set(parent[x]); }
bool union_set(int a,int b){ int pa=find_set(a); int pb=find_set(b);
if(pa==pb) { return 0; } if(parent[pa]>parent[pb]) { swap(pa,pb); }
parent[pa]+=parent[pb]; parent[pb]=pa; siz[pa]+= siz[pb] ; return 1; }
bool same_set(int a,int b){ return find_set(a)==find_set(b); }
int sizbol(int a){ return siz[find_set(a)] ;}};
*/
/*
int modInverse(int n, int p)
{
return binpow(n, p-2, p);
}
int ncr(int n, int r, int p)
{
if(n==r)
return 1;
if (r==0)
return 1;
int fac[n+1];
fac[0] = 1;
for (int i=1 ; i<=n; i++)
fac[i] = fac[i-1]*i%p;
return (fac[n]* modInverse(fac[r], p) % p *
modInverse(fac[n-r], p) % p) % p;
}
*/Swapping CodeChef Solution in PYTH 3
“# cook your dish here
t = int(input())
for i in range(t):
n = int(input())
l = list(map(int, input().split(' ')))
l.insert(0,0)
l2 = [0] * (n + 1)
l2[1] = l[1]
for j in range(2, n + 1):
l2[j] = max(l2[j - 1] + l[j] * j, l2[j - 2] + l[j] * (j - 1) + l[j - 1] * j)
print(l2[-1])Swapping CodeChef Solution in C
“#include <stdio.h>
#include <stdbool.h>
#define max(a, b) ((a>b)?a:b)
typedef long long int lli;
inline int input(){
int a=0; bool flag = false;
char c;
c=getchar_unlocked();
while(c<33){
c=getchar_unlocked();
}
if(c == 45){
flag = true;
c=getchar_unlocked();
}
while(c>=33){
a=(a<<3)+(a<<1)+(c-'0');
c=getchar_unlocked();
}
if(flag){
a *= -1;
}
return a;
};
lli dp[100001];
lli max_sum(int diff[], int n){
int i;
dp[0] = max(diff[0], 0);
dp[1] = max(dp[0], diff[1]); //base conditions
for(i=2; i<=n; i++){
dp[i] = max(diff[i] + dp[i- 2], dp[i- 1]);
}
return dp[n];
}
int main(void) {
int t, n, arr[100001], diff[100001], i;
lli res;
t = input();
while(t--){
n = input();
res = 0;
arr[0] = input();
res += (lli) arr[0];
if(n==1){
printf("%lli\n", res);
continue;
}
for(i=1; i<n; i++){
arr[i] = input();
res += (lli) arr[i] * (i+ 1);
diff[i- 1] = arr[i- 1] - arr[i];
}
res += max_sum(diff, n- 2); //for atleast 3 elems present in the array
printf("%lli\n", res);
}
return 0;
}
Swapping CodeChef Solution in JAVA
“import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
// a1+...+an=s+ak
//s1=x*k+m
//s2=x*k+m
/*
*/
public class Main {
private static void solve(int[] a) {
int n = a.length;
long[][] dp = new long[n][2];
dp[0][0]=a[0];
dp[0][1]=a[0];
dp[1][0]=(long) a[0]+(long)a[1]*2;
dp[1][1]=(long) a[1]+(long)a[0]*2;
for (int i = 2; i < n; i++) {
dp[i][0]=dp[i-1][0]+(long) a[i]*(i+1);
dp[i][0]=Math.max(dp[i][0],dp[i-1][1]+(long) a[i]*(i+1));
dp[i][1]=dp[i-2][0]+(long) a[i]*(i)+(long) a[i-1]*(i+1);
long val=dp[i-2][1]+(long) a[i]*(i)+(long) a[i-1]*(i+1);
dp[i][1]=Math.max(dp[i][1],val);
}
long ans = Math.max(dp[n-1][0],dp[n-1][1]);
System.out.println(ans);
}
static class BIT {
int[] array; // 1-indexed array, In this array We save cumulative information to perform efficient range queries and updates
public BIT(int size) {
array = new int[size + 1];
}
/**
* Range Sum query from 1 to ind
* ind is 1-indexed
* <p>
* Time-Complexity: O(log(n))
*
* @param ind index
* @return sum
*/
public int rsq(int ind) {
assert ind > 0;
int sum = 0;
while (ind > 0) {
sum += array[ind];
//Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number
ind -= ind & (-ind);
}
return sum;
}
/**
* Range Sum Query from a to b.
* Search for the sum from array index from a to b
* a and b are 1-indexed
* <p>
* Time-Complexity: O(log(n))
*
* @param a left index
* @param b right index
* @return sum
*/
public int rsq(int a, int b) {
assert b >= a && a > 0 && b > 0;
return rsq(b) - rsq(a - 1);
}
/**
* Update the array at ind and all the affected regions above ind.
* ind is 1-indexed
* <p>
* Time-Complexity: O(log(n))
*
* @param ind index
* @param value value
*/
public void update(int ind, int value) {
assert ind > 0;
while (ind < array.length) {
array[ind] += value;
//Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number
ind += ind & (-ind);
}
}
public int size() {
return array.length - 1;
}
}
public static void main(String[] args) throws FileNotFoundException {
FastScanner sc = new FastScanner();
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int[] a = sc.readArrayInt(n);
solve(a);
}
}
static void shuffleArray(int[] ar) {
// If running on Java 6 or older, use `new Random()` on RHS here
Random rnd = ThreadLocalRandom.current();
for (int i = ar.length - 1; i > 0; i--) {
int index = rnd.nextInt(i + 1);
// Simple swap
int a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
}
static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("/home/kirill/Downloads/ioi2006tests/writing_td/writing15.in")));
StringTokenizer st = new StringTokenizer("");
FastScanner() throws FileNotFoundException {
}
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long[] readArrayLong(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
int[] readArrayInt(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
}
}
// 1 2 3Swapping CodeChef Solution in PYPY 3
“import math
import bisect
def find_max_sum(arr):
incl = 0
excl = 0
for i in arr:
# Current max excluding i (No ternary in
# Python)
new_excl = excl if excl>incl else incl
# Current max including i
incl = excl + i
excl = new_excl
# return max of incl and excl
return (excl if excl>incl else incl)
try:
T = int(input())
for l in range(T):
n = int(input())
path = [int(i) for i in input().strip().split(" ")]
count = 0
for i in range(n):
count += (i+1)*path[i]
path1 = []
for i in range(n-1):
res1 = (i+2)*path[i] + (i+1)*path[i+1]
res2 = (i+1)*path[i] + (i+2)*path[i+1]
path1.append(res1-res2)
res = find_max_sum(path1)
if res > 0:
print(count+res)
else:
print(count)
except EOFError:
pass
Swapping CodeChef Solution in PYTH
“t = int(raw_input())
for i in range(t):
N = int(raw_input())
st = raw_input().split()
A = [0]
for x in st:
A.append(int(x))
# endfor x
S = 0
F = A[1]
for p in range(2,N+1):
v1 = F + p*A[p]
v2 = S + (p-1)*A[p] + p*A[p-1]
S = F
F = max(v1,v2)
# endfor p
print F
# endfor i
Swapping CodeChef Solution Review:
In our experience, we suggest you solve this Swapping CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Swapping CodeChef Solution.
“Conclusion:
I hope this Swapping CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
