akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

main() {
    string A,B,C; cin >> A >> B >> C;
    int apos=0,bpos=-1,cpos=-1;
    bool a=true,b=false,c=false;
    while(true){
        if(a){
            a=false;
            if(apos==A.size()){cout << "A" << endl; break;}
            else{
                if(A[apos]=='a'){a=true; apos++;}
                else if(A[apos]=='b'){b=true; bpos++;}
                else {c=true; cpos++;}
            }
        }
        else if(b){
            b=false;
            if(bpos==B.size()){cout << "B" << endl; break;}
            else{
                if(B[bpos]=='a'){a=true; apos++;}
                else if(B[bpos]=='b'){b=true; bpos++;}
                else {c=true; cpos++;}
            }
        }
        else if(c){
            c=false;
            if(cpos==C.size()){cout << "C" << endl; break;}
            else{
                if(C[cpos]=='a'){a=true; apos++;}
                else if(C[cpos]=='b'){b=true; bpos++;}
                else {c=true; cpos++;}
            }
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define flsh fflush(stdout)
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1000000000007
 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;


void solve()
{
   ll n;
   cin>>n;
   ll i,j;
   string s;
   ll res=0;
   cin>>s;
   for(i=2;i<n;i++)
   {
       if(s[i]=='C'&&s[i-1]=='B'&&s[i-2]=='A')
       {
         res++;
       }
   }
   cout<<res<<"\n";
}


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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
#define sanyes ios_base::sync_with_stdio(0), cout.tie(0); cin.tie(0);
#define llong long long int
#define pb push_back
#define bpc __builtin_popcount
#define f first
#define s second

const llong mxn = 1e5 + 7;
const llong mod = 1e9 + 7;
const llong inf = 1e18 + 9;

using namespace std;

llong a, b, c;

int main(){
    cin >> a >> b >> c;
    llong x = a, y = b, z = c;
    for (int i = 0; i <= 30; i ++){
        if(a % 2 || b % 2 || c % 2){
            cout << i;
            return 0;
        }a = (y + z) / 2;
        b = (x + z) / 2;
        c = (x + y) / 2;
        x = a, y = b, z = c;
    }cout << -1;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,b,e) for (common_type_t<decltype(b),decltype(e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define rep(i,n)   FOR (i, size_t{}, n)
#define ALL(x)     begin (x), end (x)
using namespace std;
using ll = int64_t;
constexpr ll inf = 2e18;

inline auto run_length_encoding (const string & s)
{
  using P = pair <char, size_t>;
  vector <P> res;
  if (! s.empty ())
  {
    res.emplace_back (s.front (), 1);
  }
  FOR (ite, next (begin (s)), end (s))
  {
    auto c = * ite;
    char prev_c;
    tie (prev_c, ignore) = res.back ();
    if (prev_c == c)
    {
      get <1> (res.back ()) += 1;
    }
    else
    {
      res.emplace_back (c, 1);
    }
  }
  return res;
}

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);

  size_t n, k;
  cin >> n >> k;
  string s;
  cin >> s;

  auto v = run_length_encoding (s);
  auto vn = v.size ();
  while (vn > 2 && k > 0)
  {
    vn -= 2;
    -- k;
  }
  if (vn == 2 && k > 0)
  {
    vn -= 1;
    -- k;
  }
  cout << n - vn << endl;

}


Measured memory_bytes: 2500
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-9;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct UnionFind{
    vector<int> par;
    vector<int> dep;
    
    UnionFind(int siz){
        par.assign(siz,0);
        dep.assign(siz,0);
        for(int i=0;i<siz;i++){
            par[i]=i;
        }
    };

    int find(int x){
        if(par[x]==x){
            return x;
        }else{
            return par[x]=find(par[x]);
        }
    }

    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return;
        }
        if(dep[x]<dep[y]){
            par[x]=y;
        }else{
            par[y]=x;
            if(dep[x]==dep[y]){
                dep[x]++;
            }
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};
vector<int> lang[100010];
int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++){
        int k;cin>>k;
        for(int j=0;j<k;j++){
            int l;cin>>l;
            lang[l].push_back(i);
        }
    }
    UnionFind uf(n);
    for(int i=1;i<=m;i++){
        for(int j=0;j<(int)lang[i].size()-1;j++){
            uf.unite(lang[i][j],lang[i][j+1]);
        }
    }
    int s=uf.find(0);
    for(int i=1;i<n;i++){
        if(uf.find(i)!=s){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 4736
#!/usr/bin/env python3
import sys
import numpy as np

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))


Measured memory_bytes: 29640
import java.util.*;
import java.io.*;

class Main{
    static int[][] xy;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        xy=new int[n][2];
        for(int i=0;i<n;i++){
            xy[i][0]=sc.nextInt();
            xy[i][1]=sc.nextInt();
        }
        sc.close();
        double ave=0;
        for(int i=0;i<n;i++){
            HashSet<Integer> toVisit=new HashSet<>();
            for(int j=0;j<n;j++) if(i!=j) toVisit.add(j);
            ave+=visit(i, toVisit);
        }
        ave/=n;
        System.out.println(ave);
    }
    public static double visit(int now, HashSet<Integer> toVisit){
        if(toVisit.size()==0) return (double) 0;
        double ret=0;
        HashSet<Integer> copy=(HashSet<Integer>) toVisit.clone();
        for(int v:copy){
            toVisit.remove(v);
            ret+=Math.sqrt((double) ((xy[now][0]-xy[v][0])*(xy[now][0]-xy[v][0])+(xy[now][1]-xy[v][1])*(xy[now][1]-xy[v][1])));
            ret+=visit(v, toVisit);
            toVisit.add(v);
        }
        ret/=copy.size();
        return ret;
    }
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    map<ll, ll> mp;
    REP(i, N) mp[A[i]]++;

    vector<ll> cnt;
    for(auto x: mp){
    	cnt.push_back(x.second);
    }

    ll M = cnt.size();
    sort(cnt.begin(), cnt.end());

    vector<ll> S(M+1, 0);
    REP(i, M) S[i+1] += S[i] + cnt[i];
    //cout << cnt << endl;
    for(int K=1;K<=N;K++){
    	ll lb = -1, ub = N+1;
    	while(ub-lb>1){
    		ll md = (lb+ub)/2;
    		ll pos = upper_bound(cnt.begin(), cnt.end(), md) - cnt.begin();
    		ll res = 0;
	    	res += S[pos];
	    	res += md*(M - pos);

	    	if(res>=md*K) lb = md;
	    	else ub = md;
    	}
    	cout << lb << endl;
    }
    return 0;
}

Measured memory_bytes: 25836
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;


int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    int T;
    //cin >> T;
    T = 1;
    for (int cs = 1; cs <= T; cs++) {
        int n, m;
        cin >> n >> m;
        vector<int> graph[3*n + 5];
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            graph[u].push_back(v + n);
            graph[u + n].push_back(v + 2 * n);
            graph[u + 2 * n].push_back(v);
        }

        int s, t;
        cin >> s >> t;
        s--;
        t--;
        queue<int> Q;
        int dist[3 * n + 5];
        for (int i = 0; i < 3 * n; i++) dist[i] = -1;
        dist[s] = 0;
        Q.push(s);
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i = 0; i < (int)graph[u].size(); i++) {
                int v = graph[u][i];
                //cerr << u << " "<< v << endl;
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    Q.push(v);
                }
            }
        }
        if (dist[t] == -1) {
            cout << -1 << "\n";
            return 0;
        }
       // cerr << dist[t] << endl;
        cout << dist[t] / 3 << endl;
    }

