akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int R = sc.nextInt();
		int G = sc.nextInt();
		System.out.println(2*G-R);
	}
	
	// print
	static void print(String s) {
		System.out.println(s);
	}
	
	// union find lib
	// usage:
	// 最初にinitを呼ぶ
	// root: 直接は呼ばないで
	// unite: まとめる
	// same: グループ判定
	static void init(int par[], int N) {
		for(int i=0; i<N; i++) {
			par[i] = i;
		}
	}
	
	static int root(int x, int [] par) {
		if(par[x] == x) {
			return x;
		} else {
			return (par[x] = root(par[x], par));
		}
	}
	
	static boolean same(int x, int y, int[] par) {
		return root(x, par) == root(y, par);
	}
	
	static void unite(int x, int y, int[] par) {
		x = root(x, par);
		y = root(y, par);
		if(x == y) return;
		par[x] = y;
	}
	
	// end union find lib
	
	// number lib
	
	static int max(int...ls) {
		int ans = Integer.MIN_VALUE;
		for(int i=0; i<ls.length; i++) {
			ans = Math.max(ans, ls[i]);
		}
		return ans;
	}
	
	static int min(int...ls) {
		int ans = Integer.MAX_VALUE;
		for(int i=0; i<ls.length; i++) {
			ans = Math.min(ans, ls[i]);
		}
		return ans;
	}
	
	static long lcm(long a, long b) {
		return a*(b/gcd(a, b));
	}
	
	static long gcd(long a, long b) {
		long ta = Math.max(a, b);
		long tb = Math.min(a, b);
		long tmp;
		while((tmp = ta%tb) != 0) {
			ta = tb;
			tb = tmp;
		}
		return tb;
	}
	
	static long modcomb(long n, long k, long mod) {
		if(k==1) {
			return n;
		}
		
		long ans = 1;
		for(long i=n; i>=n-k+1; i--) {
			ans = (ans * i)%mod;
		}
		for(long i=k; 0<i; i--) {
			ans = (ans * modpow(i, mod-2, mod)) % mod;
		}
		return ans;
	}
	
	static long modpow(long a, long b, long mod) {
		if(b==0) return 1;
		if(b%2==0) {
			long d = modpow(a, b/2, mod);
			return (d*d)%mod;
		} else {
			return (a*modpow(a, b-1, mod))%mod;
		}
	}
	
	static int disit(long a, long d) {
		int count = 0;
		while(a!=0) {
			a = a/d;
			count++;
		}
		return count;
	}
	
	// end number lib
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    bool can = false;
    for (int i = 1; i <= b; i++) {
        if ((a * i) % b == c) can = true;
    }
    if (can) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=b-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	fast_io();
	int n;
	cin >> n;
	int mx = 0;
	int ans = 0;
	cu(i,0,n){
		int x;
		cin >> x;	
		if(x >= mx){
			++ans;
			mx = x;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};


//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int main(){
    int n; cin >> n;
    cout << n/3 << endl;
}

Measured memory_bytes: 256
import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:input()

"""========main code==============="""

#t=ii()
t=1
for _ in range(t):
    n=ii()
    lol=[]
    f=0
    for i in range(n):
        a,b=ml()
        lol.append([a,b])
    for i in range(n-2):
        if(lol[i][0]==lol[i][1] and lol[i+1][0]==lol[i+1][1] and lol[i+2][0]==lol[i+2][1]):
            f=1
            break
    if f:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 67192
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
A = []
for i in range(N):
    x,l = X[i]
    A.append((x-l,x+l))
B1 = sorted(A,key=lambda x:x[1])
B1 = [(B1[i][0],B1[i][1],i) for i in range(N)]
B2 = sorted(B1,key=lambda x:x[0])
hist = [0 for _ in range(N)]
cnt = 0
i = 0
for k in range(N):
    if hist[k]==0:
        r = B1[k][1]
        hist[k] = 1
        cnt += 1
        while i<N:
            l,j = B2[i][0],B2[i][2]
            if hist[j]==1:
                i += 1
                continue
            if l<r:
                hist[j] = 1
                i += 1
            else:
                break
print(cnt)

Measured memory_bytes: 119004
N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7


def dot(M1, M2, mod=10**9+7):
  n = len(M1)
  res = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j] = (res[i][j] + M1[i][k] * M2[k][j]) % MOD
  
  return res


