akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
            Console.ReadLine();
        }

        public void Solve(ConsoleInput cin)
        {
            string[] list = { "dream", "dreamer", "erase", "eraser" };
            string s = cin.Read;


            bool can;
            do
            {
                can = false;
                foreach (string str in list)
                {
                    if (s.Length - str.Length < 0)
                        continue;

                    if (str.Equals(s.Substring(s.Length - str.Length)))
                    {
                        s = s.Substring(0, s.LastIndexOf(str));
                        can = true;
                        break;
                    }
                }
            } while (can == true && s.Length > 0);
            Console.WriteLine(can ? "YES" : "NO");
        }


    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long num) { var ret = new string[num]; for (long i = 0; i < num; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long num) { var ret = new int[num]; for (long i = 0; i < num; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long num) { var ret = new long[num]; for (long i = 0; i < num; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 30764
INF = 2*int(1e9)
cnt = 0
def merge(A, left, mid, right):
    global cnt
    nl = mid - left
    nr = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(INF)
    R.append(INF)
    i = 0
    j = 0
    for k in range(left, right):
        cnt = cnt +  1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i +  1
        else:
            A[k] = R[j]
            j = j + 1


def mergeSort(A, left, right):
    if left+1<right:
        mid = (left+right)//2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

def main():
    n = int(input())
    s = [int(i) for i in input().split()]
    mergeSort(s, 0, n)
    for i in range(n):
        if i == n-1:
            print(s[i])
        else:
            print(s[i], end=' ')

    print(cnt)
main()


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

typedef long long int ll;
typedef string str;

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t=0,n,m,k,i,a,b,j;
	cin >> n;
	ll h[10004]={0};
	for(i=1;i<=100;i++)
	{
		for(j=1;j<=100;j++)
		{
			for(k=1;k<=100;k++)
			{
				t=i*(i+j+k)+j*(j+k)+k*k;
				if(t<10001)
					h[t]++;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		cout << h[i] << "\n";
	}
	return 0;
}

Measured memory_bytes: 3696
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

#define MOD 1000000007
#define ll long long

using namespace std;


ll N,M;
vector<ll> a;
vector<ll> b;

ll db[200001]={0};



int main(){
  ll ina,inb;
  
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> M;
  a.push_back(0);
  b.push_back(0);
  for(ll i = 0;i<M;i++){
    cin >> ina>> inb;
    a.push_back(ina);
    b.push_back(inb);
    if(ina == 1)db[inb]=1;
  }


  for(ll i = 1;i<=M;i++){
    if(db[a[i]]){
      if(b[i]==N){cout << "POSSIBLE" << endl;
	return 0;
      }
    }
  }
  
  cout << "IMPOSSIBLE" << endl;
  
  return 0;
}


Measured memory_bytes: 5220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    ll n,k; cin >> n >> k;
    vector<ll> v;
    for(ll i=0;i<n;i++){
        ll h; cin >> h;
        v.push_back(h);
    }
    sort(v.begin(),v.end());
    ll ans=0;
    for(ll i=0;i<n-k;i++){
        ans+=v[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2420
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    int i =0, count =0;
    while (i < N-2) {
      if (S.charAt(i) == 'A' && S.charAt(i+1) == 'B' && S.charAt(i+2) == 'C') {
        count++;
        i += 3;
      } else {
      i++;
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 22740
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e18;

int main()
{
    ll n,k;
    cin >> n >> k;
    ll val=k;
    vector<ll> a(n),b(45);
    rep(i,n){
        cin >> a[i];
        rep(j,45){
            if((a[i]>>j)%2==1) b[j]++;
        }
    }
    vector<vector<ll>> dp(46,vector<ll>(2)); //1→ぴったり 0→真に小さい
    vector<ll> p(45);
    ll v=1;
    rep(i,45){
        p[i]=v;
        v*=2;
    }
    ll cnt=0;
    while(val!=0){
        cnt++;
        val/=2;
    }
    ll ans=0;
    rep(i,45){
        if(i>=cnt){
            ans+=b[i]*p[i];
        }
    }
    rep(i,cnt){
        ll move=cnt-1-i;
        if((k>>move)%2==1){
            if(2*b[move]>n){
                dp[i+1][0]=max(dp[i][0]+b[move]*p[move],dp[i][1]+b[move]*p[move]);
                dp[i+1][1]=dp[i][1]+(n-b[move])*p[move];
            }
            else{
                if(dp[i][0]!=0){
                    dp[i+1][0]=dp[i][0]+(n-b[move])*p[move];
                }
                dp[i+1][0]=max(dp[i+1][0],dp[i][1]+b[move]*p[move]);
                dp[i+1][1]=dp[i][1]+(n-b[move])*p[move];
            }
        }
        else{
            if(2*b[move]>n){
                if(dp[i][0]!=0){
                    dp[i+1][0]=dp[i][0]+b[move]*p[move];
                }
                dp[i+1][1]=dp[i][1]+b[move]*p[move];
            }
            else{
                if(dp[i][0]!=0){
                    dp[i+1][0]=dp[i][0]+(n-b[move])*p[move];
                }
                dp[i+1][1]=dp[i][1]+b[move]*p[move];
            }
        }
        //cout << dp[i+1][0] << " " << dp[i+1][1] << endl;
        
    }
    cout << ans+max(dp[cnt][0],dp[cnt][1]) << endl;
    return 0;
} 

Measured memory_bytes: 1024
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] word = sc.next().split("",0);
        int times = sc.nextInt();
        for(int i = 0; i < times; i++){
            String test = sc.next();
            int num1 = sc.nextInt();
            int num2 = sc.nextInt();
            int count = 0;
            if(test.equals("replace")){
                String[] str = sc.next().split("",0);
                for(int j = num1; j <= num2; j++){
                    word[j] = str[count];
                    count++;
                }
            }
            else if(test.equals("reverse")){
                String[] reverse = new String[num2 - num1 + 1];
                for(int l = num2; l >= num1; l--){
                    reverse[count] = word[l];
                    count++;
                }
                count = 0;
                for(int m = num1; m <= num2; m++){
                    word[m] = reverse[count];
                    count++;
                }
            }
            else {
                for(int k = num1; k <= num2; k++){
                    System.out.print(word[k]);
                }
                System.out.println();
            }
        }
    }
}


Measured memory_bytes: 33860
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n, f[35] = {0};
    f[0] = 1;
    rep(i,31){
        f[i + 1]+= f[i];
        f[i + 2]+= f[i];
        f[i + 3]+= f[i];
    }
    while(cin >> n, n){
        int day = f[n] / 10;
        if(f[n] / 10 == 0) day++;
        int y = day / 365;
        if(day % 365 != 0) y++;
        cout << y << endl;
    }

}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a);i < (b);++i)
#define FORR(i, b, a) for (int i = (b) - 1;i >= 0;--i)
#define REP(i, n) for(int i = 0;i < (n);++i)
#define REPR(i, n) for(int i = (n) - 1;i >= 0;--i)
#define ITER(itr, v) for(auto itr = v.begin();itr != v.end();++itr)
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
#define SIZE(v) int(v.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	ll N, K;
	cin >> N >> K;
	if (N <= K) {
		cout << min(N, K - N) << endl;
		return 0;
	}
	ll res = N - N / K * K;
	res = min(res, K - res);
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned int ui;
#define infin (ll)(pow(10,9)+7)
#define push_back pb;
using namespace std;
int main()
{
   int n;
   cin>>n;
   pair<int,int> dice[n];
   int count=0,e=0;
   for(int i=0;i<n;i++)
   {
      cin>>dice[i].first;
      cin>>dice[i].second;
      if (dice[i].first==dice[i].second)
      {
         count+=1;
         if (count==3)
         {
            cout<<"Yes"<<endl;
            e=1;
            break;
         }
      }
      else
      {
         count=0;
      }
   }
   if (e==0)
     cout<<"No"<<endl;
}

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

using namespace std;

int tree[800005], ans[200005], a[200005], maxV;
vector <int> edge[200005];
int stamp[200005];

void update(int l, int r, int ind, int idx, int val) {
	if (l == r) {
		tree[ind] = val;
		return;
	}
	int mid = (l + r) / 2;
	if (idx <= mid) update(l, mid, ind * 2, idx, val);
	else update(mid + 1, r, ind * 2 + 1, idx, val);
	tree[ind] = max(tree[ind * 2], tree[ind * 2 + 1]);
}

int query(int l, int r, int ind, int lx, int ly) {
	if (lx <= l && r <= ly) {
		return tree[ind];
	}
	int mid = (l + r) / 2;
	int mx = 0;
	if (lx <= mid) mx = max(mx, query(l, mid, ind * 2, lx, ly));
	if (ly > mid) mx = max(mx, query(mid + 1, r, ind * 2 + 1, lx, ly));
	return mx;
}

int getVal(int l, int r, int ind, int lx) {
	if (l == r) {
		return tree[ind];
	}
	int mid = (l + r) / 2;
	if (lx <= mid) return getVal(l, mid, ind * 2, lx);
	else return getVal(mid + 1, r, ind * 2 + 1, lx);
}

void solve(int id, int p) {
	stamp[id] = getVal(1, maxV, 1, a[id]);
	int best = 0;
	if (a[id] - 1 >= 1) best = query(1, maxV, 1, 1, a[id] - 1);
	update(1, maxV, 1, a[id], best + 1);
	ans[id] = tree[1];
	
	for (int i = 0; i < edge[id].size(); i++) {
		int to = edge[id][i];
		if (to == p) continue;
		solve(to, id);
	}
	
	update(1, maxV, 1, a[id], stamp[id]);
}

int main() {
	int n;
	scanf("%d", &n);
	
	vector <int> v;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		v.push_back(a[i]);
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	maxV = v.size();
	
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
	}
	
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	
	solve(1, -1);
	
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}


Measured memory_bytes: 28596
N=int(input())
a = [int(input()) for i in range(N)]
cnt=0
light=1
while True:
    light=a[light-1]
    cnt=cnt+1
    if light==2:
        break
    if cnt>N:
        break

if light==2:
    print(cnt)
else:
    print(-1)


Measured memory_bytes: 7084
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

ll N;

signed main(){
    cin >> N;
    cout << (N-1)/2 << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;

const ll MOD=1e9+7,N=1e6,MAX_S=1e8;
ll S;
ll mpw(ll n,ll m){
	ll ret=1;
	while(m){
		if (m&1){
			ret*=n;
			ret%=MOD;
		}
		n*=n;
		n%=MOD;
		m>>=1;
	}
	return ret;
}
ll pw(ll n,ll m){
	ll ret=1;
	while(m){
		if (m&1){
			ret*=n;
		}
		n*=n;
		m>>=1;
	}
	return ret;
}	
ll dig(ll n){
	ll ret=0;
	while(n){
		ret++;
		n/=10;
	}
	return ret;
}
int main(){
	cin>>S;
	ll sqs=0;
	FOR(i,1,S+8){
		if (i*i>=S){
			sqs=i;
			break;
		}
	}
	ll ans=0;
	FOR(i,1,N){
		ll sm=0;
		ll d=dig(i);
		ll l=i;
		while(sm+d*(pw(10,d)-l)<S){
			sm+=d*(pw(10,d)-l);
			l=pw(10,d);
			d++;
		}
		if ((S-sm)%d==0){
			ans++;
			ans%=MOD;
		}
	}
	for(ll i=1;i*i<=S;i++){
		if (S%i==0){
			ll j=S/i;
			if ((i==7 && j<=9*pw(10,6)) || i>7){
				ans+=(9*mpw(10,i-1)%MOD-j+1+MOD)%MOD;
				ans%=MOD;
			}
			if (i!=j){
				if ((j==7 && i<=9*pw(10,6)) || j>7){
					ans+=(9*mpw(10,j-1)%MOD-i+1+MOD)%MOD;
					ans%=MOD;
				}
				if (j>sqs){
					ans+=MOD-1;
					ans%=MOD;
				}
			}
		}
	}		
	FOR(d,7,sqs+1){
		ll y=S%d,x=S/d-y;
		if (d==7){
			if (x>9*pw(10,6)){
				ll n=(x-9*pw(10,6)+d)/(d+1);
				x-=n*(d+1);
				y+=n*d;
			}
		}
		if (y==0){
			y+=d;
			x-=d+1;
		}
		if (x>0){
			ans+=(x-1)/(d+1)+1;
			ans%=MOD;
		}
	}
	FOR(k,1,sqs){
		ll l=max({sqs,S/(k+1),S/k-1}),r=S/k;
		ans+=max(r-l,0ll);
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
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 (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

ll dp[100007];
vector<vector<ll>> E(100007);
ll N,M;
ll indeg[100007];
bool B[100007]; 

void bfs(ll s){
  queue<ll> Q;
  Q.push(s);
  B[s]=true;
  while(!Q.empty()){
    ll u=Q.front();
    Q.pop();
    rep(i,E[u].size()){
      ll v=E[u][i];
      indeg[v]--;
      dp[v]=max(dp[v],dp[u]+1);
      if(indeg[v]==0 && !B[v]){
        B[v]=true;
        Q.push(v);
      }
    }
  }
}

void topological_sort(){
  rep(i,N+1){     // 初期化
    indeg[i]=0;
  }
  rep(i,N+1){
    rep(j,E[i].size()){    //  入次数を持たせる
      indeg[E[i][j]]++;
    }
  }

  Rep(i,1,N+1){                 // 0indexed か 1indexed か で変える
    if(indeg[i]==0 && !B[i]){
      bfs(i);
    }
  }
}

int main(){
  cin >> N >> M;
  rep(i,N){
    B[i]=false;
  }
  rep(i,M){
    ll a,b;
    cin >> a >> b;
    E[a].pb(b);
  }

  topological_sort();
  ll ma = -1;
  Rep(i,1,N+1){
    ma = max(ma,dp[i]);
  }
  cout << ma << endl;
}

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

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n ;
string s ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>s ;
	n = s.size() ;
	if(s[0] == '0' || s[n-1] == '1')
		return cout<<"-1\n" , 0 ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		if(s[i] != s[n-2-i])
			return cout<<"-1\n" , 0 ;
	}
	int now = 1 , cur = 1 ;
	for(int i = n-2 ; i >= 0 ; --i)
	{
		cur++ ;
		cout<<now<<" "<<cur<<"\n" ;
		if(s[i] == '1')
			now = cur ;
	}
	return 0 ;
}		

Measured memory_bytes: 1616
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int arr[10];
int main()
{
    int i,n,max=0,sum=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
        max=max>arr[i]?max:arr[i];
        sum+=arr[i];
        //printf("arr[%d]:%d max:%d sum:%d\n",i,arr[i],max,sum);
    }
    printf("%d\n",sum-(int)(max/2));
    return 0;
}


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

int main() {

  long long A,B,K;
  cin >> A >> B >> K;

  if(A==0 && B == 0){
    cout << A << " " << B << endl;
    return 0;
  }

  if(K-A>0){
    if(B > K-A){
      B = B-(K-A);
    }else{
      B=0;
    }
    A = 0;
  }else{
    A = A-K;
  }

  cout << A << " " << B << endl;

}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))



x,n = readints()
p = readints()

if x not in p:
    print(x)
    exit()
i = 1
while 1:
    if x-i not in p:
        print(x-i)
        exit()
    elif x+i not in p:
        print(x+i)
        exit()
    i+=1



Measured memory_bytes: 61916
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define ld double
#define oo 2e18
#define OS tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

const int N = 2e3 + 5;
int n, a[N];
ll dp[N][N];
vector<pair<int, int>> v;

ll rec(ll st, ll en, int _n) {
    if (st > en) return 0;
    ll &re = dp[st][en];
    if (re != -1) return re;
    ll val = v[_n].first, indx = v[_n].second;
    re = max(abs(indx - st) * val + rec(st + 1, en, _n - 1), abs(indx - en) * val + rec(st, en - 1, _n - 1));
    return re;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        v.emplace_back(a[i], i);
    }
    memset(dp, -1, sizeof(dp));
    sort(v.begin(), v.end());
    ll ans = rec(0, n - 1, n - 1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 35224
def rrs()
  a = gets.split(' ').map(&:to_i)
  n = a[0]
  t = a[1]
  ct = 0
  q = []
  for i in 0..n-1
    q[i] = gets.split(' ')
  end
  while q.size > 0
    n = q.shift
    m = n[1].to_i
    if m <= t
      ct += m
      print n[0], ' '
      puts ct
    else
      m -= t
      ct += t
      n[1] = m
      q.push(n)
    end
  end
end

rrs()

Measured memory_bytes: 19984
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;

struct Seg {
    int val[N << 2], lazy[N << 2];
    void init(int n) {
        for (int i = 1; i <= 4 * n; i++) {
            val[i] = n;
            lazy[i] = INF;
        }
    }
    void push_up(int u) {
        val[u] = min(val[u << 1], val[u << 1 | 1]);
    }
    void push_down(int u) {
        if (lazy[u] != INF) {
            val[u << 1] = min(val[u << 1], lazy[u]);
            val[u << 1 | 1] = min(val[u << 1 | 1], lazy[u]);
            lazy[u << 1] = min(lazy[u << 1], lazy[u]);
            lazy[u << 1 | 1] = min(lazy[u << 1 | 1], lazy[u]);
            lazy[u] = INF;
        }
    }
    void update(int u, int l, int r, int x, int y, int v) {
        if (x <= l && r <= y) {
            val[u] = min(val[u], v);
            lazy[u] = min(lazy[u], v);
            return;
        }
        int mid = l + r >> 1;
        push_down(u);
        if (x <= mid) update(u << 1, l, mid, x, y, v);
        if (y > mid) update(u << 1 | 1, mid + 1, r, x, y, v);
        push_up(u);
    }
    int query(int u, int l, int r, int x) {
        if (l == r) return val[u];
        int mid = l + r >> 1;
        push_down(u);
        if (x <= mid)
            return query(u << 1, l, mid, x);
        else
            return query(u << 1 | 1, mid + 1, r, x);
    }
} T1, T2;

int a[N];
int main() {
    int n, q;
    cin >> n >> q;
    T1.init(n);
    T2.init(n);
    LL ans = (n - 2LL) * (n - 2);
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            int g = T2.query(1, 1, n, x);
            ans -= g - 2;
            T1.update(1, 1, n, 1, g, x);

        } else {
            int g = T1.query(1, 1, n, x);
            ans -= g - 2;
            T2.update(1, 1, n, 1, g, x);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 16100
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

int main() {
  i64 N, K;
  cin >> N >> K;
  vector<i64> A(N);
  rep(i,0,N) cin >> A[i];
  vector<i64> next(N);
  map<i64, i64> mp;
  rep(i,0,N) {
    if(mp.count(A[i])) {
      i64 tmp = next[mp[A[i]]];
      next[mp[A[i]]] = i;
      next[i] = tmp;
      mp[A[i]] = i;
    }
    else {
      mp[A[i]] = i;
      next[i] = N + i;
    }
  }

  i64 cnt = 0;
  {
    i64 now = 0;
    while(true) {
      i64 ne = next[now];
      if(ne >= N) cnt++;
      now = (ne + 1) % N;
      if(now == 0) break;
    }
  }
  cnt++;
  K %= cnt;

  {
    cnt = 0;
    i64 now = 0;
    while(cnt < K - 1) {
      i64 ne = next[now];
      if(ne >= N) cnt++;
      now = (ne + 1) % N;
      if(now == 0) break;
    }
    vector<i64> vec;
    for(int i = now; i < N; i++) {
      if(next[i] >= N) {
        vec.push_back(A[i]);
      }
      else i = next[i];
    }

    for(int i = 0;i < vec.size();i++) {
      cout << vec[i] << " \n"[i +1 == vec.size()];
    }
  }
}


Measured memory_bytes: 18800
import java.util.Scanner;

public class Main{
	
	static int n;
	static int[] a= new int [22];
	
	static int dfs(int A, int B, int i) {
		int x, y;
		if(i==n) {
			return Math.abs(A-B);
		}
		x=dfs(A+a[i], B, i+1);
		y=dfs(A, B+a[i], i+1);
		return Math.min(x, y);
	}
	
	public  static void main(String[] args) {
    	try (Scanner sc = new Scanner(System.in)) {
    		while(sc.hasNext()) {
    			n=sc.nextInt();
    			if(n==0) {
    				break;
    			}
    			for(int i=0; i<n; i++) {
    				a[i]=sc.nextInt();
    			}
    			System.out.println(dfs(0, 0, 0));
    		}
    	}
    }
}


Measured memory_bytes: 28520
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define inputv(arr,n) for(ll i=0;i<n;i++){ll value;cin>>value;arr.pb(value);}
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define gcd __gcd
#define nl cout<<"\n"
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
//sort in reverse order
bool compare(ll x, ll y){
    return x>y;
}
void solve()
{
  ll s,w;
  cin>>s>>w;
  if(s>w)
  {
      cout<<"safe";
      nl;
  }
  else
  {
      cout<<"unsafe";
      nl;
  }
}
int main()
{
    IOS;
    int T=1;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    n %= 10;

    if(n == 0 || n == 1 || n == 6 || n == 8)
        cout << "pon";
    else if(n == 3)
        cout << "bon";
    else
        cout << "hon";
}


Measured memory_bytes: 3648
N = int(input())
A = list(map(int,input().split()))

c=0
absA=[0 for i in range(N)]
for i in range(N):
    if A[i] <=0:
        c+=1
    absA[i]=abs(A[i])

if c%2==0:
    res = sum(absA)
else:
    res = sum(absA)-min(absA)*2
print(res)


Measured memory_bytes: 14412
#include <iostream>
using namespace std;
int n,m;

int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=2000;i++)
	{
        for(int j=0;j+i<=2000&&i+j<=n;j++)
		{
            if(i*10000+j*5000+(n-i-j)*1000==m)
            {
                cout<<i<<" "<<j<<" "<<n-i-j<<endl;
                return 0;
            }
        }
    }
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
    //return 0;
}

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

using namespace std;
typedef long long ll;

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

    bool res = true;
    for (int i = 1; i < N; i++) {
        if (h[i] >= h[i-1]) continue;
        else if (h[i] + 1 == h[i-1]) h[i] += 1;
        else {
            res = false;
            break;
        }
    }
        
    if (res) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1e18;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rnr(i,a,b) for(int i=int(a);i>=int(b);i--)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

struct UnionFind {
    vector<int> par;
    vector<int> siz;

    UnionFind(int N) : par(N), siz(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i, siz[i] = 1;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        siz[ry] += siz[rx];
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) {
        return siz[root(x)];
    }
};

int main() {
    int n, m; cin >> n >> m;
    int a[m], b[m];
    map<Pint, bool> mp;
    UnionFind uf(n);
    rep(i, m) {
        cin >> a[i] >> b[i];
        --a[i], --b[i];
        if(a[i] > b[i]) swap(a[i], b[i]);
        if(mp[{a[i], b[i]}]) continue;
        mp[{a[i], b[i]}] = true;
        uf.unite(a[i], b[i]);
    }
    int ans = 0;
    rep(i, n) {
        ans = max(ans, uf.size(i));
    }
    cout << ans << endl;
}


Measured memory_bytes: 24936
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
//#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_7 1000003
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;

#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////


int main(){fastio
    
    ll n,k;cin>>n>>k;
    if(k==1){
        cout<<0<<endl;
    }else{
        cout<<n-(k-1)-1<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
int main(){
  ll n, a, x = 1;
  cin >> n;
  for (ll i = 0; i < n; i++) {
    cin >> a;
    if (a % 2 == 0) {
      x *= 2;
    }
  }
  cout << pow(3, n) - x << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

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

int main(){
    ll N, K; cin >> N >> K;
    vector<ll> a(N); rep(i, N) cin >> a[i];
    ll ma = *max_element(all(a));
    ll gc = *a.begin();
    rep(i, N) gc = gcd(a[i], gc);
    pt(K <= ma && (ma - K) % gc == 0 ? "POSSIBLE" : "IMPOSSIBLE");
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#define Fi first
#define Se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll n;
ll a, b;
pll d[10005];
ll c[10005];
ll ans[10005];
vector<ll> graph[10005];

int main()
{
    for (int i = 0; i < 10005; i++) {
        d[i].Se = i;
    }
    
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;

        d[a].Fi++;
        d[b].Fi++;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

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

    sort(c, c + n);
    
    set<pll> nodes(d + 1, d + n + 1);

    for (int i = 0; i < n; i++) {
        pll node = *(nodes.begin());
        nodes.erase(node);
        ans[node.Se] = c[i];

        for (int j = 0; j < graph[node.Se].size(); j++) {

            if (nodes.count(d[graph[node.Se][j]]) == 1) {
                nodes.erase(d[graph[node.Se][j]]);
                d[graph[node.Se][j]].Fi--;

                nodes.insert(d[graph[node.Se][j]]);
            }
        }
    }

    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            sum += min(ans[graph[i][j]], ans[i]);
        }
    }

    cout << sum / 2 << endl;
    for (int i = 1; i <= n; i++) {
        if (i != 1) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << endl;
}


Measured memory_bytes: 1920
/* include */
#include"bits/stdc++.h"
/* namespace */
using namespace std;
/* typedef */
/* long系 */
typedef long long ll;	// long long
typedef long double ld;	// long double
/* vector系 */
typedef vector<int> vint;	// intのvector
typedef vector<double> vdouble;	// doubleのvector
typedef vector<ll> vll;	// llのvector
typedef vector<ld> vld;	// ldのvector
typedef vector<pair<int, int>> vi_i;	// i_iのvector
typedef vector<pair<double, double>> vd_d;	// d_dのvector
typedef vector<pair<ll, ll>> vl_l;	// l_lのvector
typedef vector<pair<ld, ld>> vld_ld;	// ld_ldのvector
typedef vector<string> vstring;	// stringのvector
/* pair系 */
typedef pair<int, int> i_i;	// int同士のpair
typedef pair<double, double> d_d;	// double同士のpair
typedef pair<ll, ll> l_l;	// ll同士のpair
typedef pair<ld, ld> ld_ld;	// ld同士のpair
/* define */
#define pb push_back	// push_back
#define all(v) v.begin(),v.end()	// コンテナ全体
#define PI (acos(-1))  // 円周率pi
/* 変数入出力 read, write */
template <typename T>	// 1変数
void read(T& x) {
    cin >> x;
}
template <typename T, typename T0>	// 2変数
void read(T& x, T0& y) {
    cin >> x >> y;
}
template <typename T, typename T0, typename T1>	// 3変数
void read(T& x, T0& y, T1& z) {
    cin >> x >> y >> z;
}
template <typename T, typename T0, typename T1, typename T2>	// 4変数
void read(T& x, T0& y, T1& z, T2& w) {
    cin >> x >> y >> z >> w;
}
template <typename T>	// 1変数
void write(T& x) {
    cout << x << endl;
}
template <typename T, typename T0>	// 2変数
void write(T& x, T0& y) {
    cout << x << " " << y << endl;
}
template <typename T, typename T0, typename T1>	// 3変数
void write(T& x, T0& y, T1& z) {
    cout << x << " " << y << " " << z << endl;
}
template <typename T, typename T0, typename T1, typename T2>	// 4変数
void write(T& x, T0& y, T1& z, T2& w) {
    cout << x << " " << y << " " << z << " " << w << endl;
}
// vectorの出力
template <typename T>
void printvec(const vector<T> &data) {
for (const auto elm : data) {
    cout << elm << " ";
}
cout << endl;
}


int main(int argc, char const *argv[])
{
    ll h, w; read(h, w);
    ll ans = w * (h / 2);
    if (h % 2 == 1) ans += (ll)((ld)w / (ld)2 + 0.9999999999);
    if (h == 1 || w == 1) ans = 1;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
//転がす方向を決める処理と実際に転がす処理を分けると楽ちん。
//vec == 3は下面じゃないからね！！！
#include<iostream>
using namespace std;

int n;
int t, f;

int dy[4] = {1,0,-1,0};
int dx[4] = {0,1,0,-1};
int tfrbl[7][4] = {{0},{3,5,4,2},{3,1,4,6},{6,5,1,2},{1,5,6,2},{3,6,4,1},{3,2,4,5}};	//側面右回り

//tfrblのどれを下にするか(f=0,r=1,b=2,l=3で指定)、そしたら転がす。
//仕様がこんがらがる。補正の補正の…うわぁぁぁ。
//vec = 盤面におけるサイコロの移動方向、zure = 今、前面がtfrbl[t][zure]となっている。
void goron(int vec, int zure, int &t, int &f) {
	int p = tfrbl[t][(vec+zure+2)%4];	//tの変化は、転がす方向とずれに影響(というより、下にする面の値に影響)
	int q;
	//fの変化は、転がす方向にのみ影響
	if ( vec == 0 )
		q = t;
	if ( vec == 1 || vec == 3 )
		q = f;
	if ( vec == 2 )
		q = 7-t;
		
	t = p;
	f = q;
}

int main() {
	while( cin >> n ) {
		if ( !n ) break;
		int high[300][300] = {0}, cy = 114, cx = 114;
		int num[300][300] = {0};
		while(n--) {
			cin >> t >> f;
			int py = cy, px = cx;
			while(high[py][px]) {
				int i, index = -1;
				int zure;
				//例：t = 1, f = 4ならzure = 2になる
				for( zure = 0; zure < 4; zure++ ) {
					if ( tfrbl[t][zure] == f )
						break;
				}
				
				//i, index : 盤面におけるサイコロの移動方向
				for( i = 0; i < 4; i++ ) {
					//転がる条件(下にする面の値は、tと転がす方向だけでなく向きにも影響される。)
					if ( high[py+dy[i]][px+dx[i]] < high[py][px] && tfrbl[t][(i+zure)%4] >= 4 )
						if ( index == -1 || tfrbl[t][(i+zure)%4] > tfrbl[t][(index+zure)%4] ) {
							index = i;
						}
				}
				//cout << index << endl;
				if ( index == -1 )
					break;
				//転がす( dy[i], dx[i] )進むために、tfrbl[(index+zure)%4]が下になるように転がす。
				//同じt,fにおいて、同じ面を下にして転がしても、実際に転がす方向によって、次のt,fが変わるので要注意。
				goron(index, zure, t, f);
				py += dy[index]; px += dx[index];
			}
			high[py][px]++;
			num[py][px] = t;
			//cout << py << " " << px << " " << t << " " << f << endl;
		}
		
		int count[7] = {0};
		for( int i = 0; i < 300; i++ ) {
			for( int j = 0; j < 300; j++ ) {
				count[num[i][j]]++;
			}
		}
		
		for( int i = 1; i < 6; i++ ) {
			cout << count[i] << " ";
		}
		cout << count[6] << endl;
	}
	return 0;
}

Measured memory_bytes: 1872
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    let n: i32 = sc.read();

    println!("{}", n + n * n + n * n * n);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 2136
if __name__ == "__main__":
    n = int(input())
    keys = list(map(int, input().split()))
    for i, key in enumerate(keys, 1):
        print("node {}: key = {}, ".format(i, key), end="")
        if i//2:
            print("parent key = {}, ".format(keys[i//2-1]), end="")
        if 2*i-1 < n:
            print("left key = {}, ".format(keys[2*i-1]), end="")
        if 2*i < n:
            print("right key = {}, ".format(keys[2*i]), end="")
        print()


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

int n,m,q;
int g[2010][2010];
int x,y,x2,y2;

int tmp1[2010],tmp2[2010],tmp3[2010];
int sum1[2010][2010],sum2[2010][2010],sum3[2010][2010];
//2 竖 1 横 

void solve() {
	int k1,k2,k3;
	k1=sum1[x2][y2]-sum1[x-1][y2]-sum1[x2][y-1]+sum1[x-1][y-1];
	k2=sum2[x2][y2]-sum2[x][y2]-sum2[x2][y-1]+sum2[x][y-1];
	k3=sum3[x2][y2]-sum3[x-1][y2]-sum3[x2][y]+sum3[x-1][y];
//	cout<<k1<<" "<<k2<<" "<<k3<<endl;
	cout<<k1-k2-k3<<endl;
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=n;i++) {
		tmp1[0]=tmp2[0]=tmp3[0]=0;
		for (int j=1;j<=m;j++) {
			char c;
			cin>>c;
			g[i][j]=c-'0';
			tmp1[j]=tmp1[j-1]+g[i][j];
			tmp2[j]=tmp2[j-1];
			tmp3[j]=tmp3[j-1];
			if (g[i][j]) {
				tmp2[j]+=g[i-1][j];
				tmp3[j]+=g[i][j-1];
			}
			sum1[i][j]=sum1[i-1][j]+tmp1[j];
			sum2[i][j]=sum2[i-1][j]+tmp2[j];
			sum3[i][j]=sum3[i-1][j]+tmp3[j];
//			printf("%d %d %d %d %d\n",i,j,sum1[i][j],sum2[i][j],sum3[i][j]);
		}
	}
	while (q) {
		q--;
		scanf("%d%d%d%d",&x,&y,&x2,&y2);
		solve();
	}
	return 0;
}

Measured memory_bytes: 64896
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;


int main(){
    ll n;cin>>n;
    ll f[1000][10],p[1000][11];
    rep(i,0,n)rep(j,0,10)cin>>f[i][j];
    rep(i,0,n)rep(j,0,11)cin>>p[i][j];
    ll MAX=-99999999999,cn,an;
    for(int i=1;i<(1<<10);i++){
        an=0;
        rep(j,0,n){
            cn=0;
            rep(k,0,10){
                if((i&(1<<k))&&f[j][k])cn++;
            }
            an+=p[j][cn];
        }
        MAX=max(MAX,an);
    }
    cout<<MAX<<endl;
}







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

int main(){
    string word, com, p;
    int q,a,b;
    cin >> word >> q;
    for(int t = 0; t < q; t++){
        cin >> com >> a >> b;
        if(com == "print"){
            cout << word.substr(a, b-a+1) << endl; 
        }
        else if (com =="reverse"){
            string s = word.substr(a, b-a+1);
            int n = s.size();
            for(int i = 0; i < n; i++){
                word[i+a] = s[n-i-1];
            }
        }
        else if (com == "replace"){
            cin >> p;
            word = word.replace(a, b-a+1, p);
        }
    }
    return 0;
}


Measured memory_bytes: 3196
N = int(input())
A = list(map(int, input().split()))
ind = list(range(1, N+1))


B = [0] * (N + 1)
for i in reversed(range(1, N + 1)):
    if i > N // 2:
        B[i] = A[i - 1]
        continue

    cnt = 0
    x = i * 2
    while x <= N:
        cnt += B[x]
        x += i
    cnt %= 2
    B[i] = cnt ^ A[i - 1]


ans = [i for i in range(1, N+1) if B[i] == 1]
print(len(ans))
if ans:
    print(*ans)


Measured memory_bytes: 21556
yen_500_count = gets.to_i
yen_100_count = gets.to_i
yen_50_count = gets.to_i
sum = gets.to_i
count = 0

(0..yen_500_count).each do |i|
  (0..yen_100_count).each do |j|
    (0..yen_50_count).each do |k|
      count += 1 if i * 500 + j * 100 + k * 50 == sum
    end
  end
end

p count


Measured memory_bytes: 1916
#include <iostream>
#include <string>

using namespace std;

int main() {
    string str;
    cin >> str;
    int min_ans = str.size();
    for(int i=0; i<26; i++) {
        char cur_char=(char)('a'+i);
        // cout << "cur_char = " << cur_char << endl;
        string cur_str=str;
        for(int j=str.size(); j>0; j--) {
            // cout << cur_str << endl;

            string tmp;
            bool flag=true;
            for(int k=0; k<j-1; k++) {
                if(cur_str[k+1]==cur_char || cur_str[k]==cur_char) {
                    tmp.append(1, cur_char);
                } else {
                    tmp.append(1, cur_str[k]);
                }
                if(flag) {
                    if(cur_str[k]!=cur_char) {
                        flag=false;
                    }
                }
            }
            if(flag) {
                if(cur_str[j-1]!=cur_char) {
                    flag=false;
                }
            }
            
            cur_str = tmp;
            
            if(flag) {
                if(min_ans>str.size()-j) {
                    min_ans = str.size()-j;
                }
                // cout << min_ans << endl;
                break;
            }
        }
    }
    
    cout << min_ans << endl;

    return 0;
    
}

Measured memory_bytes: 256
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    a,b = INTM()
    if a>b:
        print(a-1)
    else:
        print(a)
if __name__ == '__main__':
    do()

Measured memory_bytes: 3060
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define ck(a,b) (0<=a&&a<b)
using namespace std;
int dx[]={1,-1,0,1},dy[]={0,1,1,1};
int rec(int c[5][4],int n){
	int nc[5][4],p=n;
	rep(i,n)rep(d,4){
		int x=i/4,y=i&3,ny=x+dy[d],nx=y+dx[d],r,use,z;
		if(ck(ny,5)&&ck(nx,4)&&4*ny+nx<n&&c[x][y]==c[ny][nx]){
			use=c[x][y];
			c[x][y]=c[ny][nx]=0;
			z=0;
			rep(j,n-2){
				while(c[j+z>>2][j+z&3]==0)z++;
				nc[j/4][j&3]=c[j+z>>2][j+z&3];
			}
			c[x][y]=c[ny][nx]=use;
			r=rec(nc,n-2);
			if(p>r)p=r;
			if(r==0)return 0;
		}
	}
	return p;
}
int main(){
	int n,c[5][4]; cin>>n;
	while(n--){
		rep(i,5)rep(j,4)cin>>c[i][j];
		cout<<rec(c,20)<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    int num=scan.nextInt();
    int tako[]=new int[num];
    int Ans=0;
    for(int a=0; a<num; a++){
      tako[a]=scan.nextInt();
    }
    if(num==2){
      Ans=tako[0]*tako[1];
    }else{
      for(int a=0; a<num-1; a++){
        for(int b=a+1; b<num; b++){
          Ans+=tako[a]*tako[b];
        }
      }
    }
    System.out.println(Ans);
  }
}

Measured memory_bytes: 23124
# C - Unification

S = str(input())

zeroCnt = 0
oneCnt = 0
ans = 0
for i in range(len(S)):
    if S[i]=='0':
        if oneCnt==0:
            zeroCnt += 1
        else:
            ans += 2
            oneCnt -= 1
    else:
        if zeroCnt==0:
            oneCnt += 1
        else:
            ans += 2
            zeroCnt -= 1

print(ans)



Measured memory_bytes: 3188
loop do
   break if (n = gets.to_i) == 0
   db = []
   n.times do
      id,p,q = gets.split(" ").map{|x| x.to_i}
      info = db.assoc id
      if info == nil # add new
         db.push [id,p * q]
      else
         info[1] += p * q
      end
   end
   million_over = []
   db.each do |id,sale|
      million_over.push id if sale >= 1_000_000
   end
   if million_over.empty? # no match
      puts "NA"
   else
      million_over.each do |id|
         puts id
      end
   end
end

Measured memory_bytes: 2528
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int[] numList = new int[N];
        for (int i = 0; i < N; i++) {
            numList[i] = Integer.parseInt(sc.next());
        }

        int r = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                r += numList[i] * numList[j];
            }
        }
        System.out.println(r);
    }
}

Measured memory_bytes: 23764
// B - Judge Status Summary
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
using namespace std;

int main(){
    int n;
    cin >> n;
    string s;
    int ac=0, wa=0, tle=0, re=0;
    rep(i, n){
        cin >> s;
        if(s[0] == 'A') ac++;
        else if(s[0] == 'W') wa++;
        else if(s[0] == 'T') tle++;
        else re++; 
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
int main(){
  int n,ans=0;
  cin>>n;
  int v[n];
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  int c[n];
  for(int i=0;i<n;i++){
    cin>>c[i];
  }
  int x[n];
  for(int i=0;i<n;i++){
    x[i]=v[i]-c[i];
  }
  for(int i=0;i<n;i++){
    if(x[i]>0)
    ans+=x[i];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256