//double end_time = clock();
//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    return 0;
}

Measured memory_bytes: 17792
fun main(args: Array<String>) {
    val s = readLine()!!.toInt()

    val bucket = Array(1000001) { i -> i * 0 }
    bucket[s] = 1


    var prev = s

    for (i in 1 until bucket.size) {
        if (prev % 2 == 0) {
            if (bucket[prev / 2] == 1) {
                print(i + 1)
                return
            } else {
                bucket[prev / 2] = 1
                prev = prev / 2
            }

        } else {
            if (bucket[3 * prev + 1] == 1) {
                print(i + 1)
                return
            } else {
                bucket[3 * prev + 1] = 1
                prev = 3 * prev + 1
            }
        }
    }
}

Measured memory_bytes: 34740
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n;
	cin>>n;
	n*=(n-1);
	n/=2;
	cout<<n;
	return 0;
}

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

int main(){

 int a,aa,aaa,aaaa,b,bb,bbb,bbbb,s,t;
 cin>>a>>aa>>aaa>>aaaa>>b>>bb>>bbb>>bbbb;

 s=a+aa+aaa+aaaa;
 t=b+bb+bbb+bbbb;
 
 if(s>=t)
  cout<<s<<'\n';
 else
  cout<<t<<'\n';

return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// #define ll long long 
#define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9+7;
int mpow(int a,int b,int p=MOD){a=a%p;int res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
const int N=2*1e5+2;
int check(int val[],int m,int p)
{
	if(m==0)
	{
		if(p==2)
		{
			return val[2];
		}
		else return 0;
	}
	else if(m==1)
	{
		if(p==0)
		{
			return val[0];
		}
		else return 0;
	}
	else{
		if(p==1)
		{
			return val[1];
		}
		else return 0;
	}
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin>>n>>m;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	int pref[n];
	for(int i=0;i<n;i++)
	{
		if(i) pref[i]=pref[i-1]+a[i];
		else pref[i]=a[i];
	}	
	// vector<int> oo;
	// for(int i=0;i<n;i++)
	// {
	// 	for(int j=0;j<n;j++) oo.pb(a[i]+a[j]);
	// }
	// sort(all(oo));
	// reverse(all(oo));
	// for(auto x:oo) cout<<x<<" ";
	// cout<<"\n";
	int l=0,r=2*1e5+2;
	int left=m;
	// x+y >=mid;
	// y>=mid-x
	int ans=0;
	int cntt=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int cnt=0;
		int ans1=0;
		for(int i=0;i<n;i++)
		{
			int j=a+n-upper_bound(a,a+n,mid-a[i]-1);
			int ooo=upper_bound(a,a+n,mid-a[i]-1)-a;
			// if(ooo==n) continue;
			// if(mid==114)
			// {
			// 	cout<<a[i]<<" "<<ooo<<" "<<pref[n-1]-(ooo?pref[ooo-1]:0)<<"\n";
			// }
			ans1+=(pref[n-1]-(ooo?pref[ooo-1]:0))+j*a[i];
			cnt+=j; 
		}
		// if(mid==67)
		// {
		// 	cout<<ans1<<"\n";
		// }
		if(cnt<=m)
		{
			ans=ans1;
			cntt=cnt;
			// cout<<mid<<" "<<ans1<<"\n";
			r=mid-1;
		}
		else l=mid+1;
	}
	int ans11=0;
	int cntt1=0;
	l=0,r=2*1e5+2;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int cnt=0;
		int ans1=0;
		for(int i=0;i<n;i++)
		{
			int j=a+n-upper_bound(a,a+n,mid-a[i]-1);
			int ooo=upper_bound(a,a+n,mid-a[i]-1)-a;
			// if(ooo==n) continue;
			// if(mid==114)
			// {
			// 	cout<<a[i]<<" "<<ooo<<" "<<pref[n-1]-(ooo?pref[ooo-1]:0)<<"\n";
			// }
			ans1+=(pref[n-1]-(ooo?pref[ooo-1]:0))+j*a[i];
			cnt+=j; 
		}
		// if(mid==67)
		// {
		// 	cout<<ans1<<"\n";
		// }
		if(cnt>m)
		{
			ans11=ans1;
			cntt1=cnt;
			// cout<<mid<<" "<<ans1<<"\n";
			l=mid+1;
		}
		else r=mid-1;
	}
	if(cntt==m)
	{
		cout<<ans;
		return 0;
	}
	// cout<<ans;
	int lef=cntt1-cntt;
	int summ=ans11-ans;
	// cout<<cntt1<<" ";
	// cout<<summ/lef<<" ";
	cout<<ans+((summ)/(lef))*(m-cntt);
	// cout<<ans<<" "<<ans11<<"\n";
	// int 
	// int anss=0;
	// for(int i=0;i<n;i++)
	// {
	// 	int j=a+n-upper_bound(a,a+n,mid-a[i]-1);
	// 	cnt+=j; 
	// }
	// cout<<ans;
}  
// I never lose. I either win or I learn