def power(M, k, mod=10**9+7):
  if k == 1:
    return M
  elif k%2 == 0:
    return power(dot(M, M, mod), k//2, mod)
  else:
    return dot(M, power(dot(M, M, mod), k//2), mod)


trans = power(A, K) 

ans = 0
for t in trans:
  ans += sum(t)%MOD
  ans %= MOD

print(ans)

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

using namespace std;

int main(){
    int n;
    cin>>n;
    int a[100005];
    int f=1;
    int ma;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(i==0){
            ma=a[i];
        }
        else{
            if(ma<a[i]){
                ma=a[i];
            }
        }
        if(ma>a[i]+1){
            f=0;
        }
    }
    if(f){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define read(FILE)  freopen(FILE, "r", stdin);
#define out(FILE) freopen(FILE, "w", stdout);
#define all(x) x.begin(),x.end()
#define rep(i,m,n) for(int i=m ; i<n ; i++)
#define forr(i,m,n) for(int i=m ; i<=n ; i++)
#define endl '\n'
#define pb push_back
#define pff push_front
#define re return
const int N = 1e5 + 5;
using namespace std;
int main()
{
    IO;
    int n; cin>>n;
    int l=1,r=n-1,cnt=0;
    while(l<r){
        if((l+r)==n){
            cnt++;
            r--;
        }
        else if((l+r)<n){
            l++;
        }
        else if((l+r)>n){
            r--;
        }
    }

    cout<<cnt;



}


Measured memory_bytes: 256
#include<iostream>
int num[10][10];
using namespace std;
int main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s=to_string(i);
        num[s[0]-'0'][s[s.size()-1]-'0']++;
    }
    for(int i=0;i<10;i++)for(int j=0;j<10;j++)ans+=num[i][j]*num[j][i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector> 
#include <math.h>

using namespace std;



int main() {
	int n;
	vector <int> p;

	scanf("%d", &n);

	int max = 0;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		p.push_back(a);
			if (max < a) {
				max = a;
		}
		sum += a;
	}
	sum -= max / 2;
	printf("%ld", sum);
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

int main()
{
    long long N, K, rest = 0, minus = 0, ans = 0;
    cin >> N >> K;
    rest = N % K;
    minus = K - rest;
    cout << min(rest, minus) << endl;
    return 0;
}


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

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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const int INF = 1e9;

// xs = <weight, value>
LL knapsack(vector<PLL>& xs, LL W){
  int N = SZ(xs);
  LL dp[W+1];
  fill(dp, dp+W+1, -1);
  dp[0] = 0;
  REP(i,N){
	for(int w=xs[i].FF;w<=W;++w)
	  if(dp[w-xs[i].FF] < 0) continue;
	  else dp[w] = max(dp[w], dp[w-xs[i].FF]+xs[i].SS);
  }

  LL res = 0;
  for(int i=0;i<=W;++i) res = max(res, dp[i]);
  return res;
}

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

  int CITY, ITEM, W, T; cin >> CITY >> ITEM >> W >> T;
  map<string,int> index;
  // weight, sell price
  vector<PLL> items(ITEM);
  REP(i,ITEM){
	string s; int w, p; cin >> s >> w >> p;
	items[i] = MP(w,p);
	index[s] = i;
  }

  // x, y, buy prices
  vector<tuple<int,int,VI>> citys(CITY);
  REP(i,CITY){
	int L, x, y; cin >> L >> x >> y;
	get<0>(citys[i]) = x;
	get<1>(citys[i]) = y;
	VI& buf = get<2>(citys[i]);
	buf.assign(ITEM, INF);
	REP(i,L){
	  string s; int p; cin >> s >> p;
	  buf[index[s]] = p;
	}
  }

  // city bit, min_time
  map<int,int> vis;
  VI perm(CITY);
  REP(i,CITY) perm[i] = i;
  do{
	int t = 0, bit = 0;
	int px = 0, py = 0;
	REP(i,CITY){
	  int idx = perm[i];
	  bit |= 1<<idx;
	  int x = get<0>(citys[idx]);
	  int y = get<1>(citys[idx]);
	  t += abs(px - x) + abs(py - y);
	  int ret_t = t + abs(x) + abs(y);
	  if(ret_t > T) break;
	  px = x, py = y;
	  if(!vis.count(bit))
		vis[bit] = ret_t;
	  else
		vis[bit] = min(vis[bit], ret_t);
	}
  }while(next_permutation(ALL(perm)));

  // time, benefit
  map<LL,LL> route;
  for(auto& p: vis){
	vector<PLL> knap(ITEM);
	REP(i,ITEM) knap[i] = MP(items[i].FF, 0);
	REP(i,CITY){
	  if(p.FF>>i&1)
		REP(j,ITEM) knap[j].SS = max(knap[j].SS, items[j].SS - get<2>(citys[i])[j]);
	}
	route[p.SS] = max(route[p.SS], knapsack(knap,W));
  }

  vector<PLL> knap(ALL(route));
  cout << knapsack(knap, T) << endl;
  
  return 0;
}

Measured memory_bytes: 3308
h,w,k = map(int, input().split())
data = [list(input()) for _ in range(h)]

color = 1
ans = []
for i in range(h):
    ans_i = []
    if data[i].count("#") == 0:
        ans.append(ans_i)
        continue
    check = False
    for j in range(w):
        if data[i][j] == "#":
            if check:
                color += 1
            check = True
        ans_i.append(color)
    ans.append(ans_i)
    color += 1

left = 0
for i in range(h):
    if len(ans[i]):
        for j in range(left,i):
            ans[j] = ans[i]
        left = i + 1

for i in range(left,h):
    ans[i] = ans[left-1]

for i in range(h):
    print(*ans[i])

Measured memory_bytes: 48604
#include<stdio.h>
#include<string.h>

#define MAX 500000
#define NIL -2000000001
struct becs{
  int id,key,p,l,r;
};
typedef struct becs node;
node A[MAX];

void inp(int a,int u){
  if(u==NIL  || a==u)return;
  if(A[a].key<A[u].key){
    A[a].p=u;
    inp(a,A[u].l);
    if(A[u].l==NIL)A[u].l=a;
    return;
  }
  else{
    A[a].p=u;
    inp(a,A[u].r);
    if(A[u].r==NIL)A[u].r=a;
    return;
  }
}

void primid(int a){
  if(A[a].l!=NIL)primid(A[a].l);
  printf(" %d",A[a].key);
  if(A[a].r!=NIL)primid(A[a].r);
}

void pripri(int a){
  printf(" %d",A[a].key);
  if(A[a].l!=NIL)pripri(A[a].l);
  if(A[a].r!=NIL)pripri(A[a].r);
}

int main(){
  int a,b=0,i,j;
  char c[100];
  scanf("%d",&a);
  for(i=0;i<a;i++){
    A[i].id=A[i].p=A[i].l=A[i].r=NIL;
  }
  for(i=0;i<a;i++){
    scanf(" %s",c);
    if(strcmp(c,"insert")==0){scanf("%d",&A[b].key);A[b].id=b;inp(b,0);b++;}
    else{primid(0);printf("\n");pripri(0);printf("\n");}
  }
}



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

using namespace std;
using ll =long long;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
using P = pair<int,int>;
//Write From this Line

int main()
{
	double n, m, d;
	cin >> n >> m >> d;
	cout << setprecision(15);
	if(d == 0){
		cout << (m - 1) / n << endl;
	} else{
		cout << (2 * (n - d)*(m-1)) / (n*n) << endl;
	}
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int n, k, sum = 1;
  scanf("%d %d", &n, &k);

  for(int i = 0; i < n; i++) {
    int sum1 = sum * 2;
    int sum2 = sum + k;
    if(sum1 < sum2) {
      sum *= 2;
    }
    else {
      sum += k;
    }
  }
  printf("%d", sum);
  return 0;
}

Measured memory_bytes: 1732
//A - Air Conditioner
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x7fffffff
using namespace std;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

int main() {
    //File();
    int X;
    scanf("%d",&X);
    if(X>=30) { printf("Yes\n"); }
    else printf("No\n");
    //fclose(stdin); fclose(stdout);
   // system("pause");
    return 0;
}

Measured memory_bytes: 3660
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello{
    public static void Main(){
        var alph = "abcdefghijklmnopqrstuvwxyz";
        var nums = new int[26];
        for(var i = 0;i < 26;i++){
            nums[i] = 0;
        }
        
        while(true){
            var s = Console.ReadLine();
            if(s == null) break;
            s = s.ToLower();
            for(var i = 0;i < 26;i++){
                var count = s.Count(x => x == alph[i]);
                nums[i] += count;
            }
        }
        
        for(var i = 0;i < 26;i++){
            Console.WriteLine($"{alph[i]} : {nums[i]}");
        }
    }
}



Measured memory_bytes: 8088
#include<stdio.h>
int A[100][100];
int v[100];
void MST(int);
  
main(){
  int n, i, j;
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      scanf("%d", &A[i][j]);
    }
  }
  MST(n);
  return 0;
}
  
void MST(int n){
  int i, j, k=1, X[100], minCost, min, sum=0;
    
  X[0] = 0;
  v[0] = 1;
  for(i = 1; i < n; i++){
    v[i] = 0;
  }
  while(1){
    minCost = 2001;
    for(i = 0; i < k; i++){
      for(j = 0; j < n; j++){
    if(A[X[i]][j] < minCost && A[X[i]][j] != -1 && v[j] != 1){
      minCost = A[X[i]][j];
      min = j;
    }
      }
    }
    if(k != n){
      X[k] = min;
      v[min] = 1;
      sum += minCost;
      k++;
    }
    else break;
  }
  printf("%d\n", sum);
}

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

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

    int c = 0;
    while(n > 0){
        n /= k;
        c++;
    }
    cout << c;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())

    ans = pow(N // K, 3)
    if K % 2 == 0 and N >= K // 2:
        ans += pow((N - K // 2) // K + 1, 3)

    print(ans)
    return


if __name__ == '__main__':
    main()


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

using namespace std;

typedef pair<long long int, vector<long long int>> PLVL;

int main(){
	long long int N;
	cin >> N;
	vector<long long int>A(N);
	for( size_t i = 0; i < N; i++ ){
		cin >> A[i];
	}
	auto B = A;
	sort(A.begin(), A.end());
	long long int mid = N / 2;
	long long int minv = A[mid - 1];
	long long int maxv = A[mid];
	for( size_t i = 0; i < N; i++ ){
		if( maxv > B[i] ){
			cout << maxv << endl;
		} else{
			cout << minv << endl;
		}
	}
}



Measured memory_bytes: 5376
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        x_vec: [i64; 5],
    }

    for (i, x) in x_vec.iter().enumerate() {
        if *x == 0 {
            println!("{}", i + 1);
            return;
        }
    }
}


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

int main() {
 string s,t;
 cin>>s>>t;
 cout<<t+s<<endl;
}

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

using namespace std;

int main()
{
	char s[10];
	scanf("%s",s);
	for (int i=0;i<strlen(s)-1;i++)
	{
		if (s[i]=='A' && s[i+1]=='C')
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
string s,t;
cin >> s >> t;
long long dp[3100][3100] = {0};//dp-table,文字列s,tのi,j番目まででのLCSを保持。

//dp
for(int i = 0; i < s.size(); i++){
    for(int j = 0; j < t.size(); j++){
        //s[i],t[j]が等しい時に限り，値を更新する
        if(s[i] == t[j]){
            chmax(dp[i + 1][j + 1], dp[i][j] + 1);
        } else {//そうじゃない時，これはただ単に値を継承するだけ。
            chmax(dp[i + 1][j + 1], dp[i + 1][j]);
            chmax(dp[i + 1][j + 1], dp[i][j + 1]);
        }
    }
}

//復元する
string ans = "";
int i = s.size();
int j = t.size();

while(i > 0 && j > 0){
    if(dp[i][j] == dp[i][j-1]){
        j--;
    } else if (dp[i][j] == dp[i-1][j]){
        i--;
    } else {
        ans = s[i-1] + ans;
        i--, j--;
    }
}

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

Measured memory_bytes: 75392
#include<bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
int main(){
  string s;
  cin>>s;
	rep(i,3)cout<<((s[i]=='1')?"9":"1");
  cout<<endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=1e6+10;
int n,l,r;
char q[maxn],s[maxn],now[5];
int main()
{
	scanf("%s",s+1); n=strlen(s+1); l=2e5; r=2e5-1;
	for (int i=1;i<=n;i++) q[++r]=s[i];
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int op; scanf("%d",&op);
		if (op==1) swap(l,r);
		else
		{
			int f; scanf("%d%s",&f,now+1);
			if (f==1)
			{
				if (l<r) q[--l]=now[1];
				else q[++l]=now[1];
			}
			else
			{
				if (l<r) q[++r]=now[1];
				else q[--r]=now[1];
			}
		}
	}
	if (l<r) for (int i=l;i<=r;i++) printf("%c",q[i]);
	else for (int i=l;i>=r;i--) printf("%c",q[i]);
return 0;
}

Measured memory_bytes: 896
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    while(1){
        string S;
        cin>>S;
        if(S=="-"){
            break;
        }
        int m;
        cin>>m;
        string a,b;
        for(int i=0;i<m;i++){
            int h;
            cin>>h;
            a=S.substr(0,h);
            b=S.erase(0,h);
            S=a.insert(0,b);
        }
        cout<<S<<endl;
    }
}



Measured memory_bytes: 3168
#include"iostream"
#include"string"
using namespace std;

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	int num = 0;
	for (int i = 1; i < n; i++)
	{
		if (s[i] == 'E')num++;
	}
	int ans = num;
	for (int i = 1; i < n; i++)
	{
		if (s[i - 1] == 'W')num++;
		if (s[i] == 'E')num--;
		if (num < ans)ans = num;
	}
	cout << ans << endl;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int y, m ,d;
  char c1,c2;
  cin >> y >> c1 >> m >> c2 >> d;
  if( m <=4){
    cout << "Heisei";
  }
  else{
    cout << "TBD";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
 
#define ll long long int
#define mp make_pair 
#define pb push_back
#define ff first
#define ss second
#define fast  ios_base::sync_with_stdio(false);cin.tie(0);
#define MOD 998244353
#define ll_MAX 19223372036859
#define endl "\n"
inline ll absdiff(ll a,ll b){ return (a>b)?a-b:b-a;}
ll fast_expo(ll x,ll p){if(p==0) return 1;
else if(p%2==0){ ll t=fast_expo(x,p/2)%MOD;return (t*t)%MOD;} else return (x*(fast_expo(x,p-1))%MOD)%MOD;}
ll gcd(ll a,ll b){if(a==0||b==0) return a+b;  else return gcd(b%a,a); }

int main()
{
    fast
    ll q;q = 1;
    // cin>>q;
    for (ll t = 0; t < q; ++t)
    {
        ll n;cin>>n;
        ll arr[n];
        for(auto &i:arr) cin>>i;

        ll last=0;
        for(ll i=0;i<n;++i){
            if(arr[i]==last+1) last++;
        }
        if(last==0) cout<<-1;
        else cout<<n-last;
    }
    return 0;
}   

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll N; cin >> N;
  ll result = 0; repr(i,1,N) result += (N-1)/i;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3632
n = int(input())
a = list(map(int, input().split()))
b = list()
c = list()
for i in range(n):
    if(i==0):
        b.append(a[i])
    elif(i%2==1):
        b.append(a[i])
    else:
        c.append(a[i])
c.reverse()
c = c + b
if(i%2==1):
    c.reverse()
for i in c:
    print(i,end=' ')

Measured memory_bytes: 103380
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};


const double EPS = 1e-9;

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

        if(n == 0) break;
        vector<vector<char> > freeday(40,vector<char>(n,false));
        for(int i=0;i<n;i++){
            int m;
            cin >> m;
            for(int j=0;j<m;j++){
                int x;
                cin >> x;
                freeday[x][i] = true;
            }
        }
        vector<vector<ll> > nyan(40,vector<ll>(n));
        for(int i=0;i<n;i++){
            nyan[0][i] = 1ll << i;
        }

        int ret = -1;
        for(int i=1;i<31;i++){
            ll get = 0;
            for(int j=0;j<n;j++){
                nyan[i][j] = nyan[i-1][j];
            }
            for(int j=0;j<n;j++){
                if(freeday[i][j]) get |= nyan[i][j];
            }
            for(int j=0;j<n;j++){
                if(freeday[i][j]) nyan[i][j] = get;
            }
            if(get == (1ll << n)-1){
                ret = i;
                break;
            }
        }
        cout << ret << endl;
    }
    return 0;
}

