akhauriyash/Code-Regression huggingface dataset:
N, Z, W = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

if N == 1:
    print(abs(W - a[0]))
elif N == 2:
    print(max(abs(a[1] - a[0]), abs(a[1] - W)))
elif N>=3:
    print(max(abs(a[-1] - W), abs(a[-1] - a[-2])))

Measured memory_bytes: 3188
#include <string>
#include <iostream>
using namespace std;

int main(int argc, char const *argv[])
{
    int N;
    cin>>N;
    float A[N];
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    float S=0;
    for (int i=0;i<N;i++){
        S += 1./A[i];
    }
    cout<<1./S<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i=0;i<(int)n;i++)
#define PI acos(-1)
#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
ll mod=1e9+7;
const int INF=1001001001;

vector<int> to[100005];

int main(){
    fast_io
    
    int n,m;
    cin>>n>>m;
    rep(i,m){
        int a, b;
        cin>>a>>b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    queue<int> q;
    vector<int> dist(n, INF);
    vector<int> pre(n,-1);
    dist[0]=0;
    q.push(0);

    while(!q.empty()){
        int v=q.front();q.pop();
        for(int u : to[v]){
            if(dist[u] != INF)continue;
            dist[u] = dist[v]+1;
            pre[u] = v;
            q.push(u);
        }
    }
    cout<<"Yes"<<endl;
    rep(i,n){
        if(i==0) continue;
        int ans=pre[i];
        ++ans;
        cout<<ans<<endl;
    }
    return 0;
    
}


Measured memory_bytes: 10576
#include <cstdio>
using namespace std;
int main() {
	int x,y,z;
	scanf("%d %d", &x,&y);

    if (y == 1) {
        printf("0");
    }
    else
    {
       z = x - y;
        printf("%d",z);
    }
    
    
	
	return 0;
}
	
    

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
struct apple
{
	int x,y,z;
	apple(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
	bool operator<(const apple &other)const
	{
		return z<other.z;
	}
}e[1000005];
int h[400005],fa[200005];
int findfather(int x){return x==fa[x]?x:fa[x]=findfather(fa[x]);}
int main()
{
	memset(h,127,sizeof(h));
	int n,q,m=0;
	cin>>n>>q;
	for(int i=0;i<n;i++)fa[i]=i;
	for(int i=1;i<=q;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		e[++m]=apple(a,b,c);
		h[a+1]=min(h[a+1],c+1);
		h[b+1]=min(h[b+1],c+2);
	}
	for(int i=1;i<(n<<1);i++)h[i]=min(h[i],h[i-1]+2);
	for(int i=1;i<(n<<1);i++)
	{
		int l1=i%n,l2=(i-1)%n;
		e[++m]=apple(l1,l2,h[i]);
	}
	sort(e+1,e+m+1);
	long long ans=0;
	for(int i=1;i<=m;i++)
	{
		int x=e[i].x,y=e[i].y,z=e[i].z;
		int l1=findfather(x),l2=findfather(y);
		if(l1!=l2)
		{
			ans+=z;
			fa[l1]=l2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 17788
#include<bits/stdc++.h>
using namespace std;

int main(){ 
int n,ans=0;
cin>>n;
vector<int> p(n);
for(int i=0; i<n; i++){
cin>>p[i];
}
for(int i=0; i<n; i++){
if(p[i]!=i+1){
ans++;
}
}
if(ans<=2){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef long double ld;

const ll INFL = 1e18;
const int INF = 1000000007;
const ld PI = acos(-1);
const ld EPS = 1e-13;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int x;
    cin >> x;
    cout << 1 - x << "\n";

    return 0;
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define RFOR(i, a, b) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using i64 = int64_t;
using u64 = uint64_t;
using vi = vector<int>;
using vl = vector<i64>;
using vd = vector<double>;
using pi = pair<int, int>;
using pl = pair<i64, i64>;
using pd = pair<double, double>;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> &v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

int main() {
  int n, k;
  cin >> n >> k;
  double ans = 0;
  FOR(i, 1, n + 1) {
    int score = i;
    double tmp = 1.0 / n;
    while (score < k) {
      score *= 2;
      tmp /= 2;
    }
    ans += tmp;
  }
  cout << setprecision(10) << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int n,ans,a[110];

int main (){
    scanf("%d",&n);
    for(int i = 0;i < n;i++) scanf("%d",&a[i]);
    for(int i = 0;i < n;i++)
	for(int j = i+1;j < n;j++)
	    for(int k = j+1;k < n;k++){
		int b[3];
		b[0] = a[i],b[1] = a[j],b[2] = a[k];
		sort(b+0,b+3);
		if(b[0] + b[1] > b[2] && b[0] != b[1]&&b[1] != b[2] && b[0] != b[2]) ans++;
	    }
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>

using namespace std;

typedef long int lint;
typedef long long int llint;

#define INF 1073741824
#define LINF 4611686018000000000
#define MOD 1000000007

int prime(int x) {
    if (x == 2) return 2;
    if (x % 2 == 0) x++;
    bool ok = false;
    while (!ok) {
        ok = true;
        for (int i = 3; i * i <= x; i+=2) {
            if (x % i == 0) {
                ok = false;
                break;
            }
        }
        if (!ok) x+=2;
    }
    return x;
}

int main() {
    int x;
    cin >> x;
    cout << prime(x) << endl;
    return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;




int main(){
    int n,k;cin >> n >> k;
    if(k>=n){
        cout << n-1 << endl;
        return 0;
    }
    string s;cin >> s;
    LL ans = n;
    LL a=0,b=0;
    for (int i = 0; i <= n; i++) {
        if(i==n){
            if(s[i]=='R'){
                a++;
            }
            else{
                b++;
            }
            break;
        }
        if(s[i]!=s[i+1]){
            if(s[i]=='R'){
                a++;
            }
            else{
                b++;
            }
        }
    }
    if(min(a,b)<=k){
        cout << n - 1 << endl;
    }
    else{
        cout << n - (a + b - 2 * k - 1) << endl;
    }
    return 0;
}


Measured memory_bytes: 512
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
left = []
right = [0]*N
for i in range(N):
    if i == 0:
        left.append(A[i])
    else:
        left.append(gcd(left[i - 1], A[i]))
for i in reversed(range(N)):
    if i == N - 1:
        right[i] = A[i]
    else:
        right[i] = gcd(right[i+1], A[i])

ans = 0
for i in range(N):
    if i == 0:
        an_ = right[i + 1]
    elif i == N - 1:
        an_ = left[i-1]
    else:
        an_ = gcd(left[i-1], right[i+1])
    ans = max(ans, an_)
print(ans)


Measured memory_bytes: 89580
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k, r, s, p; string t;
    cin >> n >> k >> r >> s >> p >> t;
    vector<int> f(t.size(), 0);
    for(int i=0; i+k<t.size(); ++i){
        if(t[i]==t[i+k]){t[i+k] = 1-t[i];}
    }
    int res = 0; 
    for(int i=0; i<t.size(); ++i){
        
        if(t[i]=='r'){
            if(f[i]==1){continue;}
            else{res += p;}
        }
        else if(t[i]=='s'){
            if(f[i]==1){continue;}
            else{res += r;}
        }
        else if(t[i]=='p'){
            if(f[i]==1){continue;}
            else{res += s;}
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3840
import sys
sys.setrecursionlimit(1000000)


N = int(input())
G = [[] for i in range(N)]

for i in range(N-1):
    u, v, w = map(int, input().split())
    if w % 2 == 0:
        G[u-1].append((v-1, 1))
        G[v-1].append((u-1, 1))
    else:
        G[u-1].append((v-1, -1))
        G[v-1].append((u-1, -1))

color = [None for i in range(N)]


def set_color(v, c):
    color[v] = c
    for next_v, d in G[v]:
        if color[next_v] is None:
            set_color(next_v, d*c)


set_color(0, 1)

for c in color:
    if c == 1:
        print(1)
    else:
        print(0)


Measured memory_bytes: 76544
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using ll = long long;
using vi = vector<int>; using vvi = vector<vi>;
const ll MOD = 1e9+7; ll INF = 1LL << 60;
const vi d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vi d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vi d4x = {1, 0, -1, 0}; vi d4y = {0, 1, 0, -1};
//---------------------------------------

int main(){
    int n; cin>>n;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];
    int cnt=0;
    int ans=0;
    for(int i=0; i<n-1; i++){
        if(h[i]>=h[i+1]){
            cnt++;
        }else{
            cnt=0;
        }
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main(){

    string a;

    cin >> a;

    for(int i = 0; i < a.length(); i++){
        if(a[i] == ','){
            a[i] = ' ';
        }
    }

    cout << a << endl;

    return 0;

}


Measured memory_bytes: 3624
# AGC016
import collections

s = list(input())
c = collections.Counter(s)
n = len(s)
check_word = []
if len(c) == n:
    ans = n // 2
else:
    common = c.most_common()
    cnt_list = []
    for i in range(len(c)):
        if common[i][1] == 1:
            break
        else:
            now_word = common[i][0]
            ##print(now_word)
            check_word.append(now_word)
            locate = [i for i, x in enumerate(s) if x == now_word]
            if 0 not in locate:
                locate.insert(0, -1)
            if n-1 not in locate:
                locate.append(n)
            #print(locate)
            diff_locate = [0] * (len(locate) - 1)
            for l in range(len(locate) - 1):
                diff_locate[l] = locate[l+1] - locate[l]
            ##print(diff_locate)
            cnt_list.append(max(diff_locate) - 1)
            ##print(cnt_list)
            ##print("\n")
    if n % 2 == 1:
        if s[n // 2] in check_word:
            pass
        else:
            cnt_list.append(n // 2 )
    else:
        if s[n // 2] in check_word:
            pass
        if s[n // 2 - 1] in check_word:
            pass
        else:
            cnt_list.append(n // 2)
    ans = min(cnt_list)
print(ans)

Measured memory_bytes: 3316
#include <iostream>
using namespace std;

template<class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

static const int MAX_N = 1e5+7;
static const int INF = 1e9+7;
int h[MAX_N];
int dp[MAX_N];

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> h[i];
  }
  fill(dp, dp+MAX_N, INF);
  dp[0] = 0;
  dp[1] = abs(h[1] - h[0]);
  for (int i = 2; i < N; ++i) {
    chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
    chmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
  }
  cout << dp[N-1] << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(void)
{
	int k, sum, limit;
	k = 0;

	while(cin >> k, k) {
		sum = limit = 0;
		limit = k * (k-1) / 2;

		for(int i=0; i < limit; i++) {
			int c; cin >> c;
			sum += c;
		}
		printf("%d\n", (sum/(k-1)));
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define int long long int

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
#undef int
int main(){
#define int long long int
    int a,b;cin>>a>>b;
    cout<<(a*b)/(gcd(a,b));
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int main(){

cout<<fixed<<setprecision(12);

double r;
cin>>r;

double PI=acos(-1);
double area =r*r*PI;
double cir =(r+r)*PI;

cout<<area<<" "<<cir<<endl;

return 0;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000007
#define M 15000007
#define N 100005
#define MAX 5032117	
#define LOG 100
#define KOK 333
using namespace std;

int n,x,ans;
map<int,int> MP[2];
vector<ii> v[2];

int main() {

	//freopen("input.txt","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%d",&x);

		MP[i&1][x]++;

	}

	for(int i=0;i<2;i++) {

		for(int j=1;j;j++) {

			if(!MP[i][j]) {

				MP[i][j]=0;

				break ;

			}

		}		

		for(auto x:MP[i]) v[i].pb({x.nd,x.st});

		sort(all(v[i]),greater<ii>());

	}

	ans=2*n;

	for(int i=0;i<2;i++) {

		for(int j=0;j<2;j++) {

			if(v[0][i].nd==v[1][j].nd) continue ;

			umin(ans,n-v[0][i].st-v[1][j].st);

		}

	}

	printf("%d",ans);

}


Measured memory_bytes: 6136
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    double x = n / 1.08;
    x = (int)x;
    double y = x * 1.08;
    y = (int)y;
    double z = (x+1) * 1.08;
    z = (int)z;
    
    if(n == y){
      System.out.println((int)x);
    }else if(n == z){
      System.out.println((int)x+1);
    }else{
      System.out.println(":(");
    }
    
  }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template<typename T>
T gcd(T a, T b)
{
	if (a < b)	return gcd(b, a);
	T r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

template<typename T>
T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

template<typename T>
T ext_gcd(T a, T b, T& x, T& y)
{
	x = 1;
	y = 0;
	T x0 = 0, y0 = 1;
	while (b != 0)
	{
		T q = a / b;
		a -= q * b;
		swap(a, b);
		x -= q * x0;
		swap(x, x0);
		y -= q * y0;
		swap(y, y0);
	}
	return a;
}

template<typename T>
T inv_mod(T a, T mod)
{
	T t1, t2;
	ext_gcd(a, mod, t1, t2);
	t1 %= mod;
	if (t1 < 0)		t1 += mod;
	return t1;
}

template<typename T>
T combination_large(T n, T k, T mod)
{
	if (n < k || n < 0 || k < 0)	return 0;
	vector<T> inv(n + 1, 1), fact(n + 1, 1), fact_inv(n + 1, 1);
	for (T i = 2; i <= n; ++i)
	{
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fact[i] = (fact[i - 1] * i) % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

template<typename T>
T combination(T n, T k, T mod = 1)
{
	vector<vector<T>> table(n + 1, vector<T>(k + 1, 1));
	for (T i = 1; i <= n; ++i)
	{
		table[i][0] = 1;
		for (T j = 1; j <= n; ++j)
		{
			table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;
		}
	}
}


void rec(const int N, const int n, const int k, const string& orig)
{
	const int m = min(n, k + 1);
	for (int i = 0; i < m; ++i)
	{
		const auto next = orig + static_cast<char>('a' + i);
		if (n < N)
		{
			if (i == k)
			{
				rec(N, n + 1, k + 1, next);
			}
			else
			{
				rec(N, n + 1, k, next);
			}
		}
		else
		{
			cout << next << endl;
		}
	}
}

int main(int, char**)
{
	long long N;
	scanf("%lld",&N);

	rec(N, 1, 0, "");

	return 0;
}


Measured memory_bytes: 1536
// stoiはC++11
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
#include <functional>
#include <cctype>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)n; ++i)

int main()
{
	string st;
	stack<int> q;
	int lhs, rhs;

	while(cin >> st) {
		if(st == "+") {
			rhs = q.top();
			q.pop();
			lhs = q.top();
			q.pop();
			q.push(lhs + rhs);
		}

		else if(st == "-") {
			rhs = q.top();
			q.pop();
			lhs = q.top();
			q.pop();
			q.push(lhs - rhs);
		}
		else if(st == "*") {
			rhs = q.top();
			q.pop();
			lhs = q.top();
			q.pop();
			q.push(lhs * rhs);
		}


		else {
			q.push(stoi(st));
		}
	}

	cout << q.top() << endl;

	return 0;
}

Measured memory_bytes: 1204
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE MultiWayIf #-}

import Control.Monad
import Control.Monad.ST
import Control.Monad.State
import Control.Monad.Primitive
import Control.Applicative
import Control.Arrow
import Data.List
import Data.Array
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
import Data.Maybe
import Data.Bits
import Data.Ord
import Data.Ratio
import Data.Int
import Data.Char
import qualified Data.IntMap as IM
import qualified Data.ByteString.Char8 as BS
import qualified Data.Set as Set
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector.Generic as VG
import qualified Data.Vector.Generic.Mutable as VGM
import qualified Data.Sequence as Sq
import Data.Tuple
import Data.Function
import Text.Printf
import Debug.Trace
import Numeric

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)

listToTuple2 [a,b] = (a,b)
listToTuple3 [a,b,c] = (a,b,c)
listToTuple4 [a,b,c,d] = (a,b,c,d)
listToTuple5 [a,b,c,d,e] = (a,b,c,d,e)

readIntBS = fst . fromJust . BS.readInt

for = flip map

infixr 1 ?
(?) :: Bool -> (a,a) -> a
(?) b t = (if b then fst else snd) t

main :: IO ()
main = do
  n <- readLn :: IO Int
  ws <- lines <$> getContents

  putStrLn $ if func ws && (length . nub) ws == length ws then "Yes" else "No"

func (x:[]) = True
func (x:y:xs) = if last x == head y then func (y:xs) else False
    


Measured memory_bytes: 636
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1LL<<60;
const ll mod = 1e9 + 7;

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}

double DegreeToRadian(double degree){
    return degree * M_PI / 180.0;
}


int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};


///////////////////////////////////////////////////////////////////////////////////

int main(){
    ll a, b, c,d;
    cin >> a >> b >> c >> d;
    ll ans = 0;
    ans = max(a*c, max(a*d, max(b*c, b*d)));
    cout << ans << endl;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;

int main(){
  
  int N;
  cin >> N;
  
  if(N % 2 == 0){
    cout << N << endl;
    return 0;
  }else{
    cout << N * 2 << endl;
    return 0;    
  }
  return -1;
}

Measured memory_bytes: 3620
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	long i=0,n,m,x=0,y=0,a[214514];
	for(cin>>n;i<n;cin>>a[i],x+=a[i++]);
	for(i=0;i<n-1;i++)
	{
		y+=a[i];
		x-=a[i];
		if(i==0)m=abs(x-y);
		else m=min(m,abs(x-y));
	}
	cout<<m<<endl;
	return 0;
}

Measured memory_bytes: 1792
object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  val Array(a, b) = readLine.trim.split(' ').map(_.toInt)
  val deck = new ADeck(readLine.trim.split(' ').map(_.toInt))
  val bDeck = readLine.trim.split(' ').map(_.toInt).toList
  println(
    searchMax(deck, bDeck)
  )
  def searchMax(a: ADeck, b: List[Int]): Int = {
    def sub(cards: List[Int], position: Int): Int = {
      cards match {
        case h::t ⇒ a.nextN(position, h) match {
          case Some(p) ⇒ sub(t, p) + 1
          case None ⇒ 1
        }
        case _ ⇒ 1
      }
    }
    b match {
      case h::t ⇒ a.firstN(h) match {
        case None ⇒ searchMax(a, t)
        case Some(p) ⇒ math.max(sub(t, p), searchMax(a, t))
      }
      case Nil ⇒ 0
    }
  }

  class ADeck(private val deck: Array[Int]) {
    private val cards = (0 to 1000).map{n ⇒ deck.map{
      case `n` ⇒ 1
      case _ ⇒ 0: Int
    }.also{arr ⇒ for (i ← 1 until arr.length) arr(i) += arr(i - 1)}}.toArray
    def nextN(position: Int, n: Int): Option[Int] = {
      lowerBound(cards(n), cards(n)(position) + 1)
    }
    def firstN(n: Int): Option[Int] = {
      lowerBound(cards(n), 1)
    }
  }
  def lowerBound[T](array: Array[T], target: T)(implicit ordering: Ordering[T]): Option[Int] = {
    var left = 0
    var right = array.length
    while (left < right){
      val mid = (left + right) / 2
      if (ordering.compare(array(mid), target) < 0){
        left = mid + 1
      }else {
        right = mid
      }
    }
    if (right == array.length) None
    else Some(right)
  }
  def upperBound[T](array: Array[T], target: T)(implicit ordering: Ordering[T]): Option[Int] = {
    var left = 0
    var right = array.length
    while(left < right){
      val mid = (left + right) / 2
      if (ordering.compare(array(mid), target) <= 0){
        left = mid + 1
      }else {
        right = mid
      }
    }
    if (right == array.length) None
    else Some(right)
  }
  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}


Measured memory_bytes: 458120
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> vec(N);

  for(int i=0;i<N;i++) {
    cin >> vec[i];
  }

  int start = 0;

  int times = 0;

  while(start <= X) {
    start += vec[times];
    times++;
  }

  if(times>N+1) {
    cout << N+1 << endl;
  } else {
    cout << times << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<ll, ll>>> witness;
ll n;
bool judge(ll bit){
     for (ll i = 0; i < n; i++)
        {
            if (!(bit & (1 << i)))
                continue;
            for (pair<ll,ll> xy :witness[i])
            {
                ll x = xy.first;
                ll y = xy.second;
                if (y == 1 && !(bit & (1 << x)))
                    return  false;
                if (y == 0 && (bit & (1 << x)))
                    return false;
            }
        }
        return true;
}
int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> n;
    witness.resize(n);
    for (ll i = 0; i < n; i++)
    {
        ll a;
        cin >> a;
        witness[i].resize(a);
        for (ll j = 0; j < a; j++)
        {
            cin >> witness[i][j].first >> witness[i][j].second;
            witness[i][j].first--;
            
        }
    }
    ll res = 0;
    for (ll bit = 0; bit < (1 << n); bit++)
    {
        if (judge(bit))
        {
            ll cnt = 0;
            for (ll i = 0; i < n; i++)
            {
                if (bit & (1 << i))
                    cnt++;
            }
            res = max(res, cnt);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
n = gets.to_i
s = gets.chomp

count = 0

(0..999).each{ |i|
	index = 0
	sprintf("%03d", i).split("").each{ |ss|
		index = s.index(ss, index)
		if index == nil then
			break
		else
			index += 1
		end
	}
	if index != nil then
		count += 1
	end
}

puts count


Measured memory_bytes: 2044
/*
{

AuThOr Gwj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n;
int sum=0;
int a[2002];
bitset<4000000+1> bs;
int main(){
	fastio;
	R(n);
	rb(i,1,n){
		R(a[i]);
		sum+=a[i];
	}
	bs[0]=1;
	rb(i,1,n){
		bs|=bs<<a[i];
	}
	rb(i,(sum+1)/2,sum){
		if(bs[i]){
			cout<<i<<endl;
			return 0;
		}	
	}
	return 0;
}



Measured memory_bytes: 5128
import sys
a,b=map(int,input().split())
c=list(map(int,input().split()))
c.sort()
d=[0]*1000000
for i in range(b-1):
  d[i]+=abs(c[i]-c[i+1])
  

d.append(a-(c[-1]-c[0]))

print(a-max(d))





Measured memory_bytes: 26444
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define readll(x) scanf("%I64d",&x)
#define mod 1000000007
#define eps 1e-6
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n,a[N],dp[N][2];

int main(){
    readi(n);
    lp(i,1,n) readi(a[i]);

    dp[1][0] = dp[1][1] = 1;
    lp(i,2,n){
        dp[i][0] = a[i-1] <= a[i] ? dp[i-1][0] : 1 + dp[i-1][0];
        dp[i][0] = min(dp[i][0], 1 + dp[i-1][1]);

        dp[i][1] = a[i-1] >= a[i] ? dp[i-1][1] : 1 + dp[i-1][1];
        dp[i][1] = min(dp[i][1], 1 + dp[i-1][0]);
    }
    cout <<min(dp[n][0], dp[n][1]);
}

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//ios::sync_with_stdio(0);cin.tie(0);


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <cmath>
#include <tuple>
#include <bitset>
#include <utility>
#include <climits>
#include <iomanip>

#define push emplace_back
#define each(i, x) for (auto i=0; i < x; i++)
using ull = unsigned long long;
constexpr auto mod = 1000000007;
constexpr auto INF = ULLONG_MAX;

using namespace std;
template <typename T> inline void dump(const T& x) { cout << "[" << x << "]" << endl; }
template <typename T> inline void dump(const vector<T>& x) { for (const auto v : x) { cout << v << " "; } cout << endl; }
template <typename T> inline void sort_asc(vector<T>& x) { std::sort(x.begin(), x.end()); }
template <typename T> inline void sort_desc(vector<T>& x) { std::sort(x.begin(), x.end(), greater<T>()); }
template <typename T> inline T max_value(vector<T>& x) { return *max_element(x.begin(), x.end()); }
template <typename T> inline T min_value(vector<T>& x) { return *min_element(x.begin(), x.end()); }
template <typename T> inline T sum_value(vector<T>& x) { return accumulate(x.begin(), x.end(), 0ULL); }

int main() {
  ull n;
  cin >> n;

  ull res = 0;
  for (ull i=1; i < (n+1); i++) {
    auto s = std::to_string(i);
    if (s.size() % 2 == 1) {
      res++;
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define pb push_back
#define ppb pop_back
#define vi vector<int>
#define rep(i,n) for(int i=0;i<n;i++)
#define ren(i,n) for(int i=n-1;i>=0;i--)
#define iter(it,v) for(auto it:v)
#define iterp(it,v) for(auto it=v.begin(),it!=v.end();it++)
#define itern(it,v) for(auto it=v.rbegin();it!=v.rend();it++)
#define w(n) while(n--)
#define forp(i,a,b) for(int i=a;i<=b;i++)
#define forn(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%d",&a)
#define pf(a) printf("%d",a)
#define init(a,r) for(auto&i:a) i=r;
#define inpt(a,n) for(int i=0;i<n;i++) cin>>a[i];
#define inp(a) for(int&i:a) cin>>i;
#define diss(a) for(int i:a) cout<<i<<' ';
#define disn(a) for(int i:a) cout<<i<<'\n';
#define debug(a) cout<<#a<<": ";for(auto i:a)cout<<i<<" ";cout<<'\n';
#define mpii map<int,int>
#define sii set<int>
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define all(v) v.begin(),v.end()
#define bitc __builtin_popcount
#define fst ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define pq priority_queue
#define pii pair<int,int>
#define cs(a) cout<<a<<' '
#define cn(a) cout<<a<<'\n'
#define deb(a,b) cout<<a<<' '<<b<<endl;
#define yy "YES"
#define nn "NO"
#define ff first
#define ss second
typedef long long ll;
const int mod=1e9+7,mod1=998244353;
const int N=105,k=1e5+6;
int w[N],v[N],dp[N][k];
int n,W;
int solve(int i,int W){
    if(i>=n||W<=0)
        return 0;
    if(dp[i][W]!=-1)
        return dp[i][W];
    int a=0,b=0;
    if(W>=w[i])
        a=v[i]+solve(i+1,W-w[i]);
    b=solve(i+1,W);
    return dp[i][W]=max(a,b);
}
void a_b_l(){
    cin>>n>>W;
    rep(i,n){
        cin>>w[i]>>v[i];
    }
    memset(dp,-1,sizeof(dp));
    cn(solve(0,W));
}
signed main(){
    fst;
    int t=1;
    //cin>>t;
    w(t)
    	a_b_l();
}

Measured memory_bytes: 82304
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N = 2e5 + 20;
int n,a[N],sum[N],x[N],l,r,ans;
signed main(){
    cin>>n;
    cin>>a[0];
    sum[0]=a[0];
    x[0]=a[0];
    for(int i=1;i<n;i++){
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
        x[i]=x[i-1]^a[i];
    }
    for(int r=0;r<n;r++){
        while((sum[r]-sum[l-1])!=(x[r]^x[l-1])) l++;
        ans+=r-l+1;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4992
n=int(input())
d=[int(x) for x in input().split()]
ans=True
if(d[0]!=0):
    ans=False
d.sort()
dd=[0]*10**5
max=0
for i in d:
    dd[i]+=1
    if(max<i):
        max=i

now=1
before=0
if(dd[0]!=1):
    ans=False
else:
    before=1

for i in range(1,max+1):
    if(dd[i]==0):
        ans=False
    now=now*(before**dd[i]) % 998244353
    before=dd[i]
    #print(dd[i],now)

if(ans):
    print(now)
else:
    print("0")

Measured memory_bytes: 14396
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using static System.Console;
using static System.Linq.Enumerable;
using static System.Numerics.BitOperations;

namespace abc176
{
    class SolverB
    {
        static void Main()
        {
            SetOut(new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false});
            new SolverB().Solve();
            Out.Flush();
        }

        public void Solve()
        {
            checked
            {
                var ns = Get.Str();
                var ints = ns.ToCharArray().Select(x=> int.Parse(x.ToString())).ToArray();
                long sum = 0;
                for(int i=0; i<ints.Length; i++){
                    sum+=ints[i];
                }
                if(sum%9 == 0){
                    WriteLine("Yes");
                }else{
                    WriteLine("No");
                }
            }
        }




        static class Get
        {
            public static string Str() => ReadLine().Trim();
            public static int Int() => int.Parse(Str());
            public static long Long() => long.Parse(Str());
            public static double Double() => double.Parse(Str());
            public static string[] Strs() => Str().Split(' ', StringSplitOptions.RemoveEmptyEntries);
            public static int[] Ints() => Strs().Select(int.Parse).ToArray();
            public static long[] Longs() => Strs().Select(long.Parse).ToArray();
            public static double[] Doubles() => Strs().Select(double.Parse).ToArray();
            static bool TypeEq<T,U>() => typeof(T).Equals(typeof(U));
            static T TypeConv<T,U>(U u) => (T)Convert.ChangeType(u, typeof(T));
            static T TypeConv<T>(string s) => TypeEq<T, int>() ?   TypeConv<T, int>(int.Parse(s))
                                        : TypeEq<T, long>() ?       TypeConv<T, long>(long.Parse(s))
                                        : TypeEq<T, double>() ?     TypeConv<T, double>(long.Parse(s))
                                        : TypeConv<T, string>(s);
            public static (T,U) Tuple<T,U>() {string[] strs = Strs(); T t = TypeConv<T>(strs[0]); U u = TypeConv<U>(strs[1]); return(t,u);}
            public static (T,U,V) Tuple<T,U,V>() {string[] strs = Strs(); T t = TypeConv<T>(strs[0]); U u = TypeConv<U>(strs[1]); V v = TypeConv<V>(strs[2]); return(t,u,v);}
        }
    }
}


Measured memory_bytes: 34664
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    string s;
    cin >> s;

    vector<int> dp(2019,0);

    ll ans = 0;
    rep(i, s.size()){
        vector<int> tdp(2019,0);
        int c = s[i] - '0';

        for (int j = 0; j < 2019; j++)
        {
            //if (dp[j] == 0) continue;
            int new_key = j*10+c;
            new_key %= 2019;
            tdp[new_key] = dp[j];
        }
        tdp[c]++;        

        dp = tdp;
        ans += dp[0];
        // for(auto itr = dp.begin(); itr != dp.end(); ++itr){
        //     cout << itr->first << ":" << itr->second << endl;
        // }
        // cout << endl;
    }

    cout << ans << endl;

}



Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

template <typename T> struct BIT {
    int n;
    vector<T> bit;
    BIT(int n_) : n(n_ + 1), bit(n, 0) {
    }

    void add(int i, T x) {
        if (i == 0) {
            cout << "BIT add ERROR" << endl;
            exit(1);
        }
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[idx] += x;
        }
    }

    T sum(int i) {
        T s(0);

        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[idx];
        }
        return s;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;

    unordered_map<int, int> mp;
    unordered_map<int, int> ball;

    rep(i, N) {
        int c;
        cin >> c;
        int now = i + 1;
        if (mp[c] == 0) {
            mp[c] = now;
        } else {
            ball[mp[c]] = now;
            mp[c] = now;
        }
    }

    vec<vec<pair<int,int>>> query(N+1);
    vec<int> l(Q), r(Q);
    rep(i, Q) {
        cin >> l[i] >> r[i];
        query[l[i]].push_back({r[i],i});
    }

    BIT<ll> bit(N);
    vec<int> ans(Q);
    for (int i = N; i > 0; --i) {
        if (ball[i] != 0) bit.add(ball[i], 1);
        for (auto [R,index] : query[i]) {
            ans[index] = bit.sum(R);
        }
    }

    rep(i, Q) {
        cout << r[i] - l[i] + 1 - ans[i] << endl;
    }
}


Measured memory_bytes: 74636
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var arrayA = new int[N];
            var arrayB = Console.ReadLine().Split().Select(int.Parse).ToArray();

            for (int i = 0; i < N - 2; i++)
            {
                arrayA[i] = new int[2] { arrayB[i], arrayB[i + 1] }.Min();
            }

            Console.WriteLine(arrayA.Sum() + arrayB[0] + arrayB[N - 2]);
        }
    }
}


Measured memory_bytes: 13396
from collections import defaultdict

H, W, N = list(map(int, input().split()))
YX = [list(map(int, input().split())) for _ in range(N)]

memo = defaultdict(int)
for y, x in YX:
    y -= 1; x -= 1
    for i in range(9):
        memo[y - 1 + i//3, x - 1 + i%3] += 1

ans = [0] * 10
for y, x in memo:
    if 0 < x < W-1 and 0 < y < H-1:
        ans[memo[y, x]] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
print(*ans)

Measured memory_bytes: 191308
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

bool isSubstr(str s, str t){
  return s.substr(0,min(t.length(),s.length()))==t;
}

int main(){
  str s;
  cin >> s;
  reverse(s.begin(),s.end());
  str words[4] = {"dream", "dreamer", "erase", "eraser"};
  REP(i,4) reverse(words[i].begin(),words[i].end());
  while(s.length()>0){
    bool sub = false;
    REP(i,4){
      if(isSubstr(s,words[i])){
        s = s.substr(words[i].length(),s.length()-words[i].length());
        sub = true;
      }
    }
    if(!sub){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 512
[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reada f = stdin.ReadLine().Split() |> Array.map f
let reads f = stdin.ReadLine().Split() |> Array.toList |> List.map f

let comb n r =
    if n = r then 1L
    elif r = 0L then 1L
    else
        let a = List.fold ( * ) 1L [n .. -1L .. n - r + 1L]
        let b = List.fold ( * ) 1L [r .. -1L .. 1L]
        a / b

[<EntryPoint>]
let main _ =
    let n = read int
    let xs =
        Array.init n (fun _ -> (read string).ToCharArray() |> Array.sort)
        |> Array.groupBy id
        |> Array.choose (fun x ->
                match (snd x |> Array.length) with
                | y when y > 1 -> Some (int64 y)
                | _ -> None
            )
    Array.fold (fun s x -> s + comb x 2L) 0L xs
    |> printfn "%i"
    0

Measured memory_bytes: 50044
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
#define db double
#define pb push_back
#define pa pair<signed, signed>
#define mp make_pair
#define sc(z) scanf("%d", &(z))
#define _ff(i, a, b) for(signed i = (a); i <= (b); ++i)
#define _rr(i, a, b) for(signed i = (a); i >= (b); --i)
#define _f(i, a, b) for(signed i = (a); i < (b); ++i)
#define _r(i, a, b) for(signed i = (a); i > (b); --i)
#define lson node<<1, l, mid
#define rson node<<1|1, mid + 1, r
#define lowbit(x) x&(-x)
const signed inf = 0x3f3f3f3f;
const signed maxn = 1e7 + 5;
int main() {
    int n; sc(n);
    while (n--) {
        printf("ACL");
    }
    return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) ((int)(a).size())
typedef long long int64;
int64 s[10009], dp[5555];
int main() {
#ifdef LOCAL
  freopen(".a.in", "r", stdin);
#endif
  ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
  int64 n, k;
  cin >> n >> k;
  vector<int64> P(n + 1), C(n + 1), vis(n + 1);
  for (int i = 1; i <= n; ++i) cin >> P[i];
  for (int i = 1; i <= n; ++i) cin >> C[i];
  int64 ans = -2e18;
  auto cal = [&](vector<int64> &A) {
    int m = SZ(A);
    for (int i = 1; i <= m; ++i) dp[i] = -2e18;
    s[0] = 0;
    for (int i = 0; i < m; ++i) A.push_back(A[i]);
    for (int i = 0; i < SZ(A); ++i) {
      s[i + 1] = s[i] + A[i];
      for (int j = 1; i + 1 - j >= 0; ++j) dp[j] = max(dp[j], s[i + 1] - s[i + 1 - j]);
    }
    for (int i = 2; i <= m; ++i) dp[i] = max(dp[i - 1], dp[i]);
  };
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) {
      vector<int64> A;
      int j = i;
      int64 sum = 0, tp = 0;
      while (!vis[j]) {
        vis[j] = 1;
        A.push_back(C[j]);
        sum += C[j];
        j = P[j];
      }
      tp = k / SZ(A);
      int64 m = SZ(A);
      cal(A);
      if (sum <= 0)
        ans = max(ans, dp[min(k, m)]);
      else if (tp == 0)
        ans = max(ans, dp[k]);
      else {
        ans = max(ans, max((tp - 1) * sum + max(dp[m], tp == 1 ? dp[m] : dp[0]), tp * sum + max(dp[k % m], dp[0])));
      }
    }
  cout << ans;

  return 0;
}
//2020.08.15 20:18:44


Measured memory_bytes: 3964
////////////////////////////////////////////////
//  ********  *      *    *******    * *      //                 :
//  *         *      *   *       *   *   *    //     64 BITS     C     64 BITS
//  *****     *      *  *         *  *     *  //                 +
//  *         *      *  ***********  *     *  //:  19 - 6 - 2020 +   19 - 6 - 2020 :
//  *         *      *  *         *  *   *    //                 1
//  *         ********  *         *  * *      //     64 BITS     7     64 BITS
////////////////////////////////////////////////                 :
#define ll long long
#define ui unsigned int
#define ud unsigned double
#define mp make_pair
#define pii pair<int,int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pdi pair<double,int>
#define pb push_back
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const double pi = acos(-1.0);
int main()
{
    int r;
    int e;
    string m;
    string a;
    string g;
    cin>>m>>a>>r>>e>>g;
    if (m == g){
        r--;
    }
    else{
        e--;
    }
    cout<<r<<" "<<e<<"\n";
    return 0;
}


Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<" ";}
#define dumpl(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cout << fixed << setprecision(10);
	int M = 256;
	for (int N; cin >> N&&N;) {
		vector<int> I(N + 1); rep(i, 1, N + 1) { cin >> I[i]; }
		vector<int> R(N + 1);
		double minH = INF;
		int ansS, ansA, ansC;
		rep(S, 0, 16)rep(A, 0, 16)rep(C, 0, 16) {
			R[0] = S;
			vector<int> cnt(256, 0);
			rep(i, 1, N + 1) {
				R[i] = (A*R[i - 1] + C) % M;
				int O = (I[i] + R[i]) % M;
				cnt[O]++;
			}
			double H = 0;
			rep(i, 0, 256) {
				if (cnt[i] == 0)continue;
				H += -cnt[i] * log((double)cnt[i] / N);
			}
			if (minH > H + 1e-9) {
				minH = H;
				ansS = S, ansA = A, ansC = C;
			}
		}
		cout << ansS << " " << ansA << " " << ansC << endl;
	}
	return 0;
}

Measured memory_bytes: 3348
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <utility>
#include <functional>
#define INF 0x3f3f3f3f
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

int dp[60][60000];
int l[60];
int main() {
	int n; cin >> n;
	memset(dp, 0x3f, sizeof(dp));
	int cnt = 0;
	rep(i, n) {
		cin >> l[i];
		cnt += l[i];
		dp[i][cnt] = 0;
	}
	rep(i, n)rep(j, 60000) {
		if (dp[i][j] == INF)continue;
		int Min = j, Max = j + dp[i][j];
		int sum = 0;
		for (int k = i + 1; k < n; k++) {
			sum += l[k];
			dp[k][min(Min, sum)] = min(dp[k][min(Min, sum)], max(sum, Max) - min(Min, sum));
		}
	}
	int Min = INF;
	rep(i, cnt)Min = min(Min, dp[n - 1][i]);
	cout << Min << endl;
}


Measured memory_bytes: 17196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, a[100008], mx, mn, c;
string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n;
	
	c = 0;
	rep(i, 1, n){
		cin >> a[i];
		mx = (i == 1)? a[i] : max(a[i], mx);
		mn = (i == 1)? a[i] : min(a[i], mn);
	}
	if(mx-mn > 1){
		print("No")
		return 0;
	}
	if(mx == mn){
		if((1 <= mx && mx <= n/2) || mn == n-1){
			print("Yes")
		}
		else{
			print("No")
		}
	}
	else{
		rep(i, 1, n){
			if(a[i] == mx){c++;}
		}
		if(c == 1){
			print("No")
			return 0;
		}
		if(n-c+1 <= mx && mx <= n-c+c/2){
			print("Yes")
		}
		else{
			print("No")
		}
	}
	
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
int main (){
	int a,b,i;
	char str[15];
	scanf("%s",str);
	a=strlen(str);
	if(str[i]!='A'){
		printf("WA\n");
		return 0;
	}
	int count=0;
	for(i=2;i<strlen(str)-1;i++){
		if(str[i]=='C'){
			count++;
			}
	}
	if(count!=1){
		printf("WA\n");
		return 0;
	}
	count=0;
	for(i=0;i<strlen(str);i++){
		if(str[i]>='a' && str[i]<='z'){
			count++;
			}
	}
	if (count!=a-2){
			printf("WA\n");
			return 0;
		}
	printf("AC\n");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#include<cstdlib>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long ll;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
  int n;
  cin >> n;

  vector<ll> a(n);
  rep(i,n) cin >> a.at(i);

  ll ans=a.at(0);
  rep(i,n) ans = gcd(ans,a.at(i));

  cout << ans;
}

Measured memory_bytes: 4024
#include<iostream>
using namespace std;

int n,m;

int main()
{
	ios::sync_with_stdio(false);
	while(cin>>n>>m){
		int v,w,ans=1e6;
		for(int i=0;i<n;++i)
		{
			cin>>v>>w;
			if(w<=m)	ans=min(ans,v);
		}
		if(ans==1e6)	cout<<"TLE"<<endl;
		else	cout<<ans<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 256