Measured memory_bytes: 1792
n,k,*v=map(int,open(0).read().split())
m=0
r=range
for i in r(n+1):
 for j in r(min(k,n)-i+1):
  t=sorted(v[:i]+v[-j:]*(j>0))
  while t and(k-i-j)*t[0]<0:t.pop(0);j+=1
  m=max(m,sum(t))
print(m)

Measured memory_bytes: 3060
#include<stdio.h>
int main(void)
{
    unsigned long long int pre_a=0,pre_b=0;
    unsigned long long int a,b;
    int n;
    unsigned long long int ratio_a,ratio_b;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%llu %llu",&a,&b);
        if(pre_a%a!=0){
            ratio_a=pre_a/a+1;
        }
        else{
            ratio_a=pre_a/a;
        }
        if(pre_b%b!=0){
            ratio_b=pre_b/b+1;
        }
        else{
            ratio_b=pre_b/b;
        }
        if(a<pre_a || b<pre_b){
            if(ratio_a>ratio_b){
                a*=ratio_a;
                b*=ratio_a;
            }
            else{
                a*=ratio_b;
                b*=ratio_b;
            }
        }
        pre_a=a;
        pre_b=b;
    }
    printf("%llu\n",a+b);
    return 0;
}


Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String str[] = br.readLine().split(" ");

		double v[] = new double[n];
		ArrayList<ArrayList<Double>> list = new ArrayList<ArrayList<Double>>();
		for (int i = 0; i < n; i++) {
			v[i] = Double.parseDouble(str[i]);
		}

		Arrays.sort(v);
		double d = v[0];
		for (int i = 0; i < n; i++) {
			d = (d + v[i]) / 2;
		}
		System.out.println(d);
	}

	static double get(double d[]) {
		if (d.length == 2)
			return (d[0] + d[1]) / 2;
		double dou1[] = new double[d.length / 2];
		double dou2[];
		if (d.length % 3 == 0)
			dou2 = new double[(d.length / 2)];
		else {
			dou2 = new double[(d.length / 2) + 1];
		}
		for (int i = 0; i < d.length / 2; i++) {
			dou1[i] = d[i];
			if (d.length % 3 == 0)
				dou2[i] = d[i + (d.length / 2)];
			else {
				dou2[i] = d[i + ((d.length / 2) + 1)];
			}

		}
		return (get(dou1) + get(dou2)) / 2;
	}
}

Measured memory_bytes: 22356
a,b = map(int,input().split())

c = []

for i in range(a):
	c.append(int(input()))

c.sort()
p = c[0]
for i in range(a):
	c[i] -= p

k = c[b-1] - c[0]

for i in range(a-b+1):
	if k >= c[i+b-1] - c[i]:
		k = c[i+b-1] - c[i]

