akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>

using namespace std;


int main()
{
    int n;
    vector<int> l;
    
    cin >> n;
    for (int i = 0;i < n;i++){
        int k;
        cin >> k;
        l.push_back(k);
    }
    
    sort(l.begin(),l.end());
    
    int ans = 0;
    
    for (int i = n-1;i >= 2;i--){
        for (int j = i-1;j >= 1;j--){
            auto k = upper_bound(l.begin(),l.begin()+j-1,l[i]-l[j]);
            if (l[i] < l[j] + *k){
                ans += j-(k-l.begin());
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
a = [int(i) for i in input().split()]

len_f = sum(a)
sum_a = 0
min = 2020202021

for i in range(n):
    sum_a += a[i]
    len_f -= a[i]
    if min > abs(sum_a - len_f):
        min = abs(sum_a - len_f)

print(min)

Measured memory_bytes: 26060
N=int(input())
A=list(map(int,input().split()))
n=1
mode=0
for i in range(1,N):
	if mode==0:
		mode = A[i]-A[i-1]
	else:
		if mode * (A[i]-A[i-1]) >=0:
			continue
		else:
			n+=1
			mode=0
print(n)


Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool isPal(int i, int j, string &s)
{
    while (i < j)
    {
        if (s[i] != s[j])
        {
            return false;
        }
        i++;
        j--;
    }
    return true;
}
int main()
{
    string s;
    cin >> s;
    auto len = s.size() / 2;
    if (isPal(0, len - 1, s) && isPal(len + 1, s.size() - 1, s) && isPal(0, s.size() - 1, s))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
int main(){
	int m,f,r;
	while (1){
		scanf("%d %d %d",&m,&f,&r);
		if (m+f+r==-3) break;
		if (m==-1 || f==-1) printf("F\n");
		else if (m+f>=80) printf("A\n");
		else if (m+f>=65) printf("B\n");
		else if (m+f>=50) printf("C\n");
		else if (m+f>=30 && r>=50) printf("C\n");
		else if (m+f>=30) printf("D\n");
		else if (m+f<30)  printf("F\n");
	}
	return 0;	
}



Measured memory_bytes: 2040
n = int(input())
Adj = [[-1]*n for _ in range(n)]

for i in range(n):
    ai = int(input())
    for j in range(ai):
        xij,yij = map(int, input().split( ))
        xij -= 1
        Adj[i][xij] = yij###==ってなんぞ
#print(Adj)
ans = 0

bt = 1<<n

for b in range(bt):#全探索
    flag = True
    tmp = 0
    for i in range(n):
        for j in range(n):
            if Adj[i][j]>=0:
                if ((b>>i) &1) and not ((Adj[i][j]==0) ^ ((b>>j) &1)):#正直者の答えが矛盾,醜いがあとでビット演算子確認
                    flag = False
                    break
        if not flag:
            break
    if flag:
        for t in range(n):
            tmp += (b>>t)&1
            #print("test",b,tmp,flag)
    ans = max(tmp, ans)
    #print(b,ans)
print(ans)


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

#define int long long 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define INF 1e9+1
#define N 100005
int mx=0;

int n,m;
int dp[N];
unordered_map<int,vector<int> > adj;
bool vis[N];

int dfs(int u){
    if(dp[u]!=-1) return dp[u];
    dp[u]=0;
    //vis[u]=true;
    for(auto v:adj[u]){
        

            dp[u]=max(dp[u],1+dfs(v));
        }
        
    
    return dp[u];
}
int32_t main(){
    cin>>n>>m;
    
    while(m--){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        //adj[v].pb(u);
    }
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        if(dp[i]==-1) dfs(i);
    }
    /*for(auto i:adj){
        cout<<i.ff<<"->";
        for(auto j:i.ss) cout<<j<<" ";
        cout<<endl;
    }*/
    int mx=0;
    //cout<<endl;
    //for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
    //cout<<endl;
    //cout<<endl;
    for(int i=1;i<=n;i++) mx=max(mx,dp[i]);
    cout<<mx<<endl;
}

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

int main() {
    string S;
    int N;

    cin >> N;
    cin >> S;

    char result[S.length()];

    // cout << S.length() << endl;
    // 文字コード変換
    for (int i = 0; i < S.length(); ++i ){
        char h = S[i];
        int newN = (int(h) - 65 + N) % 26;
        S[i] = 'A' + newN;
    }

    cout << S << endl;
    

    return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    S = [input() for i in range(N)]

    C = [0,0,0,0]

    for i in range(len(S)):
        if S[i] == "AC":
            C[0] += 1
        if S[i] == "WA":
            C[1] += 1
        if S[i] == "TLE":
            C[2] += 1
        if S[i] == "RE":
            C[3] += 1

    print("AC x {}".format(C[0]))
    print("WA x {}".format(C[1]))
    print("TLE x {}".format(C[2]))
    print("RE x {}".format(C[3]))



if __name__ == '__main__':
    main()



Measured memory_bytes: 16092
#include <bits/stdc++.h>
using namespace std;
typedef std::pair<int, int> ipair;
#define int long long
#define pb push_back
#define ff first
#define INF INT_MAX
#define ss second
#define fr(i, j, a) for (int i = j; i < a; i++)
#define cnt_ones(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define sz size()
#define endl "\n"
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<ipair>
#define mod 1000000007
#define ar array
#define IOS                                                                    \
  std::ios::sync_with_stdio(false);                                            \
  cin.tie(NULL);                                                               \
  cout.tie(NULL);

void init() {
  int n, m;
  cin >> n >> m;
  int lm=INT_MIN,rm=INT_MAX;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin>>l>>r;
    lm=max(lm,l);
    rm=min(rm,r);
  }
  if(rm-lm>=0) cout<<rm-lm+1<<endl;
  else cout<<0<<endl;
}
int32_t main() {
  IOS;
  init();
  return 0;
}


Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vs = vector<string>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vvp = vector<vector<pair<int,int>>>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N,u,v;
    cin >> N >> u >> v;
    u--,v--;
    
    vvi G(N);
    rep(i,N-1){
        int a,b;
        cin >> a >> b;
        a--,b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    vi T(N,-1),A(N,-1);
    
    queue<int> tt,aa;
    tt.push(u);
    T[u] = 0;
    aa.push(v);
    A[v] = 0;
    
    while (!tt.empty()) {
        int a = tt.front();
        tt.pop();
        for (int p : G[a]) {
            if(T[p] >= 0) continue;
            T[p] = T[a]+1;
            tt.push(p);
        }
    }
    while (!aa.empty()) {
        int a = aa.front();
        aa.pop();
        for (int p : G[a]) {
            if(A[p] >= 0) continue;
            A[p] = A[a]+1;
            aa.push(p);
        }
    }

    //outve(T);
    //outve(A);
    int ans = 0;
    rep(i,N) if(T[i] <= A[i]) chmax(ans,A[i]);
    
    cout << ans-1 << endl;

    
    
    
    

    return 0;
}


Measured memory_bytes: 6656
#include<bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int m,ans;
  cin>>m;
  ans=0;
  ans+=(m/500)*2*500;
  m-=(m/500)*500;
  ans+=(m/5)*5;
  cout<<ans;
  return 0;
}
  

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

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

const int INF = 100000;
int A[100], B[100], C[100];
int DP[100][500][500];

int main(){
    int N,Ma,Mb;
    cin >> N >> Ma >> Mb;

    REP(i,N){
        int a,b,c;
        cin >> a >> b >> c;
        A[i] = a;
        B[i] = b;
        C[i] = c;
    }

    REP(i,N+1){
        REP(j,500){
            REP(k,500){
                DP[i][j][k] = INF;
            }
        }
    }
    DP[0][0][0] = 0;

    REP(i,N){
        REP(j,401){
            REP(k,401){
                if(DP[i][j][k] == INF) continue;
                DP[i+1][j][k] = min(DP[i][j][k], DP[i+1][j][k]);
                DP[i+1][j+A[i]][k+B[i]] = min(DP[i][j][k]+C[i], DP[i+1][j+A[i]][k+B[i]]);
            }
        }
    }

    //REP(i,N+1){
    //    REP(j,10){
    //        REP(k,10){
    //            printf("%d ", DP[i][j][k]);
    //        }
    //        printf("\n");
    //    }
    //    printf("\n");
    //}

    int ans = INT_MAX;
    REP(i,401){
        if(i == 0) continue;
        REP(j,401){
            if(j == 0) continue;
            if(i*Mb == j*Ma)
                ans = min(ans, DP[N][i][j]);
        }
    }

    if(ans != INF)
        cout << ans << endl;
    else
        cout << -1 << endl;

    return 0;
}


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

int main() {
	int A, B, C;
	cin >> A >> B >> C;
	bool f = false;
	if (A == B) {
		if (A != C) {
			f = true;
		}
	} else if (B == C) {
		if (B != A) {
			f = true;
		}
	} else if (C == A) {
		if (A != B) {
			f = true;
		}
	}
	if (f) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

long smax=0;
long smin=0;
long res_min=1e13;

void divide2(int H,int W){
  if(H%2==0 || W%2==0){
    smin=(long)H*(long)W/2;
    smax=(long)H*(long)W/2;
  }else{
    if(H>W){
      int half=H/2;
      smin=(long)half*(long)W;
      smax=smin+W;
    }else{
      int half=W/2;
      smin=(long)half*(long)H;
      smax=smin+H;
    }
  }
}

void divide3(int H,int W){
  if(H%3==0||W%3==0){
    smin=0;
    smax=0;
    res_min=0;
  }else{
    for(int i=H/3;i<=H/3+1;i++){
      divide2(H-i,W);
      long tmp=(long)i*(long)W;
      smax=smax>tmp?smax:tmp;
      smin=tmp>smin?smin:tmp;
      if(res_min>(smax-smin))
	res_min=smax-smin;
    }
    for(int i=W/3;i<=W/3+1;i++){
      divide2(H,W-i);
      long tmp=(long)i*(long)H;
      smax=smax>tmp?smax:tmp;
      smin=tmp>smin?smin:tmp;
      if(res_min>(smax-smin))
	res_min=smax-smin;
    }
  }
}

int main(){
  int H=0,W=0;
  cin>>H>>W;
  divide3(H,W);
  cout<<res_min<<endl;
  return 0;
}

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

int main() {
  
  int a;
  cin >> a;
  
  vector<string> blue(a);
  for(int i=0; i<a; i++){
    string s;
    cin >> s;
    blue.at(i) = s;
  }

  int b;
  cin >> b;
  
  vector<string> red(b);
  for(int i=0; i<b; i++){
    string s;
    cin >> s;
    red.at(i) = s;
  }
  
  int ans = 0;
  for(int k=0; k<a; k++){
    
    int c = 0;

    for(int i=0; i<a; i++){
      if (blue.at(k) == blue.at(i)) c++;
    }

    for(int i=0; i<b; i++){
      if (blue.at(k) == red.at(i)) c--;
    }    
    
    ans = max(ans, c);
  }
  
  cout << ans << endl;
  
  
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int n = sc.nextInt();
        int d = sc.nextInt();
        int[][] x = new int[n][d];

        for (int i = 0; i < n; i++ ) {
            for(int j = 0;j < d; j++ ) {
                x[i][j] = sc.nextInt();
            }
        }

        int ans = 0;

        for (int i = 0; i < n; i++ ) {
            for (int j = i; j < n; j++ ) {
                double temp = 0;
                for (int k = 0; k < d; k++ ) {
                    temp += Math.pow(x[i][k] - x[j][k], 2);
                }
                if (Math.sqrt(temp) == (int)Math.sqrt(temp) && temp != 0) {
                    ans++;
                }
            }
        }
        System.out.println(ans);

        sc.close();
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, m;
string s, t;

int32_t main(){_
   
   cin >> n >> m;

   int sum = 0;
   for (int i = 0; i < m; ++i)
   {
      int x;
      cin >> x;
      sum += x;
   }

   if (sum > n){
      cout<<-1;
      exit(0);
   }
   
   cout<<n-sum;

   return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define INF (1 << 30)

struct Spray{
    Spray(int v){
	val = v;
	minimum = v;
	size = 1;
	l = r = p = 0;
    }
    int val, minimum, size;
    Spray *l, *r, *p;
    
    int state(){
	if(p == 0)return 0;
	if(p->l == this)return -1;
	if(p->r == this)return 1;
    }

    Spray *update(){
	size = (l?l->size:0) + (r?r->size:0) + 1;
	minimum = min(val, min((l?l->minimum:INF), (r?r->minimum:INF)));
	return this;
    }

    void rotate(){
	Spray *par = p, *mid;
	if(par->l == this){
	    mid = r;r = par;
	    par->l = mid;
	}
	if(par->r == this){
	    mid = l;l = par;
	    par->r = mid;
	}
	if(mid)mid->p = par;
	p = par->p; par->p = this;
	if(p && p->l == par)p->l = this;
	if(p && p->r == par)p->r = this;
	par->update();
	update();
    }
    
    void spray(){
	while(state()){
	    int st = state() * p->state();
	    if(st == -1)rotate();
	    if(st == 1)p->rotate();
	    rotate();
	}
    }
};

typedef pair<Spray*, Spray*> SprayP;
typedef SprayP P;

Spray* node(Spray *r, int pos){
    int lsize = (r->l)?r->l->size:0;
    int rsize = (r->r)?r->r->size:0;
    if(lsize == pos - 1)return r;
    if(lsize >  pos - 1)return node(r->l, pos);
    if(lsize <  pos - 1)return node(r->r, pos - lsize - 1);
}

SprayP split(Spray* r, int pos){
    if(pos == 0)return P(0, r);
    if(r->size == pos) return P(r, 0);
    r = node(r, pos);
    r->spray();
    Spray *right = r->r;
    r->r = 0; right->p = 0;
    return P(r->update(), right->update());
}

Spray *merge(Spray *a, Spray *b){
    if(a == 0)return b;
    if(b == 0)return a;
    a = node(a, a->size);
    a->spray();b->spray();
    a->r = b; b->p = a;
    a->update();
    return a->update();
}

SprayP delt(Spray *r, int pos){
    SprayP tmp1 = split(r, pos);
    SprayP tmp2 = split(tmp1.second, 1);
    return P(merge(tmp1.first, tmp2.second), tmp2.first);
}

Spray *insert(Spray *r, Spray *it, int pos){
    SprayP tmp = split(r, pos);
    return merge(merge(tmp.first, it), tmp.second);
}

Spray *shift(Spray *r, int left, int right){
    SprayP tmp = delt(r, right);
    return insert(tmp.first, tmp.second, left);
}

Spray *setnum(Spray *r, int pos, int val){
    r = node(r, pos + 1);
    r->spray();
    r->val = val;
    return r->update();
}

Spray *comb(Spray *r, Spray *l){
    l->l = r;
    if(r) r->p = l;
    return l->update();
}

int main(){
    int n, q, a, x, y, z;
    cin >> n >> q;
    Spray *r = 0;
    for(int i = 0;i < n;i++){
	cin >> a;
	r = comb(r, new Spray(a));
    }
    for(int i = 0;i < q;i++){
	cin >> x >> y >> z;
	if(x == 0){
	    r = shift(r, y, z);
	}
	if(x == 1){
	    SprayP tmp1 = split(r, z + 1);
	    SprayP tmp2 = split(tmp1.first, y);
	    cout << tmp2.second->minimum << endl;
	    tmp1.first = merge(tmp2.first, tmp2.second);
	    r = merge(tmp1.first, tmp1.second);
	}
	if(x == 2){
	    r = setnum(r, y, z);
	}
    }
    return 0;
}

Measured memory_bytes: 10568
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define fi first
#define se second
#define pii pair<long long,long long>
#define int long long
#define endl '\n'
#define pll pair<long long,long long>
#define LONGLONG_MAX 100000000000000
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a);}
                a=(a*a);
                b>>=1;
        }
    return ans;
        
}
int dp[200005][5];
int fun(int i,int j,int a[],int n){
    if(j>=3)return LLONG_MIN;
    if(i>=n){
        return 0;
    }
    if(dp[i][j]!=-1)return dp[i][j];
    int ans=LLONG_MIN;
    ans=max(ans,fun(i+2,j,a,n));
    ans=max(ans,fun(i+3,j+1,a,n));
    ans=max(ans,fun(i+4,j+2,a,n));
    return dp[i][j]=ans+a[i];
}
int fun1(int i,int j,int a[],int n){
    if(j>=2)return LLONG_MIN;
    if(i>=n){
        return 0;
    }
    if(dp[i][j]!=-1)return dp[i][j];
    int ans=LLONG_MIN;
    ans=max(ans,fun1(i+2,j,a,n));
    ans=max(ans,fun1(i+3,j+1,a,n));
    ans=max(ans,fun1(i+4,j+2,a,n));
    return dp[i][j]=ans+a[i];
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    srand(time(0));
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(n%2==0){
        memset(dp,-1,sizeof(dp));
        int ans=max(fun1(0,0,a,n),max(fun1(1,1,a,n),fun1(2,2,a,n)));
        cout<<ans;
        return 0;
    }
    memset(dp,-1,sizeof(dp));
    int ans=max(fun(0,0,a,n),max(fun(1,1,a,n),fun(2,2,a,n)));
    cout<<ans;
    return 0;
}


Measured memory_bytes: 17672
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,a;
    std::deque<int> deq;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>a;
        deq.emplace_back(a);
    }
    int max=0;
    for (int j=0;j<deq.size();j++) {
        int count=0;
        if (deq[j]==1) {
            while (deq[j]==1) {
                count++;
                j++;
            }
        }
        if (max<count) {
            max=count;
        }
    }
    cout<<max+1<<endl;
}