Measured memory_bytes: 1252
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);


int main(){
	int n,a,b,c,x;
	while(cin>>n>>a>>b>>c>>x,n){
		vi y(n);
		REP(i,n){
			cin>>y[i];
		}
		int cnt=0;
		bool ng=false;
		REP(i,n){
			while(true){
				if(x==y[i]){
					x=(x*a+b)%c;
					if(i>0)cnt++;
					if(cnt>10000){
						ng=true;
					}
					break;
				}
				x=(x*a+b)%c;
				cnt++;
				if(cnt>10000){
					ng=true;
					break;
				}
			}
		}
		if(ng){
			cout<<-1<<endl;
		}else{
			cout<<cnt<<endl;
		}
	}
}

Measured memory_bytes: 0
package main

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

const mod = 1000000007

// 1MB
const ioBufferSize = 1 * 1024 * 1024

var sc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	sc.Split(bufio.ScanWords)
	return sc
}()

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

func main() {
	n := nextInt()
	w := make([]string, n)

	for i := 0; i < n; i++ {
		w[i] = next()
	}

	already := map[string]bool{}
	already[w[0]] = true
	for i := 1; i < n; i++ {
		prev := w[i-1]
		s := w[i]
		if already[s] || prev[len(prev)-1] != s[0] {
			fmt.Println("No")
			return
		}
		already[s] = true
	}

	fmt.Println("Yes")
}


