akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    
    int n;
    cin >> n;
    vector<int> a(n);
    int s = 0;
    rep(i,n){
        cin >> a[i];
        s += abs(a[i]);
    }
    SORT(a);
    if(a[0] >= 0){
        cout << s-2*a[0] << endl;
        int x = a[0];
        rep(i,n-2){
            cout << x << " " << a[i+1] << endl;
            x = x-a[i+1];
        }
        cout << a[n-1] << " " <<  x << endl;
    }else if(a[n-1] < 0){
        cout << s+2*a[n-1] << endl;
        int x = a[n-1];
        rep(i,n-1){
            cout << x << " " << a[n-2-i] << endl;
            x = x-a[n-2-i];
        }
        //cout << a[n-1] - x << endl;
    }else{
        cout << s << endl;
        //int x = a[0];
        for(int i = 1;i<n-1;i++){
            if(a[i] >= 0){
                cout << a[0] << " " << a[i] << endl;
                a[0] -= a[i];
            }
        }
        for(int i = 0;i<n-1;i++){
            if(a[i] < 0){
                cout << a[n-1] << " " << a[i] << endl;
                a[n-1] -= a[i];
            }
        }
    }





    
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://diverta2019-2.contest.atcoder.jp/tasks/diverta2019_2_b

Measured memory_bytes: 2688
#include<stdio.h>
int main(){
  int h,w;
  scanf("%d%d",&h,&w);
  char a[h+3][w+3];
  int i,j;
  for(i=0;i<=h+1;i++){
    if(i==0 || i==h+1){
      for(j=0;j<=w+1;j++)
        a[i][j]='#';
    }
    else{
      for(j=0;j<=w;j++)
        scanf("%c",&a[i][j]);
      a[i][0]='#';
      a[i][w+1]='#';
    }
  }
  for(i=0;i<=h+1;i++){
    for(j=0;j<=w+1;j++)
      printf("%c",a[i][j]);
    puts("");
  }
  return 0;
}


Measured memory_bytes: 1624
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

N,K = map(int,input().split())

aa=[list(map(int,input().split())) for i in range(N)]
aa.sort()

num = 0
for a,b in aa:
	num += b
	if num >= K:
		print(a)
		sys.exit()

Measured memory_bytes: 28492
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {FIN
    
    int h, w, i;
    while (cin >> h >> w, h or w) {
        for (i = 0; i < h; i++)
            cout << string(w, '#') << "\n";
        cout << "\n";
    }
    
    return 0;
}


Measured memory_bytes: 3204
#include <stdio.h>
#include <math.h>
int main() {
    int n,z,w;
    scanf("%d %d %d",&n,&z,&w);
    int a[n];
    for(int i = 0;i < n;i++) scanf("%d",&a[i]);
    if(n ==1) printf("%d",abs(w - a[n-1]));
    else if(abs(w-a[n-1]) > abs(a[n-2]-a[n-1])) printf("%d",abs(w - a[n-1]));
    else printf("%d",abs(a[n-2] - a[n-1]));
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main()
{   
    int a[3][3];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    int x[3],y[3];
    x[0]=0;
    for(int i=0;i<3;i++) y[i]=a[0][i]-x[0];
    for(int i=0;i<3;i++) x[i]=a[i][0]-y[0];
    bool good=true;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(x[i]+y[j]!=a[i][j]) good=false;
        }
    }
    if(good) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
using System;

class Diverta_2019_B
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int R = int.Parse(input[0]);
        int G = int.Parse(input[1]);
        int B = int.Parse(input[2]);
        int N = int.Parse(input[3]);

        int max_r = N / R;
        int max_g = N / G;

        long count=0;

        for (int i = 0; i <= max_r; i++)
        {
            for (int j = 0; j <= max_g; j++)
            {
                int last = N - (i * R + j * G);
                if (last < 0) break;

                if (last % B == 0) {
                    count++;
                }
            }
        }

        Console.WriteLine(count);
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <string>
 
using namespace std;
 