Measured memory_bytes: 3128
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        boolean flag = true;
        for(int i = 1; i < 10; i++){
            if(N / i < 10 && N % i == 0){
                flag = true;
                break;
            }
            else if(N / i >= 10){
                flag = false;
            }
        }

        if(flag) System.out.println("Yes");
        else System.out.println("No");
    }
}

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

class Main{
  static int n=0;
  static int[][] A;
  static int[][] B;
  public static void main(String args[]){
    int i,j;
    Scanner scan = new Scanner(System.in);

    n = scan.nextInt();
    A = new int[n][50];
    B = new int[n+1][n+1];
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
        B[i][j] = 0;
      }
    }

for(i=0;i<n;i++){
  A[i][0] = scan.nextInt();
  A[i][1] = scan.nextInt();
  for(j=0;j<A[i][1];j++){
    A[i][j+2] = scan.nextInt();
  }
}
graph();
for(i=1;i<=n;i++){
  for(j=1;j<=n;j++){
    if(j==n){
      System.out.println(B[i][j]);
      break;
    }
    System.out.print(B[i][j]+" ");
  }
}
    }

static void graph(){
int i,j,k;

for(i=0;i<n;i++){
  for(j=0;j<A[i][1];j++){
    for(k=0;k<n;k++){
      if(A[i][j+2]==A[k][0]){
        B[i+1][k+1] = 1;
      }
    }
  }
}
}

}



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