Measured memory_bytes: 640
// Copyright (C) 2017 __debug.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#define x first
#define y second
#define MP std::make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using std::pair;
using std::vector;
using std::string;

typedef long long LL;
typedef pair<int, int> Pii;

const int oo = 0x3f3f3f3f;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
string procStatus()
{
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
    int f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (x = 0; isdigit(ch); ch = getchar())
        x = 10 * x + ch - '0';
    return x *= f;
}
template<typename T> void write(T x)
{
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[20];
    int top = 0;
    for (; x; x /= 10)
        s[++top] = x % 10 + '0';
    while (top)
        putchar(s[top--]);
}
// EOT

const int MAXN = 1e5 + 5;

int N;
int A, B, H[MAXN];

void input()
{
    read(N); read(A); read(B);
    for (int i = 1; i <= N; ++i) {
        read(H[i]);
    }
}

bool check(LL x)
{
    LL all = x * B;
    LL need = 0;
    for (int i = 1; i <= N; ++i) {
        if (H[i] > all)
            need += (H[i] - all + A - B - 1) / (A - B);
    }
    return need <= x;
}

void solve()
{
    int l = -1, r = 1e9;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%d\n", r);
}

int main()
{
#ifdef __DEBUG
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif

    input();
    solve();

    return 0;
}