print(k)

Measured memory_bytes: 51416
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

const ll INF=1e18;

struct E{
	int dest;
	int price,time;
	
	E(int a,int b,int c){
		dest=a,price=b,time=c;
	}
};

int n,m,s;
vector<E> al[55];
ii changer[55];

ll w[55][2505];
priority_queue<iii,vector<iii>,greater<iii> > pq;

ll ans[55];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>s;
	
	s=min(s,2504); //dont want overflow
	
	int a,b,c,d;
	while (m--){
		cin>>a>>b>>c>>d;
		al[a].push_back(E(b,c,d));
		al[b].push_back(E(a,c,d));
	}
	
	rep(x,1,n+1) cin>>changer[x].fi>>changer[x].se;
	
	memset(w,63,sizeof(w));
	memset(ans,-1,sizeof(ans));
	
	w[1][s]=0;
	pq.push(iii(w[1][s],ii(1,s)));
	
	ll time;
	ll node,amt;
	while (!pq.empty()){
		time=pq.top().fi;
		node=pq.top().se.fi;
		amt=pq.top().se.se;
		pq.pop();
		
		if (time>w[node][amt]) continue;
		
		//cout<<time<<" "<<node<<" "<<amt<<endl;
		
		if (ans[node]==-1) ans[node]=time;
		
		//try to increase cash
		if (w[node][min(amt+changer[node].fi,2504LL)]>w[node][amt]+changer[node].se){
			w[node][min(amt+changer[node].fi,2504LL)]=w[node][amt]+changer[node].se;
			pq.push(iii(w[node][min(amt+changer[node].fi,2504LL)],ii(node,min(amt+changer[node].fi,2504LL))));
		}
		
		for (auto &it:al[node]){
			if (amt-it.price<0) continue;
			if (w[it.dest][amt-it.price]>w[node][amt]+it.time){
				w[it.dest][amt-it.price]=w[node][amt]+it.time;
				pq.push(iii(w[it.dest][amt-it.price],ii(it.dest,amt-it.price)));
			}
		}
	}
	
	rep(x,2,n+1) cout<<ans[x]<<endl;
}


Measured memory_bytes: 7448
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int a, b, c; cin >> a >> b >> c;
    swap(a, b);
    swap(a, c);
    cout << a << " " << b << " " << c << endl;
    return 0;
}