typedef long double ld;

const ld EPS = 1e-9;
const ld INF = 1e10;
const ld PI = M_PI;

struct Point{
  ld x, y;
  Point(ld x, ld y):x(x), y(y){}
  Point(){}
};

Point operator+(const Point &a, const Point &b){
  return Point(a.x + b.x, a.y + b.y);
}
Point operator-(const Point &a, const Point &b){
  return Point(a.x - b.x, a.y - b.y);
}
Point operator*(const Point &a, const ld b){
  return Point(a.x * b, a.y * b);
}
Point operator*(const Point &a, const Point &b){
  return Point(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
}
Point operator/(const Point &a, const ld b){
  return Point(a.x / b, a.y / b);
}

ld cross(const Point &a, const Point &b){
  return a.x*b.y - a.y*b.x;
}

ld dot(const Point &a, const Point &b){
  return a.x*b.x + a.y*b.y;
}

ld norm(const Point &a){
  return dot(a, a);
}

struct Line:vector<Point>{
  Line(Point a = Point(0, 0), Point b = Point(0, 0)){
    this->push_back(a);
    this->push_back(b);
  }
};

int ccw(Point a, Point b, Point c){
  b = b - a;
  c = c - a;
  if(cross(b, c) > EPS) return +1; // 反時計周り
  if(cross(b, c) < -EPS) return -1; // 時計周り
  if(dot(b, c) < 0) return +2; // c -- a -- b がこの順番に一直線上
  if(norm(b) < norm(c)) return -2; // a -- b -- c がこの順番に一直線上
  return 0; // a -- c -- b が一直線上
}

ld abs(const Point &a){
  return sqrt(norm(a));
}

Point projection(const Line &l, const Point &p){
  ld t = dot(p-l[0], l[1]-l[0]) / norm(l[0] - l[1]);
  return l[0] + (l[1] - l[0]) * t;
}

bool is_intersect_SS(const Line &s, const Line &t){
  return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
    ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}

bool is_intersect_SP(const Line &l, const Point &p){
  return ccw(l[0], l[1], p) == 0;
}

ld distance_SP(const Line &s, const Point &p){
  const Point r = projection(s, p);
  if(is_intersect_SP(s, r)) return abs(r - p);
  return min(abs(s[0] - p), abs(s[1] - p));
}

ld distance_SS(const Line &s, const Line &t){
  if(is_intersect_SS(s, t)) return 0;
  return min(min(distance_SP(s, t[0]), distance_SP(s, t[1])),
	     min(distance_SP(t, s[0]), distance_SP(t, s[1])));
}

int main(){  
  int q;
  cin >> q;
  while(q--){
    Point p0, p1;
    Line l1, l2;
    cin >> p0.x >> p0.y >> p1.x >> p1.y;
    l1 = Line(p0, p1);
    
    cin >> p0.x >> p0.y >> p1.x >> p1.y;
    l2 = Line(p0, p1);
    
    ld ans = distance_SS(l1, l2);
    printf("%.10Lf\n", ans);
    //printf("%.10Lf %.10Lf\n", ans.x, ans.y);
  }
  
  return 0;
}

Measured memory_bytes: 1256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func secondMin(a, b, c int) bool {
	if a < b && b < c {
		return true
	}
	if a > b && b > c {
		return true
	}
	return false
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	p := nextInts(n)

	ans := 0
	for i := 1; i < n-1; i++ {
		if secondMin(p[i-1], p[i], p[i+1]) {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int n,a,b,i,j;
int rec(int x,int y,int z,int m)
{
    if(!z)
        return printf(" %d",y);
    int k=(x^y)&-(x^y),l;
    for(m|=k,l=1; m&l; l<<=1);
    return rec(x,x^l,z-1,m),printf(" %d",x^k^l),rec(x^k^l,y,z-1,m);
}
int main()
{
    for(scanf("%d%d%d",&n,&a,&b); i<n; j+=(a^b)>>i&1,++i);
    (1&j?(printf("YES\n%d",a),rec(a,b,n-1,0),printf("\n")):printf("NO\n")),exit(0);
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
  long long int a, b;
  cin >> a >> b;
  if((a%2==0 && b%2==0) || (a%2!=0 && b%2!=0))
    cout << (a+b)/2 <<"\n";
  else
    cout << "IMPOSSIBLE\n";
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n,k,ans=0;
    cin >> n>> k;
    if(k==0) ans=n*n;
    else
    {
        for(int b=k+1;b<=n;b++)
        {
        ans+=(n/b)*(b-k);
        if(n%b>=k) ans+=n%b-k+1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
Module Module1

	Sub Main()
		Dim tx As IO.TextReader = Console.In

		Dim n As Integer = Integer.Parse(tx.ReadLine())

		If n = 1 Then
			Console.WriteLine("Hello World")
		Else
			Dim a As Integer = Integer.Parse(tx.ReadLine())
			Dim b As Integer = Integer.Parse(tx.ReadLine())
			Console.WriteLine(a + b)
		End If
	End Sub

End Module


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

#define f(i,a,b) for( ll  i = a; i < (ll) b ; i++ ) 
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(a) (ll) a.size()
#define all(a) a.begin(), a.end()
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define inter   ios::sync_with_stdio(false);cin.tie(0)

// policy-based



using namespace std;


typedef long long ll; // int or long long
typedef long double ld;
typedef pair<ll,ll> ii ;
typedef vector<ll>  vi ;
typedef vector<ii> vii ;



 
const ll MAX = 3e5+100;
const ll inf = 1e9;
const ll mod = 1e9+7;

ll mul(ll a,ll b){
	return (a*b)%mod;
}
ll bp(ll a,ll e){
	if(e == 0) return 1;
	if(e&1) return (a*bp(a,e-1))%mod;
	ll x = bp(a,e>>1);
	return (x*x)%mod;
}

ll inv(ll a){
	return bp(a,mod-2);
}
ll fac[MAX];

ll comb(ll n,ll k){
	if(k>n) return 0;
	return mul(fac[n],inv(mul(fac[n-k],fac[k])));
}

int main(){
	fastio;
	fac[0] = 1;
	f(i,1,MAX) fac[i] = mul(fac[i-1],i);
	ll s,ans = 0;
	cin >> s;
	f(i,1,s+1){
		(ans += comb(s-2*i-1,i-1))%=mod;
//		cout << s-2*i+1<<" - "<<i-1 << " "<< comb(s-2*i+1,i-1)<< endl;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5980
N  = int(input())
mon_arr = list(map(int, input().split()))
hero_arr = list(map(int, input().split()))

nums = 0

for i in range(N):
  if (mon_arr[i] + mon_arr[i+1]) > hero_arr[i]:
    nums += hero_arr[i]
    if mon_arr[i+1] > (mon_arr[i] + mon_arr[i+1] - hero_arr[i]):
      mon_arr[i+1] = (mon_arr[i] + mon_arr[i+1] - hero_arr[i])
  else:
    nums += (mon_arr[i] + mon_arr[i+1])
    mon_arr[i+1] = 0
    
print(nums)

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

#define int long long

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)
#define rrep(i, s) rep(i, s, >= 0, --)

#define all(c) begin(c), end(c)
template<typename T>bool maxup(T& a, T&& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool maxup(T& a, T& b) { if (a < b) { a = b; return true; }; }
template<typename T>bool minup(T& a, T&& b) { if (a > b) { a = b; return true; }; }
template<typename T>bool minup(T& a, T& b) { if (a > b) { a = b; return true; }; }

#define X first
#define Y second

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

signed main() {
	int N; cin >> N;
	int x = 1, y = 1;
	rep(_, N) {
		int t, a; cin >> t >> a;
		int k = max((x - 1) / t + 1, (y - 1) / a + 1);
		x = t * k;
		y = a * k;
	}
	cout << x + y << endl;
	system("pause");
}

Measured memory_bytes: 504
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    map<string, int> mp;
    while(n--){
        string x;
        cin >> x;
        mp[x]++;
    }
    set<pair<string, int>> s;
    int mxf = 0;
    for(auto &x : mp){
        mxf = max(mxf, x.S);
        s.insert(MP(x.F, x.S));
    }
    for(auto &x : s){
        if(x.S == mxf){
            cout << x.F << nl;
        }
    }
    return 0;
}
/*
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

Measured memory_bytes: 36352
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <random>
#include <fstream>
#include <string>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <stack>

#define REP(i, N) for(int i = 0; i< N; i++)
using namespace std;
#define ll long long
const int INF = 1 << 29;
const ll llINF = 10000000000000000;

const int MOD = 1000000007;

#define MAX_N 100100
typedef pair<int, int> P;
typedef pair<ll, ll> llP;

int main(){
    char S[110];
    int K;
    cin >> S;
    cin >> K;
    char s;
    REP(i, K){
        s = S[i];
        if(s != '1')break;
    }
    printf("%c\n", s);
}


Measured memory_bytes: 888
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cout << #x << ": " << x << endl
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'

int gcd(int a, int b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	ll n, a, b, c, d, e;
	cin >> n >> a >> b >> c >> d >> e;
	ll mn = min({a, b, c, d, e});
	ll ans = (n + mn - 1) / mn;
	cout << ans + 4 << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 256
num=int(input())
str=input()
redCounter = 0
blueCounter = 0
for i in range(num):
    if str[i] == "R":
        redCounter += 1
    elif str[i] == "B":
        blueCounter += 1

if redCounter > blueCounter:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
/**
 *   created: 13 July 2019  09:12:11
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) c.begin(),c.end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================


int main()
{
	optimizeIO();
	int tt=1;
	//cin>>tt;
	while(tt--){
		int n,t;
		cin>>n>>t;
		int temp = 2*t+1;
		int res = n/temp;
		if(n%temp)
			res++;
		cout<<res;
	}
	return 0;
}


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

using namespace std;
using ll = long long;

void solve(ll A, ll B, ll C) { cout << max({A, B, C}) * 9 + A + B + C << endl; }

int main() {
  ll A;
  cin >> A;
  ll B;
  cin >> B;
  ll C;
  cin >> C;
  solve(A, B, C);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int ans,n,tot,d[N],dp[N],head[N],nex[2*N],to[2*N];
void add(int u,int v)
{
    to[++tot]=v;
    nex[tot]=head[u];
    head[u]=tot;
}
void dfs(int u,int fa)
{
    if(!head[u])
    {d[u]=1;return;}
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];
        if(v==fa) continue;
        dfs(v,u);
        ans=max(ans,d[u]+d[v]+1);d[u]=max(d[u],d[v]+1);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    ans++;
    if(ans%3!=2) printf("First\n");
    else printf("Second\n");
}


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

// Swapping Two Numbers

int main(){
	int i;
	int datasets[3000][2];
	int numOfData;

	for(i = 0; i < 3000; i++){
		cin >> datasets[i][0] >> datasets[i][1];;

		if (datasets[i][0] == 0 && datasets[i][1] == 0){
			break;
		}
	}
	numOfData = i;

	for(i = 0; i < numOfData; i++){
		if(datasets[i][0] < datasets[i][1]){
			cout << datasets[i][0] << ' ' << datasets[i][1] << endl;
		}else{
			cout << datasets[i][1] << ' ' << datasets[i][0] << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3112
n=int(input())
A=[int(i) for i in input().split()]

L=[0 for i in range(n+1)]
for num in A:
    L[num]+=1

big=0
for num in L:
    big+=num*(num-1)//2

for num in A:
    sma=L[num]
    print(big-sma*(sma-1)//2+(sma-1)*(sma-2)//2)

Measured memory_bytes: 104732
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))
S.sort()
if sum(S)%10!=0:
    print(sum(S))
else:
    for i in range(N):
        if S[i]%10!=0:
            print(sum(S)-S[i])
            break
        elif i==N-1:
            print(0)
            break

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

#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 998244353 
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define mii unordered_map<int,int>
#define mll unordered_map<ll,ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi  first

#define se second
#define pb push_backP
#define mp make_pair
#define pp pop_back
#define vii vector<int>
#define vll vector<ll>
#define vpp vector<pii>
#define all(c) c.begin(),c.end()
#define tr(it,c) for(it = c.begin() ; it!=c.end() ; it++)
int inf = INT_MAX ;
ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }
ll gcd(ll a,ll b){ return ((b==0) ? a:gcd(b,a%b));}

ll dp[15][15];
ll get_first(ll x){
   ll b;
   while(x){
     b = x % 10;
     x/=10;
   }
   return b;
}

int main(){
	boost;

	ll n;  cin >> n; 
     for(int i = 1; i <= n; i++){
        dp[get_first(i)][i%10]++;
     }
     ll ans = 0;
     for(int i = 0; i <= 9; i++){
       for(int j = 0; j <=9; j++){
            ans = ans + dp[i][j]*dp[j][i];
       }
     }
 
       cout << ans << endl;
       return 0;

}

Measured memory_bytes: 256
import sys
# from collections import defaultdict, deque
# import math
# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def solve():
    n = getN()
    nums = getList()

    bulk = n*(n+1)//2
    ope = sum(nums) // bulk
    if sum(nums) % bulk != 0:
        print("NO")
        return
    nums = nums + [nums[0]]

    tmp = 0
    for i, j in zip(nums, nums[1:]):
        if j - i > ope:
            print("NO")
            return
        else:
            expected = i + ope
            if (expected - j) % n != 0:
                print("NO")
                return
            tmp += (expected - j) // n
    # print(tmp)
    if tmp == ope:
        print("YES")
    else:
        print("NO")


def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()


Measured memory_bytes: 87156
/*
    Name:zhangchuanyan
    Copyright:HHTC
    Author:zhangchuanyan
    Date: 2020/8/15 20:38:08
    Description:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	string str;
	cin>>str;
	if(str=="RRR"){
		cout<<"3\n";
	} else if(str=="RRS"||str=="SRR"){
		cout<<"2\n";
	} else if(str=="SSS"){
		cout<<"0\n";
	} else{
		cout<<"1\n";
	}
    return 0;
}



Measured memory_bytes: 3128
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(N)]

D.sort(key=lambda x:x[1],reverse=True)

DP=[[0,0] for i in range(T+1)]

for ind,(x,y) in enumerate(D):
    for time in range(T,x-1,-1):
        if DP[time][0]<DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time]=[DP[time-x][0]+y,ind+1]
            else:
                DP[time]=[DP[time-x][0]+y,DP[time-x][1]]

        elif DP[time][0]==DP[time-x][0]+y:

            if DP[time-x][1]==ind:
                DP[time][1]=min(ind+1,DP[time][1])
            else:
                DP[time][1]=min(DP[time-x][1],DP[time][1])

    #print(DP)

D.append((0,0))
                
ANS=DP[-1][0]

for x,y in DP[:-1]:
    #if x==0:
    #    continue
    ANS=max(ANS,x+D[y][1])

print(ANS)
    


Measured memory_bytes: 51804
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("unroll-loops")
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define DB double
#define ST string
#define BS bitset
#define VE vector
#define VL vector<LL>
#define VP vector<pair<LL,LL>>
#define VVL vector<vector<LL>>
#define PQ priority_queue
#define PQS priority_queue<LL,vector<LL>,greater<LL>>
#define PB push_back
#define POB pop_back
#define PF push_front
#define POF pop_front
#define EB emplace_back
#define MP make_pair
#define TS to_string
#define TU to_ullong
#define FOR(i,a,n) for(i=a;i<n;i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define UB(a,n) *upper_bound(ALL(a),n)
#define LB(a,n) *lower_bound(ALL(a),n)
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000001
//#define ERR 0.00000000000001
#define NUM 200010
#define FAST cin.tie(0);ios::sync_with_stdio(false)

void Yn(LL a){if(a)printf("Yes\n");else printf("No\n");}
void YN(LL a){if(a)printf("YES\n");else printf("NO\n");}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL GCD(LL a,LL b){LL c=1,tmp=max(a,b);b=min(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int lcmpr(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return -1;if(*(LL*)a<*(LL*)b)return 1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int ccmpr(const void* a,const void* b){return *(char*)b-*(char*)a;}
int scmp(const void* a,const void* b){return strcmp((char*)a,(char*)b);}
int scmpr(const void* a,const void* b){return strcmp((char*)b,(char*)a);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(m,d);x-=k*y;swap(x,y);}return mod(a*mod(x,MOD),MOD);}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}
bool cmps(pair<LL,LL> a,pair<LL,LL> b){if(a.second!=b.second)return a.second<b.second;return a.first<b.first;}

int main(){
  FAST;
  LL i,j,k,q,n,x,m,a,b,c,ans;
  cin>>k>>q;
  LL d[k];
  rep(i,k)cin>>d[i];
  rep(i,q){
    cin>>n>>x>>m;
    a=c=0;
    rep(j,k){
      b=(a+d[j])%m;
      if(a<b)c++;
      a=b;
    }
    ans=c*((n-1)/k);
    //cout<<a<<" "<<c<<" "<<ans<<endl;
    ans-=(x%m+a*((n-1)/k))/m;
    a=(x+a*((n-1)/k))%m;
    rep(j,(n-1)%k){
      b=(a+d[j])%m;
      if(a<b)ans++;
      a=b;
    }
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it;}cout<<endl;}


int main() {
    ll n;
    cin>>n;
    ll sum = 100000000000;
    rep(i,n/2){
        ll a = i+1;
        ll b = n -a;

        ll aaa = 0;
        rep(j, to_string(a).size()){
            aaa+=to_string(a)[j] - '0';
        } 
        rep(j, to_string(b).size()){
            aaa+=to_string(b)[j] - '0';
        } 
        sum = min(sum,aaa);
    }
    pr(sum);
}



Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
	v = A[i]
	j = i-1
	while j>=0 and A[j]>v:
		A[j+1] = A[j]
		j-=1
	A[j+1] = v
	print(*A)


Measured memory_bytes: 5980
ny = list(map(int, input().split()))

for i in range(ny[0] + 1):
    for j in range(ny[0] + 1):
        if (1000 * i + 5000 * j <= ny[1]) and ((ny[1] - 1000*i - 5000*j) % 10000 == 0) and \
        ((ny[1] - 1000*i - 5000*j) // 10000 + i + j == ny[0]):
            print((ny[1] - 1000*i - 5000*j) // 10000, j, i)
            break
    else:
        continue
    break
else:
    print(-1, -1, -1)

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

const int mnx = 1e6 + 9;
const int mod = 1e9 + 7;

ll n, a, b, c, d;

int main() {

cin >> n >> a >> b;
cin >> c >> d;

for(int i = 1; i <= n; i++){
    if(i * c - d * (n - i - 1) <= b - a && b - a <= i * d - c * (n - i - 1)){
        cout << "YES\n";
        return 0;
    }
}

cout << "NO\n";

return 0;

}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        long[] a = Console.ReadLine().Split().Select(i => long.Parse(i)).ToArray();

        int ans = 0;
        bool flag = true;
        while (flag)
        {
            for (int i = 0; i < n; i++)
            {
                if (a[i] % 2 == 1)
                {
                    flag = !flag;
                    break;
                }
                else
                {
                    a[i] /= 2;
                }
            }
            if (flag) ans++;
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11348
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
template <typename T> 
using lim = numeric_limits<T>;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = 2e5;
int n;
string s;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;

    int l = 0;
    int r = n-1;
    int cnt = 0;
    while(l < r){
        if (s[l] == 'R') l++;
        else if (s[r] == 'W') r--;
        else {
            cnt++;
            l++;
            r--;
        }
    }
    cout << cnt << "\n";
}

Measured memory_bytes: 3768