// 最是秋风管闲事，红他枫叶白人头。
//     -- 赵翼《野步》


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

ll dp[100100];
int n, h[100100];

ll func( ) {
    dp[1] = 0;
    dp[2] = abs(h[1] - h[2]);

    for (int pos = 3; pos <= n; ++pos) {
        dp[pos] = min(
            dp[pos - 1] + abs(h[pos] - h[pos - 1]), 
            dp[pos - 2] + abs(h[pos] - h[pos - 2])
        );
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    func();
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>

#define INF_LL 9000000000000000000
#define INF 2000000000

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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

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

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int n, m;
	int bibs[100];

	cin >> n >> m;
	REP(i, n){
		cin >> bibs[i];
	}

	REP(k, m){
		REP(i, n-1){
			if(bibs[i] % (k+1) > bibs[i+1] % (k+1)){
				swap(bibs[i], bibs[i+1]);
			}
		}
	}
	REP(i, n){
		cout << bibs[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3048
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int a, b;

    cin >> a >> b;

    for (int i = 1; i <= 1000; i++)
    {
        if ((int)(i * 0.08) == a && (int)(i * 0.1) == b)
        {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector<int> A;
vector<int> A1;
#define ten6 2000030
int N;
bool used[ten6];

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a = 0;
        cin >> a;
        A.push_back(a);
        //dependent.push_back(0);
    }
    sort(A.begin(), A.end());
    if(A[0]==1){
        if(N>1){
            if(A[1]==1){
                cout<<0;
                return 0;
            }
        }
        cout<<1;
        return 0;
    }
    int last=0;
    for (int i = 0; i < N; i++)
    {
        if(last==A[i]){
            used[A[i]-1]=true;
            continue;
        }
        for(int x=A[i]*2;x<=ten6;x+=A[i]){
            used[x-1]=true;
        }
        last=A[i];
    }
    int res=0;

    for (int i = 0; i < N; i++)
    {
        if(!used[A[i]-1]){
            res++;
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 6004
#include<iostream>
#include<algorithm>
using namespace std;
int t[101],n,maxm;
int main(){
  for(int i=0;i<101;i++)t[i]=0;
  maxm=0;
  while(cin>>n){
    t[n]++;
    maxm=max(maxm,t[n]);
  }
  for(int i=1;i<=100;i++){
    if(maxm==t[i])cout<<i<<endl;
  }
  return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n,a,b;
  	ci(n>>a>>b);
  ll z=0;
  co(M(z,abs(a-b)-n))
     }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int lli;

int main(){
    lli n,a,b;
    cin >> n >> a >> b;
    vector<lli> x(n);
    for(int i=0; i<n; i++){
        cin >> x[i];    
    }
    lli ans = 0;
    for(int i=0; i<n-1; i++){
        ans += min(a*(x[i+1]-x[i]), b);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
using namespace std;
static const int MAX = 100;

int bubbleSort(int A[], int N)
{
    int sw = 0;

    bool flag = 1;
    for (int i = 0; flag; i++)
    {
        flag = 0;
        for (int j = N - 1; j >= i + 1; j--)
        {
            if (A[j] < A[j - 1])
            {
                swap(A[j], A[j - 1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
};

int main()
{
    int A[MAX], j, N, sw;
    cin >> N;
    for (int k = 0; k < N; k++)
    {
        cin >> j;
        A[k] = j;
    }
    // int A[10] = {1, 6, 3, 7, 9, 423, 76, 432, 0, 64}, N = 10, sw;
    sw = bubbleSort(A, N);
    for (int i = 0; i < N; i++)
    {
        if (i)
        {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;
    cout << sw << endl;
    return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include<iomanip>
using namespace std;
using P = pair<int, int>;
int MOD = 1000000007;

int N, M;
bool isAC[200010];
int p[200010];
string s[200010];

int main()
{
	cin >> N >> M;
	int account = 0;
	int pena = 0;
	for (int i = 0; i < M; i++) {
		cin >> p[i] >> s[i];
	}
	for (int i = 0; i < M; i++) {
		if (s[i] == "AC") {
			if (!isAC[p[i]]) {
				account++;
				isAC[p[i]] = true;
			}
		}
	}
	for (int i = 0; i < M; i++) {
		if (s[i] == "AC") {
			if (isAC[p[i]]) {
				isAC[p[i]] = false;
			}
		}
		else {
			if (isAC[p[i]]) {
				pena++;
			}
		}
	}
	cout << account << " " << pena << endl;
}

Measured memory_bytes: 7040
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans= 0
for i in range(n):
    if a[i] >= b[i]:
        ans += b[i]
    else:
        ans += a[i]
        if b[i] - a[i] >= a[i + 1]:
            ans += a[i + 1]
            a[i + 1] = 0
        else:
            ans += b[i] - a[i]
            a[i + 1] -= b[i] - a[i]
print(ans)

Measured memory_bytes: 81892
#include <cstdio>
#include <cmath>

int main(){
 int n;
 scanf("%d\n",&n);
 for(int i = 0;i < n;i++){
  float x1,x2,x3,x4,y1,y2,y3,y4;
  scanf("%f %f %f %f %f %f %f %f\n",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
  if(atan((y1 - y2) / (x1 - x2)) == atan((y3 - y4) / (x3 - x4))){
   printf("YES\n");
  }else{
   printf("NO\n");
  }
 }
}

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

using namespace std;

stack<pair<int, pair<int, int> > >candEdges;

bool isConnected(vector<pair<int, int> > G[], int u, int v, int p = -1)
{
	if (u == v) return (true);
	
	for (int i = 0; i < G[u].size(); i++){
		if (G[u][i].first != p){
			candEdges.push(make_pair(G[u][i].second, make_pair(u, G[u][i].first)));
			if (isConnected(G, G[u][i].first, v, u)) return (true);
			candEdges.pop();
		}
	}
	
	return (false);
}

int main()
{
	int n, m;
	
	while (scanf("%d %d", &n, &m) && n){
		vector<pair<int, int> > G[128];	
		vector<pair<int, pair<int, int> > > edges;
		
		for (int i = 0; i < m; i++){
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			a--; b--;
			edges.push_back(make_pair(c, make_pair(a, b)));
		}
		
		sort(edges.begin(), edges.end());
		
		int ans = 10000;
		
		vector<pair<int, pair<int, int> > > usingEdges;
		for (int i = 0; i < m; i++){
			pair<int, pair<int, int> > e = edges[i];
			
			if (isConnected(G, e.second.first, e.second.second)){
				pair<int, pair<int, int> > e2 = candEdges.top();
				while (!candEdges.empty()){
					if (e2.first > candEdges.top().first){
						e2 = candEdges.top();
					}
					candEdges.pop();
				}
				
				for (auto it = G[e2.second.first].begin(); it != G[e2.second.first].end(); it++){
					if (*it == make_pair(e2.second.second, e2.first)){
						G[e2.second.first].erase(it);
						break;
					}
				}
				for (auto it = G[e2.second.second].begin(); it != G[e2.second.second].end(); it++){
					if (*it == make_pair(e2.second.first, e2.first)){
						G[e2.second.second].erase(it);
						break;
					}
				}
				for (int j = 0; j < usingEdges.size(); j++){
					if (usingEdges[j] == e2 || usingEdges[j] == make_pair(e2.first, make_pair(e2.second.second, e2.second.first))){
						usingEdges.erase(usingEdges.begin() + j);
						break;
					}
				}
			}
			
			usingEdges.push_back(e);
			G[e.second.first].push_back(make_pair(e.second.second, e.first));
			G[e.second.second].push_back(make_pair(e.second.first, e.first));
			
			if (usingEdges.size() == n - 1){
				int mini, maxi;
				mini = maxi = usingEdges[0].first;
				for (int j = 1; j < usingEdges.size(); j++){
					maxi = max(maxi, usingEdges[j].first);
					mini = min(mini, usingEdges[j].first);
				}
				ans = min(ans, maxi - mini);
			}
		}
		
		printf("%d\n", ans == 10000 ? -1 : ans);
	}
	
	return (0);
}

Measured memory_bytes: 1320
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
void print(ll x){
	if(x<0)putchar('-'),x=-x;
	int y=x%10+'0';
	if(x>=10)print(x/10);
	putchar(y);
}
ll n,m,sum,w[105],c[105],dp[100005];
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		w[i]=read(),c[i]=read(),sum+=c[i];
	memset(dp,0x3f,sizeof(dp)),dp[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=sum;j>=c[i];j--)
			dp[j]=min(dp[j-c[i]]+w[i],dp[j]);
	for(int i=sum;i>=0;i--)
		if(dp[i]<=m)return print(i),0;
}

Measured memory_bytes: 1024
def solve():
    n, x = map(int, input().split())
    al = [int(i) for i in input().split()]
    bi = [i for i in al]
    ans = sum(al)
    for k in range(1, n):
        bi = [min(bi[i-1], al[i]) for i in range(n)]
        ans = min(ans, k * x + sum(bi))
    print(ans)

if __name__=="__main__":
    solve()

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

using namespace std;

int main() {
    long long n;
    long long max = 0;
    cin >> n;
    string s;
    map<string, long long> m;

    for (int  i = 0; i < n; i++){ 
        cin >> s;
        m[s] += 1;
    }
    for (auto itr = m.begin(); itr != m.end(); itr++) {
        if (max < itr->second){
            max = itr->second;
        }
    }
    for (auto itr = m.begin(); itr != m.end(); itr++) {
        if (itr->second == max){
            cout << itr->first << endl;
        } 
    }


    return 0;
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;

map<int, int> mp;
int f(int x) {
    if (x<=5) return x;
    if (mp.count(x)) return mp[x];
    int a = 6;
    int b = 9;
    int res = x;
    while (x>=a) {
        chmin(res, f(x-a)+1);
        a *= 6;
    }
    while (x>=b) {
        chmin(res, f(x-b)+1);
        b *= 9;
    }
    mp[x] = res;
    return res;
}


int main(){
    int n;
    cin >> n;
    int ans = f(n);
    
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
const ll INF = 10000000000000000;

int main(){
	static int n;
	static int l[100010],r[100010];
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; i ++){
		scanf("%d%d",&l[i],&r[i]);
	}
	l[0] = r[0] = 0;
	
	priority_queue<ll> L;
	priority_queue<ll,vector<ll>,greater<ll>> R;
	ll dL = 0, dR = 0;
	ll m = 0;
	L.push(-INF);
	R.push(INF);
	for(int i = 1 ; i <= n ; i ++){
		dR += r[i-1]-l[i-1];
		dL -= r[i]-l[i];
		ll x = L.top()+dL;
		ll y = R.top()+dR;
		if(l[i] < x){
			L.push(l[i]-dL);
			L.push(l[i]-dL);
			L.pop();
			R.push(x-dR);
			m += x-l[i];
		}
		else if(l[i] > y){
			R.push(l[i]-dR);
			R.push(l[i]-dR);
			R.pop();
			L.push(y-dL);
			m += l[i]-y;
		}
		else {
			L.push(l[i]-dL);
			R.push(l[i]-dR);
		}
	}
	cout << m << endl;
}

Measured memory_bytes: 2804
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
	string s;
	cin >> s;
	if (s == "Sunny") {
		cout << "Cloudy" << endl;
	}
	else if (s == "Cloudy") {
		cout << "Rainy" << endl;
	}
	else if (s == "Rainy") {
		cout << "Sunny" << endl;
	}

}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
using namespace std; 
typedef long long ll; 
int son[100005][2]; 
char str[100005]; 
ll tot_dep, sg[100005]; 
inline int chk(ll x)
{
	int res = 0; 
	if (!x)
		return 0; 
	while (x & 1 ^ 1)
	{
		res++; 
		x >>= 1; 
	}
	return res; 
}
void dfs(int u, int dep = 0)
{
	if (!u)
		return; 
	int l = son[u][0], r = son[u][1]; 
	dfs(l, dep + 1); 
	dfs(r, dep + 1); 
	sg[0] = 1ll << chk(tot_dep - dep); 
	sg[u] = sg[l] ^ sg[r]; 
}
int main()
{
	// freopen("ARC087-E.in", "r", stdin); 
	int n, tot = 1; 
	scanf("%d%lld", &n, &tot_dep); 
	for (int i = 0; i < n; i++)
	{
		scanf("%s", str); 
		int u = 1, len = strlen(str); 
		for (int j = 0; j < len; j++)
		{
			if (!son[u][str[j] - '0'])
				son[u][str[j] - '0'] = ++tot; 
			u = son[u][str[j] - '0']; 
		}
	}
	dfs(1); 
	puts(sg[1] ? "Alice" : "Bob");
	return 0; 
}


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

bool solve() {
	int n;
	cin >> n;

	vector<int> a(n), f(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		f[a[i]]++;
	}

	int D = *max_element(a.begin(), a.end());

	if (D % 2 == 0) {
		for (int i = D; i > D / 2; i--) {
			f[i] -= 2;
			if (f[i] < 0) return false;
		}
		f[D / 2]--;
		if (f[D / 2] < 0) return false;
		for (int i = 1; i <= n - 1; i++) {
			if (i < D / 2 + 1 && f[i] > 0) return false;
		}
	} else {
		for (int i = D; i > D / 2; i--) {
			f[i] -= 2;
			if (f[i] < 0) return false;
		}
		for (int i = 1; i <= n - 1; i++) {
			if (i <= D / 2 + 1 && f[i] > 0) return false;
		}
	}
	return true;
}

int main() {
	puts(solve() ? "Possible" : "Impossible");
}

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

#define int           long long 
#define S             second
#define F             first
#define pb            push_back
#define all(c)        (c).begin(),(c).end()
#define rall(c)       (c).rbegin(),(c).rend() 
#define lb            lower_bound
#define si(c)         (int)((c).size())
#define lcm(a, b)      (a * (b / __gcd(a,b)))  
#define inf           (int)(1e18)
#define endl          '\n'
#define mp            make_pair
#define time(s)       (double(clock()-s)/double(CLOCKS_PER_SEC))
#define debug(args...)    _F(#args, args)
#define vi            std::vector<int>
#define pii           pair<int, int> 
#define vpi           vector<pii>

clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

template<typename T> void _F(const char *name, T arg1){ cerr << name << " = " << arg1 << endl;}
template<typename T, typename... Args> void _F(const char *names, T arg1, Args... args)
{ const char *name = strchr(names, ',');cerr.write(names, name-names) << " = " << arg1 << endl;_F(name+2, args...);}

template< typename T1, typename T2 > istream& operator>>(istream& in, pair<T1, T2> &q){ in >> q.F >> q.S; return in;}
template< typename T1, typename T2 > ostream& operator<<(ostream& out, pair<T1, T2> &q){ out << q.F << " " << q.S; return out;}
template< typename T1, typename T2 > pair<T1, T2> operator+(pair<T1, T2> p1, pair<T1, T2> p2){ return {p1.F+p2.F, p1.S+p2.S};}
template< typename T1, typename T2 > pair<T1, T2> operator-(pair<T1, T2> p1, pair<T1, T2> p2){ return {p1.F-p2.F, p1.S-p2.S};}
template< typename T1, typename T2 > bool operator<(pair<T1, T2> p1, pair<T1, T2> p2){ return p1 < p2 ;}

template<typename T> void Unique(vector<T> &v){
    sort(all(v)), v.resize(distance(v.begin(), unique(all(v))));
}


void solve(int &test) {
    int n;
    cin >> n;
    if(n%1000){
        cout << 1000-n%1000 << endl;
        return;
    }
    cout << 0 << endl;
}

signed main(){

    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);   

    int t = 1;

    start = clock(); 

    cout << fixed << setprecision(2);
    
    
    for(int i = 1; i <= t; ++i){
        solve(i);
    }
    cerr << time(start);
    return 0;
}

Measured memory_bytes: 3796