Measured memory_bytes: 256
(defun to-yen (amount currency)
  (cond
    ((eql currency 'JPY) amount)
    ((eql currency 'BTC) (* amount 380000.0))
    (t (error "unknown currency"))))

(let* ((n (read))
       (table (loop for i below n collect (list (read) (read)))))
  (format t "~A~%"
          (loop for row in table
             sum (to-yen (car row) (second row)))))


Measured memory_bytes: 5216
#include<stdio.h>

int main(){
	long a, b, i, c=0;
	scanf("%ld%ld", &a, &b);
	if(( a <= 0 && b >= 0 ) || (a >= 0 && b <=0) ) printf("Zero\n");
	else if( a > 0 && b >0) printf("Positive\n");
	else if((b - a)%2 == 0) printf("Negative\n");
	else printf("Positive\n");

	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int mod = 1e9 + 7;

inline int add(int a, int b) {
  return a+b >= mod ? a+b-mod : a+b;
}

inline int sub(int a, int b) {
  return a >= b ? a-b : a-b+mod;
}

inline int mul(int a, int b) {
  return llint(a)*b % mod;
}

const int MAX = 404;

int N;
int A[MAX], B[MAX], invA[MAX], invB[MAX];
int f[MAX][MAX][MAX / 3][3];

int solve(int a, int b, int de, int k) {
  int& ref = f[a][b][de][k];

  if (ref != -1) return ref;

  if (k == 2) {
    // svi moraju jest ili je gotovo
    if (a < N && b < N) {
      return ref = solve(a + 1, b + 1, de + 1, 0);
    }
    if (a == N && b == N && de == 0) return ref = 1;
    return ref = 0;
  }

  if (k == 0) { // prvi
    if (a < N && invB[A[a]] < b) return ref = solve(a + 1, b, de, 0);

    ref = 0;
    if (a < N && de > 0) ref = add(ref, mul(de, solve(a + 1, b, de - 1, 0)));
    ref = add(ref, solve(a, b, de, 1));
    return ref;
  }


  if (k == 1) { // drugi
    if (b < N && invA[B[b]] < a) return ref = solve(a, b + 1, de, 1);

    ref = 0;
    if (b < N && de > 0 && (a == N || B[b] != A[a])) ref = add(ref, mul(de, solve(a, b + 1, de - 1, 1)));
    if (a == N || b == N || A[a] != B[b]) ref = add(ref, solve(a, b, de, 2));
    return ref;
  }

  return ref;
}

int main(void) {
  memset(f, -1, sizeof(f));
  
  scanf("%d", &N);
  REP(i, N) scanf("%d", &A[i]), --A[i];
  REP(i, N) scanf("%d", &B[i]), --B[i];
  
  REP(i, N) invA[A[i]] = i;
  REP(i, N) invB[B[i]] = i;
    
  int ans = solve(0, 0, 0, 0);
  for (int i = 3; i <= N; i += 3) ans = mul(ans, (i-2) * (i-1));
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256640
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}


int main() {

    int N;
    cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    bitset<64> B(0);
    long long sum = 0;
    long long ans = 0;

    int right = 0;
    for (int left = 0; left < N; left++) {
        if (right <= left) right = left;
        while (right < N && ((B ^ bitset<64>(A[right])) == (sum + A[right]))) {
            sum += A[right];
            B ^= bitset<64>(A[right]);
            right++;
        }
        ans += (right - left);
        sum -= A[left];
        B ^= A[left];
    }

    cout << ans << endl;

    return 0;
}














































Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> p(n);
	rep(i, n) cin >> p[i];
	sort(all(p));
	int ans = 0;
	rep(i, k) ans += p[i];
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n; cin >> n;
  int t = 0;
  bool ok = true;
  while (n--) {
    string s; cin >> s;
    if (s == "A") {
      ++t;
    } else {
      --t;
    }
    if (t < 0) ok = false;
  }
  if (t) ok = false;
  cout << (ok ? "YES" : "NO") << '\n';
}


Measured memory_bytes: 3224
N, Y = map(int, input().split())
a,b,c = -1,-1,-1
flag= False
Y=Y/1000

for i in range(N+1):
    for j in range(N-i+1):
        sum = 9*i + 4*j + N
        if sum==Y:
            a,b,c=i,j,N-i-j
            flag=True
            break
    if flag == True:
        break

print(a,b,c)




Measured memory_bytes: 3188
def main():
    s = input()
    p = input()
    answer = 'Yes' if match(s, p) else 'No'
    print(answer)

def match(s, p):
    for i in range(0, len(s)):
        for j in range(0, len(p)):
            if s[(i + j) % len(s)] != p[j]:
                break
        else:
            return True
    return False

if __name__ == '__main__':
    main()



Measured memory_bytes: 5564
import bisect


class BTreeNode:
    def __init__(self):
        self.key = []
        self.child = []


class BTree:
    def __init__(self):
        self.root = BTreeNode()

    def search_higher(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_right(ptr.key, key)
            if i != len(ptr.key):
                ret = ptr.key[i]
            ptr = ptr.child[i]
        i = bisect.bisect_right(ptr.key, key)
        if i != len(ptr.key):
            ret = ptr.key[i]
        return ret

    def search_lower(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_left(ptr.key, key)
            if i != 0:
                ret = ptr.key[i - 1]
            ptr = ptr.child[i]
        i = bisect.bisect_left(ptr.key, key)
        if i != 0:
            ret = ptr.key[i - 1]
        return ret

    def insert(self, key):
        def insert_rec(ptr):
            b_size = 10
            if not ptr.child:
                bisect.insort(ptr.key, key)
                if len(ptr.key) == b_size * 2 - 1:
                        ret = BTreeNode()
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            else:
                i = bisect.bisect(ptr.key, key)
                temp = insert_rec(ptr.child[i])
                if temp is not None:
                    ptr.key.insert(i, temp.key.pop(-1))
                    ptr.child.insert(i, temp)
                    if len(ptr.child) == b_size * 2:
                        ret = BTreeNode()
                        ret.child = ptr.child[:b_size]
                        ptr.child = ptr.child[b_size:]
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            return None
        temp = insert_rec(self.root)
        if temp is not None:
            root = BTreeNode()
            root.key = [temp.key.pop(-1)]
            root.child = [temp, self.root]
            self.root = root

    def dump(self):
        def dump_rec(ptr, dep):
            for _ in range(0, dep):
                print("  ", end="")
            print(ptr.key)
            for c in ptr.child:
                dump_rec(c, dep + 1)
        dump_rec(self.root, 0)
        print("")


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = BTree()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()


Measured memory_bytes: 16208
//y15-3
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while (true)

int main(){
    int D,L;
    cin >> D >> L;
    cout << D/L + D%L << endl;
    return 0;
}


Measured memory_bytes: 3100
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//Computation of Minimum Length of Pipeline
public class Main{

	class E implements Comparable<E>{
		int s, t, d;
		public E(int s, int t, int d) {
			this.s = s;
			this.t = t;
			this.d = d;
		}
		public int compareTo(E o) {
			return d-o.d;
		}
	}

	class UnionFind {
		final int[] tree;
		int num;
		public UnionFind(int n) {
			this.tree = new int[n];
			Arrays.fill(tree, -1);
			num=n;
		}
		void union(int x, int y) {
			x = root(x);
			y = root(y);
			if(x != y) {
				if(tree[x] < tree[y]) {
					x ^= y; y ^= x; x^= y;
				}
				tree[x] += tree[y];
				tree[y] = x;
				num--;
			}
		}
		boolean find(int x, int y) {
			return root(x) == root(y);
		}
		int root(int x) {
			return tree[x] < 0 ? x : (tree[x] = root(tree[x]));
		}
		int size(int x) {
			return -tree[root(x)];
		}
		int getNum() {
			return num;
		}
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int s = sc.nextInt(), n = sc.nextInt();
			if((s|n)==0)break;
			PriorityQueue<E> q = new PriorityQueue<E>();
			for(int i=0;i<s;i++)for(int j=0;j<n;j++){
				int x = sc.nextInt();
				if(x==0)continue;
				q.add(new E(i, s+j, x));
			}
			for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
				int x = sc.nextInt();
				if(x==0)continue;
				q.add(new E(s+i, s+j, x));
			}
			UnionFind u = new UnionFind(s+n);
			boolean[] ok = new boolean[s+n];
			for(int i=0;i<s;i++)ok[i] = true;
			int res = 0, c = s;
			while(c<s+n){
				E e = q.poll();
				if(ok[e.s]&&ok[e.t])continue;
				if(!u.find(e.s, e.t)){
					res += e.d;
					u.union(e.s, e.t);
					if(ok[e.s]){
						for(int i=s;i<s+n;i++){
							if(!ok[i]&&u.find(e.s, i)){
								ok[i] = true; c++;
							}
						}
					}
					else if(ok[e.t]){
						for(int i=s;i<s+n;i++){
							if(!ok[i]&&u.find(e.t, i)){
								ok[i] = true; c++;
							}
						}
					}
				}
			}
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int M = in.nextInt();
    
    int[] nums = new int[N];
    
    for (int i = 0; i < N; i++) {
      nums[i] = in.nextInt();
    }
    
    int[] heights = new int[N];
    for (int i = 0; i < M; i++) {
      int A = in.nextInt() - 1;
      int B = in.nextInt() - 1;

      heights[A] = Math.max(heights[A], nums[B]);
      heights[B] = Math.max(heights[B], nums[A]);
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
      if (nums[i] > heights[i]) ans++;
    }
    
    System.out.println(ans);
  }
}


Measured memory_bytes: 59504
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>

typedef long long ll;

using namespace std;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}
int main() {
    int A, B, T; cin >> A >> B >> T;
    cout << ((T/A) * B) << endl;
}


Measured memory_bytes: 256
// IlyM

#include <bits/stdc++.h>
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define tra(a,b) for (auto a:b) 
#define fo(a,b,c) for (int a=b;a<=c;a++) 
#define ms(a,b) memset(a,b,sizeof(a)) 
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())
#define bit(i,j) (i&(1<<j))

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef pair<int,ii> iii;

const int N=2e5+5,mod=998244353;
ll n,r;
int main()
{
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	cin>>n>>r;
	if (n>=10) cout<<r;
	else cout<<r+100*(10-n);
	return 0;
}


Measured memory_bytes: 256
A,B = map(int,input().split())

S = input()

for i in range (A):
  if S[i] == '-':
    print("No")
    exit()
  else:
      continue

for j in range(A,A+B+1):
  if j == A and S[j] != '-':
    print("No")
    exit()
  elif j>A and S[j] == '-':
    print("No")
    exit()
  else:
      continue
print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n);(i)>=0;(i)--)
typedef long long lint;

int main(){
    vector <pair<lint,lint>> A;
    vector <lint> B;
    lint d,f,g,h,count=0;
    lint N,H;
    cin >>N>>H;
    rep(i,N){
        lint s,v;
        cin>>s>>v;
       A.push_back(make_pair(s,v));
    }
    sort(A.begin(),A.end(),greater<pair<lint,lint>>());
    rep(i,N){
        lint s,v;
        tie(s,v)=A[i];
        if(i==0){
            d=s;
            f=v;
        }else B.push_back(v);
    }
    sort(B.begin(),B.end(),greater<lint>());
    lint i=0;
    while(1){
        if(H<=f){
            count++;
            cout<<count<<endl;
            return 0;
        }
        if(i<N-1&&B[i]>d){H-=B[i];
        count++;
        i++;
        }else {
            H-=d;
            count++;
        }
        if(H<=0){
            cout<< count<<endl;
            return 0;
        }
    }

 }



  


Measured memory_bytes: 3568
# union find, bfs

import sys
from collections import deque
si = sys.stdin.readline


def main():
    [n, m] = [int(e) for e in si().split()]
    if not m:
        print(1)
        return

    visited = [False]*(n+1)
    fm = [set() for _ in range(n+1)]
    mx, comp = 0, 0

    while m:
        m -= 1
        [a, b] = [int(e) for e in si().split()]
        fm[a].add(b)
        fm[b].add(a)

    for i in range(1, n+1):
        if visited[i]:
            continue
        visited[i] = True
        comp += 1
        q = deque()
        q.append(i)
        cnt = 1
        while q:
            curr = q.popleft()
            for e in fm[curr]:
                if not visited[e]:
                    visited[e] = True
                    q.append(e)
                    cnt += 1
        mx = max(mx, cnt)
    print(mx)

if __name__ == '__main__':
    main()


Measured memory_bytes: 72888
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def main():
    X = int(input())
    for i in range(pow(10,5)):
        num = X + i
        if(is_prime(num)):
            print(num)
            break


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int a, b;
	cin >> a >> b;
	cout << max(0, a - 2 * b) << endl;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N, M, K;
long long int num[20001];
long long int dp[20001];

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)cin >> num[i];
	for (int i = 1; i <= N; i++)dp[i] = LLONG_MAX;
	for (int i = 0; i < N; i++) {
		long long int mi = LLONG_MAX;
		long long int MA = LLONG_MIN;
		for (int j = i + 1; j <= min(i + M, N); j++) {
			mi = min(mi, num[j]);
			MA = max(MA, num[j]);
			dp[j] = min(dp[j], dp[i] + K + (j - i)*(MA - mi));
		}
	}
	cout << dp[N] << endl;
	return 0;
}