int main(){
  int n;
  string S;
  string T;
  cin >> n>> S>> T;
  
  for(int i=0; i<n; ++i)
    cout << S[i]<< T[i];
  
 return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
std::vector<int> z_algorithm(std::string s) {
    int sz = s.size();
    std::vector<int> res(sz);
    res[0] = sz;
    int i = 1, j = 0;
    while(i < sz) {
        while(i+j < sz && s[j] == s[i+j]) ++j;
        res[i] = j;
        if(j == 0) {
            ++i;
            continue;
        }
        int k = 1;
        while(i+k < sz && k+res[k] < j) {
            res[i+k] = res[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return res;
}
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  string s; cin >> s;
  int ma = 0;
  for(int i=0;i<n;++i) {
    vector<int> d = z_algorithm(s.substr(i, n));
    int sz = n - i;
    for(int j=0;j<sz;++j) {
      ma = max(ma, min(j, d[j]));
    }
  }
  cout << ma << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> now(N);
	for (int i = 0; i < N; i++) {
		now[i] = i;
	}
	for (int i = 0; i < M; i++) {
		int a;
		cin >> a;
		now[a] = -1;
	}
	int ans = 0;
	while (now.size() > 1) {
		vector<int> nxt;
		for (int i = 0; i < now.size(); i += 2) {
			if (now[i] == -1) nxt.push_back(now[i + 1]);
			else if (now[i + 1] == -1) nxt.push_back(now[i]);
			else {
				nxt.push_back(now[i]);
				ans++;
			}
		}
		now = nxt;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
inline char *ans(int X,int Y){
    if(Y&1)
        return "No";
    int A,B=Y/2-X;
    A=X-B;
    if(A<0||B<0)
        return "No";
    if(A*2+B*4==Y)
        return "Yes";
    return "No";
}
int main(){
    int X,Y;
    cin>>X>>Y;
    cout<<ans(X,Y);
    return 0;
}

Measured memory_bytes: 3584
#!/usr/bin/env python3
import sys


def solve(S: int):
    S =str(S)[::-1]
    MOD = 2019
    mod_l = [int(0)]*2019
    mod_l[0] = 1
    prev = 0
    for x in range(len(S)):
        k = int(S[x]) * pow(10, x, MOD) % MOD + prev
        mod_l[k%2019] += 1
        prev = k%2019

    s = sum([x*(x-1)//2 for x in mod_l])
    print(s)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 71500
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long res = 0;
        for(int i=1; i<=n; i++) {
            if(i%3 != 0 && i%5 != 0) res+=i;
        }
        System.out.println(res);


    }
}

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

int main()
{
    int n, ans = INT_MAX;
    cin>>n;
    vector<int> h(n), dp(n,INT_MAX);
    for(auto& x:h) cin>>x;
    dp[0] = 0;
    for(int i=1; i<n; i++)
    {
        int p = INT_MAX, q = INT_MAX;
        if( i>0 ) p = abs(h[i]-h[i-1])+dp[i-1];
        if( i>1 ) q = abs(h[i]-h[i-2])+dp[i-2];
        dp[i] = min( p,q );
    }
    cout<<dp[n-1]<<"\n";
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int results[1001][1001];

int lcs(string x, string y)
{
    // initialize
    for (int i = 0; i < 1001; ++i) {
        for (int j = 0; j < 1001; ++j)
            results[i][j] = 0;
    }

    int maxlcs = 0;
    for (int i = 1; i <= x.length(); ++i) {
        for (int j = 1; j <= y.length(); ++j) {
            if (x[i-1] == y[j-1])
                results[i][j] = results[i-1][j-1] + 1;
            else
                results[i][j] = max(results[i-1][j], results[i][j-1]);

            if (maxlcs < results[i][j])
                maxlcs = results[i][j];
        }
    }
    return maxlcs;
}

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

    vector<string> x(n);
    vector<string> y(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    for (int i = 0; i < n; ++i)
        cout << lcs(x[i], y[i]) << '\n';
}



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

int main(){
	int n,m;
	int c[300],stats[300][3];
	string s;
	while(cin >> n >> m){
		int dp[301][301][3] = {};
		getchar();
		for(int i = 0;i < n;i++) {
			getline(cin,s);
			cin >> c[i] >> stats[i][0] >> stats[i][1] >> stats[i][2];
			getchar();
		}
		for(int i = 1;i <= n;i++){
			for(int j = 0;j <= m;j++){
				for(int k = 0;k < 3;k++){
					if(j - c[i - 1] >= 0) dp[i][j][k] = max(dp[i - 1][j][k],dp[i][j - c[i - 1]][k] + stats[i - 1][k]);
					else dp[i][j][k] = dp[i - 1][j][k];
				}
			}
		}
		int ma = 0;
		for(int i = 0;i < 3;i++) {
			ma = max(ma,dp[n][m][i]);
		}
		cout << ma << endl;
	}
	return 0;
}

Measured memory_bytes: 4248
#include <stdio.h>
#define N 36

typedef struct{
    int num;
    char type;
}Card;

int main(){
    Card in[N],bubble[N],selection[N];
    int n,i,j,minj,flag=0;
    Card stac,stac2;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf(" %c%d",&in[i].type,&in[i].num);
        bubble[i]=in[i];
        selection[i]=in[i];
    }
    
    //bubble
    for(i=0;i<n;i++){
        for(j=n-1;j>i;j--){
            if(bubble[j].num<bubble[j-1].num){
                stac=bubble[j];
                bubble[j]=bubble[j-1];
                bubble[j-1]=stac;
            }
        }
    }
    //bubble end
    
    //selection
    for(i=0;i<n;i++){
        minj=i;
        for(j=i;j<n;j++){
            if(selection[j].num<selection[minj].num){
                minj=j;
            }
        }
        stac=selection[minj];
        selection[minj]=selection[i];
        selection[i]=stac;
    }
    //selection end
    
    //bubble aply
    for(i=0;i<n-1;i++){
        printf("%c%d ",bubble[i].type,bubble[i].num);
        if(bubble[i].type!=selection[i].type)flag++;
    }
    printf("%c%d\nStable\n",bubble[n-1].type,bubble[n-1].num);
    //bubble aply end
    
    //selection aply
    for(i=0;i<n-1;i++){
        printf("%c%d ",selection[i].type,selection[i].num);
    }
    printf("%c%d\n",selection[n-1].type,selection[n-1].num);
    if(flag==0)printf("Stable\n");
    else printf("Not stable\n");
    
    return 0;

}

Measured memory_bytes: 608
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(k,a,b) for(int k=(a); k < (b); k++)
#define FORE(k,a,b) for(int k=(a); k <= (b); k++)
#define REP(k,a) for(int k=0; k < (a); k++)

#define ALL(c) (c).begin(), (c).end()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define RANGE(lb, x, ub) ((lb) <= (x) && (x) < (ub))

#define dump(x) cerr << #x << ": " << (x) << endl;

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int INF = 1000000000;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main(void) {
  int p,q,r; cin >> p >> q >> r;
  cout << min(p+q, min(q+r, p+r)) << endl;
  return 0;
}


Measured memory_bytes: 888
// problem: "https://atcoder.jp/contests/abc148/tasks/abc148_f"

#include<bits/stdc++.h>

using namespace std;

vector<int> lvl_heights(vector<int>G[],int n,int r)
{
    vector<int>V(n+1,-1);
    V[r] = 0;

    queue<int>Q;
    Q.push(r);

    while(!Q.empty())
    {
        int p = Q.front();
        Q.pop();

        int i;
        for(i=0;i!=G[p].size();i++)
        {
            if(V[G[p][i]] == -1)
            {
                V[G[p][i]] = V[p]+1;
                Q.push(G[p][i]);
            }
        }
    }

    return V;
}


int TagTree(vector<int>G[],int n,int u,int v)
{
    if(n == 2)
        return 0;

    vector<int>A = lvl_heights(G,n,v);
    vector<int>T = lvl_heights(G,n,u);      // define

    int i,m;
    m = -1;
    for(i=1;i!=n+1;i++)
    {
        if(G[i].size() == 1)
        {
            if(A[G[i][0]] >= T[G[i][0]])
            {
                m = max(m,A[G[i][0]]);
            }
        }
    }

    return m;
}

int main()
{
    int n,v,u;
    cin>>n>>u>>v;

    int i,x,y;
    vector<int>G[n+1];

    for(i=1;i!=n;i++)
    {
        cin>>x>>y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    cout<<TagTree(G,n,u,v);      // define

    return 0;
}


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

int main() {
  string S;
  cin >> S;
  
  int N = S.size();
  
  bool Ans = true;
  
  for(int i=0;i<N;i++){
    if(i%2==0){
      if(S.at(i) != 'R'&&S.at(i)!='U'&&S.at(i)!='D'){
        Ans = false;
      }
    } else {
      if(S.at(i) != 'L'&&S.at(i)!='U'&&S.at(i)!='D'){
        Ans = false;
      }
    }
  }
  
  if(Ans == true){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3580
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    double d;
    cin >> d;
    cout << fixed;
    cout << setprecision(10);
    if(d < 1.0){
        cout << d*sqrt(2) << endl;
    }else{
        cout << max(d*sqrt(2), floor(d+1)) << endl;
    }
    return 0;
}

Measured memory_bytes: 3236
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    int n;
    cin >> n;
    vector<ll> a(3*n);
    rep(i, 3 * n) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int l = 0;
    int r = 3 * n - 2;
    ll ans = 0;
    while(1) {
        if ( l >= r ) break;
        ans += a[r];
        ++l;
        r -= 2LL;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
/*
[dwacon5th-prelims] E - Cyclic GCDs
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 1e5;
const ll MOD = 998244353;

int N;
int a[MAX_N];

ll gcd(ll a, ll b) {
    while (b > 0) {
        swap(a %= b, b);
    }
    return a;
}

ll solve() {
    sort(a, a + N);
    ll ans = 1;
    for (int i = 0; i < N; i++) {
        (ans *= gcd(a[i], i)) %= MOD;
    }
    return ans;
}

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

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 768
import time

N, Q = map(int, input().split())
SegTree = [0 for i in range(4*N)]

def modify(i, left, right, value, pos=-1):
    global SegTree
    if left==right:
        if pos != -1:
            SegTree[i] = value
        else:
            SegTree[i] = 2147483647
        return

    mid = int((left+right)/2)
    if pos==-1 or pos<=mid:
        modify(i*2, left, mid, value, pos)
    if pos==-1 or pos>mid:
        modify(i*2+1, mid+1, right, value, pos)
    
    SegTree[i] = min(SegTree[i*2], SegTree[i*2+1])

def query_min(i, L, R, left, right):
    if right < L or R < left:
        return 2147483647
    if left<=L and R<=right:
        return SegTree[i]
    mid = int((L+R)/2)
    return min(query_min(2*i, L, mid, left, right),
               query_min(2*i+1, mid+1, R, left, right))

modify(i=1, left=0, right=N-1, value=0, pos=-1) #init

for querys in range(Q):
    t, a, b = map(int, input().split())
    if t == 0:
        modify(i=1, left=0, right=N-1, pos=a, value=b)
    else:
        print( query_min(i=1, L=0, R=N-1, left=a, right=b) )

Measured memory_bytes: 10972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


struct Edge {
    ll to;
    ll weight;
    Edge(ll t, ll w) : to(t), weight(w) { }
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, ll>;


typedef vector<vector<int> > Matrix;

const int INF = 100000000;
Matrix d;

void warshall_floyd(int n) { // nは頂点数
    for (int i = 0; i < n; i++)      // 経由する頂点
        for (int j = 0; j < n; j++)    // 開始頂点
            for (int k = 0; k < n; k++)  // 終端
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}

ll modnum = 1e9+7;

int main() {
    ll n; cin >> n;
    vector<ll> t(n), a(n);
    rep(i, n) cin >> t[i] >> a[i];

    ll aa = 0, tt = 0;
    rep(i, n) {
        if(aa < a[i]) aa = a[i];
        if(tt < t[i]) tt = t[i];
        
        ll diva = (aa+a[i]-1)/a[i];
        aa = diva * a[i];
        ll tmpt = diva * t[i];
        if(tmpt >= tt) {
            tt = tmpt;
        } else {
            ll divt = (tt+t[i]-1)/t[i];
            tt = divt * t[i];
            aa = divt * a[i];
        }

    }

    ll ans = aa + tt;

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 

using namespace std;

long long X, K, D;

int main(){
	cin >> X >> K >> D;
	X = abs(X);

	long long num = X/D;
	if (num >= K) {
		//0までたどり着けない
		//全力で0に近づく
		cout << X - K * D << endl;
	} else {
		K -= num;
		X -= num * D;
		if(K % 2 == 0) {
			cout << X << endl;
		} else {
			cout << abs(X-D) << endl;
		}
	}

}


Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#include<vector>
struct UF{
	int n;
	vector<int>parent,rank;
	UF(int n_=0):n(n_),parent(n_),rank(n_,0)
	{
		for(int i=0;i<n_;i++)parent[i]=i;
	}
	int find(int a)
	{
		return parent[a]!=a?parent[a]=find(parent[a]):a;
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
	bool unite(int a,int b)
	{
		a=find(a),b=find(b);
		if(a==b)return false;
		if(rank[a]<rank[b])
		{
			parent[a]=b;
		}
		else
		{
			parent[b]=a;
			if(rank[a]==rank[b])rank[a]++;
		}
		return true;
	}
};
#include<vector>
#include<functional>
#include<limits>
template<typename T>
struct segtree{
	function<T(T,T)>calcfn,updatefn;
	int n;
	T defvalue;
	vector<T>dat;
	segtree(int n_=0,T defvalue_=numeric_limits<T>::max(),
		function<T(T,T)>calcfn_=[](T a,T b){return a<b?a:b;},
		function<T(T,T)>updatefn_=[](T a,T b){return b;}
	):defvalue(defvalue_),calcfn(calcfn_),updatefn(updatefn_)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,defvalue);
	}
	void copy(const vector<T>&v)
	{
		for(int i=0;i<v.size();i++)dat[i+n-1]=v[i];
		for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[i*2+1],dat[i*2+2]);
	}
	void update(int i,T a)
	{
		i+=n-1;
		dat[i]=updatefn(dat[i],a);
		while(i>0)
		{
			i=(i-1)/2;
			dat[i]=calcfn(dat[2*i+1],dat[2*i+2]);
		}
	}
	T query(int a,int b,int i=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		if(r<=a||b<=l)return defvalue;
		else if(a<=l&&r<=b)return dat[i];
		else
		{
			return calcfn(
				query(a,b,i*2+1,l,(l+r)/2),
				query(a,b,i*2+2,(l+r)/2,r)
			);
		}
	}
};
int n;
long d,a[2<<17];
vector<pair<long,int> >A;
main()
{
	cin>>n>>d;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		A.push_back(make_pair(a[i],i));
	}
	priority_queue<pair<long,pair<int,int> > >P;
	sort(A.begin(),A.end());
	segtree<pair<long,int> >segl(n,make_pair((long)9e18,0),[](pair<long,int>a,pair<long,int>b){return a.first<b.first?a:b;});
	segtree<pair<long,int> >segr(n,make_pair((long)9e18,0),[](pair<long,int>a,pair<long,int>b){return a.first<b.first?a:b;});
	for(int i=0;i<n;i++)
	{
		pair<long,int>L=segl.query(0,A[i].second),R=segr.query(A[i].second,n);
		if(L.first<9e18)
		{
			P.push(make_pair(-L.first-A[i].first-d*A[i].second,make_pair(L.second,A[i].second)));
		}
		if(R.first<9e18)
		{
			P.push(make_pair(-R.first-A[i].first+d*A[i].second,make_pair(R.second,A[i].second)));
		}
		segl.update(A[i].second,make_pair(A[i].first-d*A[i].second,A[i].second));
		segr.update(A[i].second,make_pair(A[i].first+d*A[i].second,A[i].second));
	}
	UF uf(n);
	long ans=0;
	while(!P.empty())
	{
		long cost=-P.top().first;
		int x=P.top().second.first,y=P.top().second.second;
		P.pop();
		if(uf.unite(x,y))
		{
			ans+=cost;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 32620
function main(input) {
   input = input.trim();
  const a = input.split(" ").map(Number);
 
 console.log((a[0]*a[1])%3==0||(a[0]+a[1])%3==0?"Possible"
			:"Impossible");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29588
N = int(input())
s = input().strip()

types = ["S", "W"]

res = ""

def check(a, b, c, s):
    if s == 'o':
        if b == 'W':
            return a != c
        else:
            return a == c
    else:
        if b == 'W':
            return a == c
        else:
            return a != c

for t in types:
    circle = ""
    for tt in types:
        circle = t+tt
        for i in range(1, N-1):
            pre_a = circle[i-1]
            now_a = circle[i]
            if s[i] == 'o':
                if pre_a == now_a:
                    circle += "S"
                else:
                    circle += "W"
            else:
                if pre_a == now_a:
                  circle += "W"
                else:
                  circle += "S"
        is_ok = True
        is_ok *= check(circle[-1], circle[0], circle[1], s[0])
        is_ok *= check(circle[-2], circle[-1], circle[0], s[-1])

        if is_ok:
            print(circle)
            exit()

print(-1)


Measured memory_bytes: 3444
n,d=map(int,input().split())
x = []
nijou = set([i**2 for i in range(10000)])
for i in range(n):
	x.append([int(i) for i in input().split()])
ans = 0
for i in range(n-1):
	for j in range(i+1, n):
		if sum([(x[i][k] - x[j][k])**2 for k in range(d)]) in nijou:
			ans += 1
print(ans)

Measured memory_bytes: 4084
n = int(input())
s = str(input())
count = 0
sum_RGB = s.count("R") * s.count("G") * s.count("B")
for i in range(n):
    for j in range(i, n):  # rangeをiからにすることでループ減らせる
        # for k in range(n): # sum_RGBから減らしていくのでｋがi,jで決まる
        k = 2*j - i
        if k < n:
            a = (s[i], s[j], s[k])
            # print(a)
            a_set = set(a)
            # print(a_set)
            if len(a_set) == 3:
                count += 1

print(sum_RGB - count)

Measured memory_bytes: 80124
#include <bits/stdc++.h>
using namespace std;
long long dp[105][100005];
long long knapsack(int w[],int v[],int W,int n)
{
	if(W==0 || n==0) return 0;
	if(dp[n][W]!=-1) return dp[n][W];
	if(w[n-1]<=W){
		return dp[n][W] = max(v[n-1]+knapsack(w,v,W-w[n-1],n-1),knapsack(w,v,W,n-1));
	}
	else return dp[n][W] = knapsack(w,v,W,n-1);
}
int main() {
	int n,W;
	cin>>n>>W;
	int w[n],v[n];
	memset(dp,-1,sizeof dp);
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	cout<<knapsack(w,v,W,n)<<'\n';
}


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

int main () {
  int H, W;
  cin >> H >> W;
  vector<char> A(W);
    
    for (int i=0;i<H+2;i++) {
      for (int j=0;j<W+2;j++) {
        vector<char> B(W+2);
        if (i==0||i==H+1) {
          if(j==W+1) {
            B.at(j)='#';
            cout << B.at(j) << endl;
          }
          else {
            B.at(j)='#';
            cout << B.at(j);
          }
        }
        else {
          if(j==0) {
            B.at(j)='#';
            cout << B.at(j);
          }
          else if(j==W+1) {
            B.at(j)='#';
            cout << B.at(j) << endl;
          }
          else {
            cin >> A.at(j-1);
            cout << A.at(j-1);
          }
        }
      }
    }
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')
# ----------------------------------------------------------- #

s = S()
t = S()
if s == t[:-1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 72516
#include <stdio.h>
#include <string.h>
#define N 1001
int Z[N][N];
char X[N], Y[N];

int LCS (void);

int main() {
  int n, i, x;
 
  scanf("%d", &n);
  for(i=0;i<n;i++) {
    scanf("%s", X);
    scanf("%s", Y);
    x = LCS();
    printf("%d\n", x);
  }
  return 0;
}

int LCS(void) {
  int m, n, i, j;
 
  m = strlen(X);
  n = strlen(Y);
  for(i=0;i<=m;i++) Z[i][0] = 0;
  
  for(j=0;j<=n;j++) Z[0][j] = 0;
 
  for(i=1;i<=m;i++) {
    for(j=1;j<=n;j++) {
      if(X[i-1] == Y[j-1]) Z[i][j] = Z[i-1][j-1] + 1;
      else if(Z[i-1][j] >= Z[i][j-1]) Z[i][j] = Z[i-1][j];
      else Z[i][j] = Z[i][j-1];
    }
  }
  return Z[m][n];
}

Measured memory_bytes: 4516
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using lint = long long int;

int main()
{
	int A, B;
	cin >> A >> B;

	int diff = abs(A - B);
	if (diff % 2 == 0) {
		cout << min(A, B) + (diff / 2);
	}
	else {
		cout << "IMPOSSIBLE";
	}


	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[1000];
int main()
{
    a[0]=0;
    for(int i=1;i<=999;i++)
    {
        a[i]=a[i-1]+i;
    }
    int x,y;
    scanf("%d%d",&x,&y);
    int p1=lower_bound(a+1,a+1000,x)-a;
    for(int i=p1;;i++)
    {
        if(y+a[i]-x==a[i+1])
        {
            printf("%d\n",a[i]-x);
            return 0;
        }
    }
    return 0;
}


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


int main() {
  int n;
  cin >> n;
  map<int,int> list;
  for (int i=0; i<n; i++){
    int a;
    cin >>a;
    list[a]=i+1;
  }
  for (int j=1; j<=n;j++){
    cout << list[j] << " ";
    if(j==n) cout << endl;
  }
}

Measured memory_bytes: 5504
using System;
using System.Linq;

namespace _0557
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            long[,] dp = new long[n,21];
            dp[0,x[0]] = 1;
            for (int i = 1; i < n - 1; i++)
            {
                for (int j = 0; j <= 20; j++)
                {
                    if (dp[i - 1,j] > 0)
                    {
                        if (j + x[i] <= 20) dp[i,j + x[i]] += dp[i - 1,j];
                        if (0 <= j - x[i]) dp[i,j - x[i]] += dp[i - 1,j];
                    }
                }
            }
            Console.WriteLine(dp[n - 2,x[n - 1]]);
        }
    }
}


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

int main() {
  
  int a, b ; 
  cin >> a >> b ;
  
  int ans = 0 ; 
  
  for ( ; a <= b ; a++){
	int test = 0;
    int base = 1;
    
    for ( int i = 0 ; i <5 ; i++ ){
    	test += base*( (int)(to_string(a).at(i) - '0')) ;
        base *= 10 ;  
    }
      
      if ( a == test)
      //cout << a << ":" << test << endl ; 
        ans += 1 ;
    }
  cout << ans << endl ; 
  

  
}




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

int boo(int x, int y){
	if(x%y) return x%y -1;
	else return y - 1;
}

char foo(string str,int mk, int i){
	char ch, mozi[16] = "00adgjmptw", mozi1[8] = " .,!?";
	if(str[mk] - '0' == 1) ch = mozi1[(i - mk)%5];
	else if(((str[mk] - '0') == 7) || ((str[mk] - '0') == 9)) ch = mozi[str[mk] - '0'] + boo(i - mk, 4);
	else ch = mozi[str[mk] - '0'] + boo(i - mk, 3);
	return ch;
}

int main(){
	int N, mk, count, temp;
	int i, j, k;
	string str;
	char ch[2000];
	
	cin>>N;
	
	for(i = 0; i < N; i++){
		mk=0; count=0;
		cin>>str;
		for(j = 0; j < (int)str.size(); j++){
			if(str[j] == '0'){
				if(mk != j)ch[count++] = foo(str, mk, j);
				mk =  j + 1;
			}
		}
		
		for(j = 0; j < count; j++) cout<<ch[j];
		if(count)cout<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;

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

    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
    }

    int S, T;
    cin >> S >> T;
    S--, T--;

    vector<vector<int>> dist(N, vector<int>(3, 1e9));
    queue<pii> que;
    dist[S][2] = 0;
    que.push({S, 2});
    while (!que.empty()) {
        pii p = que.front();
        que.pop();
        int v = p.first, n1 = p.second;
        for (auto nv : G[v]) {
            int n2 = (n1 + 1) % 3;
            if (dist[nv][n2] < 1e9)
                continue;
            dist[nv][n2] = dist[v][n1] + (n2 == 0);
            que.push({nv, n2});
        }
    }

    cout << (dist[T][2] < 1e9 ? dist[T][2] : -1) << endl;
    return 0;
}


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

using namespace std;

#define int long long

const int mod = 1e9 + 7;

int bp(int a, int b) {
    if (b == 0) return 1;
    int val = bp(a, b / 2);
    if (b % 2) return (val * ((val * a) % mod)) % mod;
    return (val * val) % mod;
}

int divv(int a, int b) {
    return a * bp(b, mod - 2) % mod;
}

void solve() {
    int n, k;
    cin >> n >> k;
    int ans = 1;
    int tc1 = 1, tc2 = 1;
    for (int i = 0; i < min(k, n); ++i) {
        tc1 = (tc1 * (n - i)) % mod;
        tc1 = divv(tc1, 1 + i);
        tc2 = (tc2 * (n - 1 - i)) % mod;
        tc2 = divv(tc2, 1 + i);
        ans = (ans + tc1 * tc2) % mod;
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


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

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)


int main(void){
  int r,d,x;
  cin>>r>>d>>x;
  r(i,10){
    x=r*x-d;
    cout<<x<<endl;
  }

return 0;}


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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	int sum = 0;
	for (char c : s) {
		sum += c - '0';
		sum %= 9;
	}
	cout << (sum ? "No" : "Yes") << '\n';
}



Measured memory_bytes: 3744
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	auto path = vector<vector<int>>(n + 1, vector<int>());
	for(int i = 0; i < m; ++i){
		int a, b;
		cin >> a >> b;
		path[a].push_back(b);
		path[b].push_back(a);
	}
	auto ans = vector<int>(n + 1);
	auto q = queue<pair<int,int>>();
	q.push(make_pair(1,0));
	while(!q.empty()){
		auto p = q.front();
		q.pop();
		int c = p.first;
		int r = p.second;
		if(ans[c] != 0) continue;
		ans[c] = r;
		for(int i = 0; i < (int)path[c].size(); ++i){
			q.push(make_pair(path[c][i], c));
		}
	}
	cout << "Yes" << endl;
	for(int i = 2; i <= n; ++i){
		cout << ans[i] << endl;
	}
	return 0;
}

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

#define MOD 1000000007
class mll {
	unsigned long long val = 0;
public:
	mll(long long y = 0) : val(((y % MOD) + MOD) % MOD) {}
	mll operator + (const mll& y) { return mll(*this) += y; }
	mll& operator += (const mll& y) {
		val = (val + y.val) % MOD;
		return *this;
	}
	mll operator - (const mll& y) { return mll(*this) -= y; }
	mll& operator -= (const mll& y) {
		val = (val - y.val + MOD) % MOD;
		return *this;
	}
	mll operator * (const mll& y) { return mll(*this) *= y; }
	mll& operator *= (const mll& y) {
		val = (val * y.val) % MOD;
		return *this;
	}
	mll operator / (const mll& y) { return mll(*this) /= y; }
	mll& operator /= (const mll& y) {
		long long a = y.val, b = MOD, u = 1, v = 0;
		while (b) {
			long long t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		val = (((val * u) % MOD) + MOD) % MOD;
		return *this;
	}
	bool operator >= (const mll& y) {
		return this->val >= y.val;
	}
	mll pow(long long t) const {
		if (!t) return 1;
		mll a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	unsigned long long getVal() {
		return val;
	}


	friend ostream& operator <<(ostream& os, mll& y) {
		os << y.val;
		return os;
	}
};
#undef MOD


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

	mll ten = 10;
	mll q = ten.pow(100);

	ll N, K;
	cin >> N >> K;

	set<ll> S;
//	mll c = q * (K - 1);
	ll c = 0;
	for (ll i = K; i <= N + 1; i++) { // kosu
//		c += q;
		c += (N * (N + 1) / 2 - (N - i)*(N + 1 - i) / 2) - (i * (i - 1)) / 2 + 1;

//		for (ll j = (i * (i - 1)) / 2; j <= (N * (N + 1) / 2 - (N-i)*(N+1-i)/2); j++) {
//			mll p = c + j;
//			S.insert(p.getVal());
//		}
	}
	//	cout << S.size() << endl;
	cout << mll(c).getVal() << endl;
}


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

int main() {
 char c;
  cin >> c;
  if(c == 'a'||c == 'i'||c == 'u'||c == 'e'||c == 'o')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
}


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

ll value[100005];

int main() {
    ll N, T, count = 0;
    cin >> N >> T;
    for (int i = 0; i < N; i++) {
        cin >> value[i];
    }
    ll min_num = value[0], min_sub = 0;
    for (int i = 1; i < N; i++) {
        if (value[i] > min_num && min_sub < value[i] - min_num) {
            min_sub = value[i] - min_num;
        }
        else if (value[i] < min_num) {
            min_num = value[i];
        }
    }
    min_num = value[0];
    for (int i = 1; i < N; i++) {
        if (value[i] > min_num && min_sub == value[i] - min_num) count++;
        else if (value[i] < min_num) min_num = value[i];
    }
    cout << count << endl;
    return 0;
}

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

bool is_palindrome(string s) {
	string aux = s;
	reverse(s.begin(), s.end());
	return (aux == s);
}

int main() {
	string s;
	cin >> s;
	int n = s.size();
	if(is_palindrome(s) and is_palindrome(s.substr(0, (n-1)/2)) and is_palindrome(s.substr((n+1)/2, (n-1)/2)) ) {
		cout << "Yes";
	} else cout << "No";
	return 0;
}

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

typedef long long ll;
typedef int64_t i6;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 1; i <= n; ++i)
#define ALL(v) (v).begin(), (v).end()
#define Sort(x) sort(ALL(x))
#define Sort_rev(x) Sort(x);reverse(ALL(x))

template<typename V,typename T>
T find_num(V v, T num) {
    if ( find(ALL(v), num) == v.end() ) {
        return false;
    } else {
        return true;
    }
}

// π M_PI
// deg = rad*180/M_PI

int main() {
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    if ( n <= m ) {
        ans = 1;
    }

    cout << ( ans ? "unsafe" : "safe" ) << endl;
    return 0;
}


Measured memory_bytes: 3572
#include<stdio.h>
#include<string.h>
#define N 1000

int lcs(char x[], char y[])
{
  int m,n;
  int i,j;
  int c[N+1][N+1];

  m = strlen(x);
  n = strlen(y);

  for(i=0;i<=m;i++)
  {
    c[i][0] = 0;
  }
  for(j=0;j<=n;j++)
  {
    c[0][j] = 0;
  }

  for(i=1;i<=m;i++)
  {
    for(j=1;j<=n;j++)
    {
      if(x[i-1]==y[j-1])
      {
        c[i][j] = c[i-1][j-1]+1;
      }
      else if(c[i-1][j]<c[i][j-1])
      {
        c[i][j] = c[i][j-1];
      }
      else
      {
        c[i][j] = c[i-1][j];
      }
    }
  }
  return c[m][n];
}

int main()
{
  int n,i;
  char x[N],y[N];
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%s",x);
    scanf("%s",y);
    printf("%d\n",lcs(x,y));
  }
  return 0;
}



Measured memory_bytes: 5644
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C - Forbidden List
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_P = 100;
const int INF = 1 << 30;

/* typedef */

/* global variables */

bool used[MAX_P + 2];

/* subroutines */

/* main */

int main() {
  int x, n;
  scanf("%d%d", &x, &n);

  for (int i = 0; i < n; i++) {
    int pi;
    scanf("%d", &pi);
    used[pi] = true;
  }

  int mind = INF, minp = -1;
  for (int p = 0; p <= MAX_P + 1; p++)
    if (! used[p]) {
      int d = abs(p - x);
      if (mind > d) mind = d, minp = p;
    }

  printf("%d\n", minp);
  return 0;
}


Measured memory_bytes: 3220
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

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

int main()
{
    string s, t; cin >> s >> t;
    vector<int> index[26]; // 0-indexed
    int n = s.size();
    rep(si, n){
        char c = s[si];
        int ci = c-'a';
        index[ci].push_back(si);
        index[ci].push_back(si+n);
    }

    bool exists[26];
    fill_n(exists, 26, false);
    rep(ti, t.size()){
        char c = t[ti];
        exists[(c-'a')] = true;
    }
    rep(c, 26){
        if(exists[c] && index[c].size() == 0){
            cout << -1 << endl;
            return 0;
        }
        sort(index[c].begin(), index[c].end());
    }

    ll ans; // 0-indexed but the real answer is 1-indexed
    rep(i, t.size()){
        char ti = t[i];
        int idx = ti - 'a';
        if(i == 0){
            ans = index[idx][0];
            continue;
        }

        ll state = (ans % n);
        ll next = *(upper_bound(index[idx].begin(), index[idx].end(), state));
        ans += (next - state);
    }

    cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 4632
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll=long long;
using P=pair<int,int>;
int main() {
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    int aplan,bplan,abplan,waste;
    //all a
    if(2*c<b) aplan=a*x+c*y*2;
    else aplan=a*x+b*y;
    //all b
    if(2*c<a) bplan=b*y+c*x*2;
    else bplan=a*x+b*y;
    // ab
    if(x>y) abplan=2*c*y+a*(x-y);
    else abplan=2*c*x+b*(y-x);
    //waste
    waste=2*c*max(x,y);
    cout<<min(min(waste,aplan),min(bplan,abplan));

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    if (abs(a - c) <= d || (abs(a-b) <= d && abs(c-b) <= d)) cout << "Yes" << endl; 
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    long int s;
    int h,m;
    scanf("%ld",&s);
    m=s/60;
    s=s%60;
    h=m/60;
    m=m%60;
    printf("%d:%d:%ld\n",h,m,s);
        return 0;
}

Measured memory_bytes: 1836
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k;
int sum=1;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		if(sum<=k)sum+=sum;
		else sum+=k;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
ta=[]
t=0
a=0
ans=[[1,1]]
for i in range(n):
    p=[int(j) for j in input().split()]
    i=max(ans[-1][0]//p[0],ans[-1][1]//p[1])
    while True:
        if p[0]*i>=ans[-1][0] and p[1]*i>=ans[-1][1]:
            ans.append([p[0]*i,p[1]*i])
            break
        i+=1

print(sum(ans[-1]))

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

int n, a[1000002] = {0};
int evenity[1000002] = {0};


int is_two1() {
	if (n == 1) {
		if (a[0] == 2) return 1;
		else return 0;
	}
	if (a[0] == 0 && a[1] == 2 || a[0] == 2 && a[1] == 0) {
		int t = a[1];
		for(int i = 2; i < n; i++) {
			if (a[i] != t) return 0;
		}
		return 1;
	}
	return 0;
}
int is_two2() {
	if (n == 1) {
		if (a[0] == 2) return 1;
		else return 0;
	}

	if (a[n-1] == 0 && a[n-2] == 2 || a[n-1] == 2 && a[n-2] == 0) {
		int t = a[n-2];
		for(int i = 0; i < n-2; i++) {
			if (a[i] != t) return 0;
		}
		return 1;
	}
	return 0;
}

void fill_evenity() {
	int m = 2;
	for(; m < n; m *= 2) {
		for(int i = 0; i < n; i += m) {
			evenity[i]++;
		}
	}
}

void process_once() {
	for(int i = 0; i < n - 1; i++) {
		a[i] = abs(a[i + 1] - a[i]);
	}
}

int all_02() {
	for(int i = 0; i < n; i++) {
		if (a[i] == 1) return 0;
	}
	for(int i = 0; i < n; i++) {
		a[i] /= 2;
	}
	return 1;
}

int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
		char c;
		cin >> c;
		a[i] = (c - '0');
	}
	process_once();
	n--;
	int flag = 0;
	if (all_02()) flag = 1;
	fill_evenity();
	int m = n - 1;
	int s = 0, e = 0;
	for(int i = 0; i < n; i++) {
		if (i == 0 || i == n - 1) {
			s = (s + a[i]) % 2;
			continue;
		}
		e = e + evenity[m + 1 - i] - evenity[i];
		if (e > 0) {
			continue;
		} else {
			s = (s + a[i]) % 2;
		}
	}
	if (flag) cout << s * 2 << endl;
	else cout << s << endl;
}




Measured memory_bytes: 8192
n = raw_input()
input = n.split(" ")
n, x = input[0], input[1]
l = raw_input().split(" ")
current = 0
bounce = 1
for i in range(len(l)):
    current += int(l[i])
    if current <= int(x):
        bounce += 1
    else:
        break
print(bounce)


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

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 long long INF = 1LL << 60;

int main(){
  int a, b, c;
  cin >> a >> b >> c;

  cout << (a + b + c == 2 * max(a, max(b, c)) ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	
	//D
	int n, k;
	string s;
	cin >> n >> k;
	cin >> s;
	int seq[100001];
	int i;
	for (i = 0; i < 100001; i++) {
		seq[i] = 0;
	}
	int seqnum = 0;
	if (s[0] == '0') {
		seq[0] = 0;
		seqnum++;
	}
	i = 0;
	int counter = 0;
	int maxcounter;
	char seqnow = s[0];
	while (i < s.length()) {
		if (s[i] == seqnow) {
			seq[seqnum]++;
		}
		else {
			seqnum++;
			seqnow = s[i];
			seq[seqnum]++;
			//seqnum++;
		}
		i++;
	}
	//for (i = 0; i <= seqnum; i++) {
	//	cout << seq[i] << endl;
	//}
	seq[seqnum + 1] = 0;
	if (k >= (seqnum + (seqnum % 2)) / 2) {
		cout << s.length() << endl;
		return 0;
	}
	else {
		for (i = 0; i <= 2 * k; i++) {
			counter = counter + seq[i];
			//cout << counter << endl;
		}
		maxcounter = counter;
		for (i = 0; i < (seqnum + (seqnum % 2)) / 2 - k; i++) {
			counter = counter - seq[i * 2] - seq[i * 2 + 1];
			counter = counter + seq[i * 2 + 2 * k + 1] + seq[i * 2 + 2 * k + 2];
			//cout << counter << endl;
			if (maxcounter < counter)maxcounter = counter;
		}
		cout << maxcounter << endl;
		return 0;
	}

	//C
	/*string s;
	int i;
	int counter1 = 0, counter2 = 0;
	cin >> s;
	for (i = 0; i < s.size(); i++) {

		if (i % 2 == 0) {
			if (s[i] == '1') {
				counter1++;
				//cout << 'a';
			}
			else {
				counter2++;
				//cout << 'i';
			}
		}
		else {
			if (s[i] == '0') {
				counter1++;
				//cout << 'u';
			}
			else {
				counter2++;
				//cout << 'e';
			}
		}
		
	}

	if (counter1 < counter2) {
		cout << counter1 << endl;
	}
	else {
		cout << counter2 << endl;
	}

	return 0;
	*/
	//B
	/*int n;
	cin >> n;
	int i;
	int h[20];
	for (i = 0; i < n; i++) {
		cin >> h[i];
	}
	int maxh = 0;
	int hcounter = 0;
	maxh = h[0];
	hcounter++;
	for (i = 1; i < n; i++) {
		if (h[i] >= maxh) {
			maxh = h[i];
			hcounter++;
		}
	}
	cout << hcounter << endl;
	return 0;*/
	
	
	//A
	/*
	int a,b;
	cin >> a >> b;
	int x = 0;
	for (int i = 0; i < 2; i++) {
		if (a > b) {
			x = x + a;
			a--;
		}
		else {
			x = x + b;
			b--;
		}
	}
	cout << x << endl;
	return 0;
	*/


}

Measured memory_bytes: 896
from collections import Counter


n = int(input())
a = list(map(int, input().split()))


def main():
    if all(map(lambda e: e == 0, a)):
        print('Yes')
        return

    if n % 3 != 0:
        print('No')
        return

    count = dict(Counter(a))
    keys = list(count.keys())
    values = list(count.values())
    # a, b, c a^b^c=0
    if len(count) == 3:
        if values[0] == values[1] and values[1] == values[2] and (keys[0] ^ keys[1] ^ keys[2]) == 0:
            print('Yes')
        else:
            print('No')
    # a, a, 0 a^b^c=0
    elif len(count) == 2:
        if 0 not in count:
            print('No')
        elif (2 * count[0]) == max(values):
            print('Yes')
        else:
            print('No')
    # 0, 0, 0 -> L.9
    else:
        print('No')


if __name__ == "__main__":
    main()
    

Measured memory_bytes: 16924
N,C=[int(x) for x in str(input()).split()]
D=[[0 for x in range(0,C+1)]]
for i in range (0,C):
  D.append([0]+[int(x) for x in str(input()).split()])
c=[[0 for x in range(0,N+1)]]
for j in range(0,N):
  c.append([0]+[int(x) for x in str(input()).split()])



mod1=[0 for x in range(0,C+1)]
mod2=[0 for x in range(0,C+1)]
mod0=[0 for x in range(0,C+1)]

for x in range (1,N+1):
  for y in range(1,N+1):
    if (x+y)%3==0:
      mod0[c[x][y]]+=1
    elif (x+y)%3==1:
      mod1[c[x][y]]+=1
    else:
      mod2[c[x][y]]+=1



error=1000000000
for i in range(1,C+1):
  for j in range(1,C+1):
    if j!=i:
      for k in range(1,C+1):
        if k!=j:
          if k!=i:
            e=0

            for x in range(1,C+1):
              e+=mod0[x]*D[x][i]+mod1[x]*D[x][j]+mod2[x]*D[x][k]


       
            error=min(error,e)
print(error)





Measured memory_bytes: 5108