Measured memory_bytes: 3504
#include <bits/stdc++.h>
    
using namespace std;
typedef long long ll;
    
int main()
{
    ll N, A, B;
    cin >> N >> A >> B;

    ll result = N / (A + B) * A;
    ll rem = N % (A + B);
    result += min(rem, A);

    cout << result;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
using namespace std;


int main(){
    long long int n,m,x,y,z;
    cin>>n>>m;
    vector<tuple<long long int,long long int,long long int>> w(n);
    vector<long long int> v(n);
    for(long long int i=0;i<n;i++) {
        cin >> x >> y >> z;
        w[i] = make_tuple(x, y, z);
    }
    long long int result = 0,restmp;
    for (int j = 0; j < 8; j++){
        restmp = 0;
        for(long long int i=0;i<n;i++){
            v[i] = (1 + (j & 1) * (-2)) * get<0>(w[i]) + (1 + (j & 2) * (-1)) * get<1>(w[i]) + (1 + ((j & 4)/2) * (-1)) * get<2>(w[i]);
            
        }
        sort(v.begin(), v.end(), greater<long long int>());
    
        for(long long int i=0;i<m;i++){

            restmp+=v[i];
       //     cout<<v[i]<<" " << restmp << endl;
    
        }
        result = max(result, restmp);
    }
    
    cout<<result<<endl;
}


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

using namespace std;
typedef long long ll ;
#define forl(i,n) for(int i=0 ; i<n ; i++)

vector<int> dp ;
vector<int> h ;
int n,k ;

int solve(int x)
{
	if(dp[x]!=-1)
		return dp[x] ;
	dp[x]=1e9 ;
	for(int i=1 ; i<=k ; i++)
	{
		if(x-i<0) break ;
		dp[x]=min(dp[x] ,abs(h[x]-h[x-i])+solve(x-i)) ;
	}
	return dp[x] ;
}

int main()
{
	int T=1;
	// cin >> T ;

	while(T--)
	{
		cin>>n>>k ;
		h.resize(n) ;
		for(int i=0 ; i<n ; i++)
			cin>>h[i] ;

		dp.resize(n) ;
		for(int i=0 ; i<n ; i++)
			dp[i]=-1 ;
		dp[0]=0 ;
		dp[n-1]=solve(n-1) ;
		cout<<dp[n-1]<<endl ;
	}
	return 0;
}

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

long long N;
long long a[200005];
set<long long> ans;

int main(){
	cin >> N;
	for(long long i = 1; i <= N; i++){
		cin >> a[i];
	}

	for(long long i = N; i > 0; i--){
		long long num = i;
		long long sumi = 0;

		for(long long idx = num; idx <= N; idx += num){
			if(ans.count(idx)){
				sumi++;
			}
		}
		if(sumi % 2 != a[i]){
			ans.insert(num);
		}
	}
	cout << ans.size() << endl;
	for(auto num: ans){
		cout << num << endl;
	}
}



Measured memory_bytes: 8576
#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
const int N=1e3+10;
const int INF=1e9+10;
int n,dp[N][N],pos[N],top;
vector<pair<int,pi>>graph[N];
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
    return ;
}
int f(int a,int b){
    if(pos[a]==n&&pos[b]==n)return 0;
    if(pos[a]>pos[b])swap(a,b);
    if(dp[a][b]>=0)return dp[a][b];
    int ans=INF;
    if(a==b)for(pair<int,pi> i:graph[a])for(pair<int,pi> j:graph[a]){
        if(i==j)ans=min(ans,i.S.F+i.S.S+f(i.F,i.F));
        else ans=min(ans,i.S.F+j.S.F+f(i.F,j.F));
    }
    else for(pair<int,pi> i:graph[a])ans=min(ans,i.S.F+f(i.F,b));
    return dp[a][b]=ans;
}
void dfs(int now){
    for(pair<int,pi> i:graph[now])if(pos[i.F]<0)dfs(i.F);
    pos[now]=top--;
    return ;
}
int main(){
    int m,l,r,a,b;
    scanf("%d%d",&n,&m);
    top=n;
    for(int i=1;i<=n;i++)pos[i]=-1;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=-1;
    while(m--){
        scanf("%d%d%d%d",&l,&r,&a,&b);
        graph[l].PB({r,{a,b}});
    }
    dfs(1);
    printf("%d\n",f(1,1));
}


Measured memory_bytes: 6836
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define repa(X,A,Y) for (int (X) = A;(X) <= (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int N;
ll a[100010];

int main() {
  std::ios::sync_with_stdio(false);std::cin.tie(0);

  cin >> N;
  rep(i, N) cin >> a[i];
  sort(a, a+N);

  vector<ll> ans;
  ll ma = 0;
  if (N%2 == 0) {
    ans.push_back(a[N/2-1]);
    for (int i = 0; (i+1)*2 <= N-2; ++i) {
      ans.push_back(a[N-i-1]);
      ans.push_back(a[i]);
    }
    ans.push_back(a[N/2]);
    ll sum = 0;
    for (int i = 1; i < ans.size(); ++i) sum += abs(ans[i-1]-ans[i]);
    ma = max(ma, sum);

    ans.resize(0);
    ans.push_back(a[N/2]);
    for (int i = 0; (i+1)*2 <= N-2; ++i) {
      ans.push_back(a[i]);
      ans.push_back(a[N-i-1]);
    }
    ans.push_back(a[N/2-1]);
    sum = 0;
    for (int i = 1; i < ans.size(); ++i) sum += abs(ans[i-1]-ans[i]);
    ma = max(ma, sum);
  } else {
    ans.push_back(a[N/2]);
    for (int i = 0; (i+1)*2 <= N-1; ++i) {
      ans.push_back(a[N-i-1]);
      ans.push_back(a[i]);
    }
    ll sum = 0;
    for (int i = 1; i < ans.size(); ++i) sum += abs(ans[i-1]-ans[i]);
    ma = max(ma, sum);

    ans.resize(0);
    ans.push_back(a[N/2]);
    for (int i = 0; (i+1)*2 <= N-1; ++i) {
      ans.push_back(a[i]);
      ans.push_back(a[N-i-1]);
    }
    sum = 0;
    for (int i = 1; i < ans.size(); ++i) sum += abs(ans[i-1]-ans[i]);
    ma = max(ma, sum);
  }

  // rep(i, ans.size()) cout << "ans[" << i << "] = " << ans[i] << endl;


  cout << ma << endl;
  return 0;
}


Measured memory_bytes: 2168
#include <iostream>
#include <vector>

using namespace std;
const int INF = 1001001001;

int prim(vector< vector<int> > cost)
{
    vector<int> V(1, 0), T(cost.size());
    for(int i=0;i<cost.size();++i) T[i] = i;
    T[0] = INF;
    int mini, minj, min_cost, ans=0;
    while(V.size() < cost.size())
    {
        min_cost = INF;
        for(int i : V){
            for(int j : T)
            {
                if(j == INF) continue;
                if(cost[i][j] < min_cost)
                {
                    mini = i;
                    minj = j;
                    min_cost = cost[i][j];
                }
            }
        }
        V.push_back(minj);
        T[minj] = INF;
        cost[mini][minj] = cost[minj][mini] = INF;
        ans += min_cost;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int> > cost(n, vector<int>(n));

    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            cin >> cost[i][j];
            if(cost[i][j] == -1) cost[i][j] = INF;
        }
    }

    cout << prim(cost) << endl;
}



Measured memory_bytes: 3164
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019
print(ans)

Measured memory_bytes: 9332
#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 1e5+5;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

int s[maxn];
vector<ll> pre[maxn],suf[maxn];
int main()
{
    fastio();
    int n; cin>>n;
    rep(i,0,n-1) cin>>s[i];
    rep(i,1,n-1){
        for(int j=0;j<n;j+=i){
            if(pre[i].size() == 0) pre[i].pb(s[j]);
            else pre[i].pb(pre[i].back() + s[j]);
        }
        for(int j=n-1;j>=0;j-=i){
            if(suf[i].size() == 0) suf[i].pb(s[j]);
            else suf[i].pb(suf[i].back() + s[j]);
        }
    }
    ll ans = 0;
    rep(k,1,n-1){
        for(int d=1;d*k<n-1;d++){
            int A = n-1-k*d;
            int B = A-d;
            if(B <= 0) break;
            if(A%d==0 && A/d<=k) continue;
            ans = max(ans,pre[d][k] + suf[d][k]);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 35708
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    cin >> s;
    int a = stoi(s.substr(0, 2));
    int b = stoi(s.substr(2, 2));
    
    bool oka = (a >= 1 && a <= 12);
    bool okb = (b >= 1 && b <= 12);
    if (oka && okb) cout << "AMBIGUOUS\n";
    else if (oka) cout << "MMYY\n";
    else if (okb) cout << "YYMM\n";
    else cout << "NA\n";
}


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

using namespace std;

#define ll long long
#define ld long double

int main()
{
    ll n;
    cin >> n;
    ll res = 0;
    ll minTillNow = LONG_LONG_MAX;
    while(n--)
    {
        ll a;
        cin >> a;
        if(a < minTillNow)
        {
            minTillNow = a;
            res++;
        }
    }

    cout << res << endl;

    return 0;
}



Measured memory_bytes: 256
N = int(input())
ans = 10**5
for a in range(1, N//2 + 1):
    suma = 0
    sumb = 0
    b = N - a
    while a > 0:
        suma += a % 10
        a //= 10
    while b > 0:
        sumb += b % 10
        b //= 10
    if (suma + sumb) < ans:
        ans = suma + sumb
print(ans)

Measured memory_bytes: 3064