akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define rrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}

template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }
template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

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



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


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

    int n = x/100;
    int y = x%100;

    if(y >= 0 && y <= 5*n) cout << 1 << endl;
    else cout << 0 << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] num = new String[4];
		for (int i = 0; i < 4; i++) {
			num[i] = sc.next();
		}
		Arrays.sort(num);
		StringBuilder s = new StringBuilder(4);
		for(String sss:num)
			s.append(sss);

		if ("1479".equals(s.toString())) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

	}
}

Measured memory_bytes: 23124
s = input()
t = ("erase", "eraser", "dream", "dreamer")
def Solve(s):
    while 1 :
        for i in t :
            if s.endswith(i):
                s = s[:-len(i)]
                break
        else:
            print('NO')
            break
        if not s:
            print('YES')
            break
Solve(s)



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

int main() {
	int a,b,c,d,e,k;
	cin >> a >> b >> c >> d >> e >> k;
	string ans;
	if (e - a <= k){
		ans = "Yay!";
	}
	else{
		ans = ":(";
	}
	cout << ans << endl;
}


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

int main() {
    int n;
    cin>>n;
    long long int ar=0;

    
    
    int temp[64];
    for(int i=0;i<64;i++){
        temp[i]=0;
    }
    for(int i=0;i<n;i++){
        cin>>ar;
        int j=0;
        while(ar>0){
            temp[j]+=ar%2;
            ar/=2;
            j++;
        }
    }
    long long int sum=0,tempsum=0,temp2;

    for(int i=0;i<63;i++){
        int k1=temp[i],k2=n-temp[i];
        // cout <<k1 << " " << k2 << endl;
        tempsum=k1;tempsum*=k2;
        if(tempsum>1000000007)    tempsum=tempsum%1000000007;
        temp2=(pow(2,i));
        // cout << temp2 <<endl;
        // cout << tempsum<< endl;
        if(temp2>1000000007)    temp2=temp2%1000000007;
        tempsum*=temp2;
        sum+=tempsum;
        if(sum>1000000007)    sum=sum%1000000007;

    }
    cout << sum << endl;
    return 0;

}


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

bool cmp(const pair<int, int> &a, const pair<int, int> &b){
    return a.first < b.first;
} 
int main(){
    int N; cin >> N;
    deque<pair<int,int>> robo;
    for(int i=0; i<N; i++){
        int x, l; cin >> x >> l; 
        robo.push_back(make_pair(x, l));
    }

    sort(robo.begin(), robo.end(), cmp);

    int cnt = N;
    while(!robo.empty()){
        pair<int, int> next = robo.front();
        robo.pop_front();
        if(robo.empty()) break;
        int r = next.first + next.second;
        next = robo.front();
        while(r > next.first - next.second){
            //cout << next.first << " " << next.second << endl;
            cnt--;
            r = min(r, next.first + next.second);
            robo.pop_front();
            if(robo.empty()) break;
            next = robo.front();
        }
    }
    cout << cnt << endl;
}


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

int main()
{
    int N;
    int a[100000] = {0};

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

    int now = 0;
    int ans = 1;
    bool visit[100000] = {false};
    visit[0] == true;
    while (1)
    {
        if (a[now] == 2)
        {
            cout << ans << endl;
            return 0;
        }
        else if (a[now] != 2 && visit[a[now] - 1] == false)
        {
            visit[a[now] - 1] = true;
            now = a[now] - 1;
            ans++;
        }
        else
        {
            cout << -1 << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<map>
#include<cstdio>
using namespace std;
int main(void) {
	map<string, int>m;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char s[20],s2[20];
		scanf("%s", s);
		scanf("%s", s2);
		if (s[0] == 'i') {
			m[s2] = 1;
		}
		else
		{
			if (m[s2]) cout << "yes" << endl;
			else {
				cout << "no"<<endl;
			}
		}
	}
	return 0;
}


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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  int n,k;
  cin >> n >> k;
  int a,b,c;
  // long long ans = 0;
  long long ans1 = 0;
  long long ans2 = 0;

  for(int i = 1; i <= n; i++){
    if(k % 2 == 0){
      if(i % k == 0) ans1 ++;
      else if(i % k == k / 2) ans2 ++;
    }else {
      if(i % k == 0) ans1 ++;
    }
  }
  cout << ans1 * ans1 * ans1 + ans2 * ans2 * ans2 << endl;

  return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define P pair<int, int>
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
const int MAX_N = (1 << 16);
const int INF = 100000 * 20;

int N, dp[MAX_N];
vector< vector<int> > v;

int calc(int bit, int now){
  int ret = v[now][0];
  //REP(i, N + 1) cout <<v[now][i] <<" "; cout <<endl;
  REP(i, N){
    int tmp = (1 << i);
    if(bit & tmp){
      //cout <<tmp <<", " <<i <<", " <<v[now][i] <<endl;
      ret = min(ret, v[now][i + 1]);
    }
  }
  //cout <<"now = " <<now <<", bit = " <<bit <<", ret = " <<ret <<endl;
  //cout <<"---" <<endl;
  return ret;
}

void disp(){
  REP(i, (1 << N)){
    cout <<i <<" : " <<dp[i] <<endl;
  }
}

int main() {
  while(cin >>N && N){
    v = vector<vector<int> >(N, vector<int>(N + 1));
    REP(i, N) REP(j, N + 1) cin >>v[i][j];
    //debug
    //REP(i, N){
    //  REP(j, N + 1) cout <<v[i][j] <<" ";
    //  cout <<endl;
    //}
    REP(i, (1 << N)) dp[i] = INF;
    dp[0] = 0;
    REP(mask, (1 << N)){
      if(mask == INF) continue;
      REP(i, N){
        int next = (1 << i);
        if(mask & next) continue;
        dp[(mask | next)] = min(dp[(mask | next)], dp[mask] + calc(mask, i));
        //cout <<(mask | next) <<", " <<mask <<", " <<next <<", " <<dp[(mask | next)] <<endl;
      }
    }
    //disp();
    cout <<dp[(1 << N) - 1] <<endl;
  }
  return 0;
}

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

paths = [0] * N
paths[0] = 1

first_length = 0
loops_length = 0

present_place = 0
for i in range(N):
    present_place = A[present_place]-1
    if paths[present_place] != 0:
        loops_length = (i+2) - paths[present_place]
        first_length = paths[present_place]-1
        break
    paths[present_place] = i+2

if K <= first_length:
    print(A[paths.index(K)])
else:
    K = K - first_length
    print(paths.index(first_length+1 + K % loops_length) + 1)

Measured memory_bytes: 32380
#include <stdio.h>
#include <math.h>

using namespace std;

int main(){
	double x1,x2,x3,y1,y2,y3,xp,yp;
	double calc1,calc2,calc3;

	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&xp,&yp)!=EOF){
		calc1 = (x2-x1)*(yp-y1)-(y2-y1)*(xp-x1);
		calc2 = (x3-x2)*(yp-y2)-(y3-y2)*(xp-x2);
		calc3 = (x1-x3)*(yp-y3)-(y1-y3)*(xp-x3);

		if((calc1>0&&calc2>0&&calc3>0) || (calc1<0&&calc2<0&&calc3<0)){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
    return 0;
}

Measured memory_bytes: 2580
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define il inline
#define re register
#define fo(i,j,k) for(register int i=j;i<=k;i++)
#define do(i,j,k) for(register int i=j;i>=k;i--) 
#define inf 0x7fffffff
typedef long long ll;
using namespace std;
il ll read()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f*x;	
}
int n; 
ll sum;
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int main()
{
	cin>>n;
	fo(i,1,n)
	{
		fo(j,1,n)
		{
			fo(k,1,n)
			{
				sum+=gcd(i,gcd(j,k));
			} 
		}
	}
	cout<<sum;
	return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans,i;

int main(){
	cin>>n;
	
	for(i=1;i<=n;i++)
	if(i%3!=0&&i%5!=0)
	ans+=i;
	
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair

#define REP(i, n) for(int i=0;i<(int)(n);++i)
#define FOR(i,l,h) for(int i=(int)(l);i<=(int)(h);++i)
#define FORD(i,h,l) for(int i=(int)(h);i>=(int)(l);--i)

//#define max(a,b) a>b?a:b
//#define min(a,b) a>b?b:a

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

#define dump(x)  cerr << #x << " = " << (x) << endl
#define ALL(t) (t).begin(),(t).end()

using namespace std;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

int sum() { return 0; }

template<typename T, typename... Args>
T sum(T a, Args... args) { return a + sum(args...); }



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	ll n,d;cin>>n>>d;
    ll x,y;
    d = (ll)d*d;
    ll cnt =0;
    for (int i = 0; i < n; ++i)
    {
        cin>>x>>y;
        ll pd = ((ll)x*x + (ll)y*y);

        if(pd <= d) cnt++;
    }
    cout<<cnt;
    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int l,r,d;
  cin>>l>>r>>d;
  int i;
  int c=0;
  for(i=l;i<=r;i++)
  {
    if(i%d==0)
      c++;
  }
  cout<<c;
  return 0;
}

Measured memory_bytes: 3600
N = gets.to_i
A = gets.split.map(&:to_i)

rui = [0]

A.each_with_index do |a, i|
  rui[i + 1] = rui[i] + a
end

ans = 0

f = -> (x, y) {
  v = rui[y + 1] - rui[x]

  while y < N - 1 && (v & A[y + 1]) == 0
    v += A[y + 1]
    y += 1
  end

  y
}

l = r = 0

while l < N
  r = f[l, r]
  d = r - l + 1
  ans += d
  l += 1
end

puts ans



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

int main()
{
	int n, l;

	cin >> n >> l;

	vector<string> v(n);

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

	sort(v.begin(), v.end());

	for (auto s : v) {
		cout << s;
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        long numR = 0;
        long numG = 0;
        long numB = 0;
        long ans = 0;
        for(int i=0;i<N;i++){
            char c = S.charAt(i);
            if(c=='R'){
                numR++;
            }else if(c=='G'){
                numG++;
            }else{
                numB++;
            }
        }
        // 組み合わせの数を計算
        ans = numR*numG*numB;
        for(int a=1;a<N;a++){
            for(int sa = 1;a+sa*2<=N;sa++){
                if(S.charAt(a-1) != S.charAt(a+sa-1) && S.charAt(a-1) != S.charAt(a+sa*2-1) && S.charAt(a+sa-1) != S.charAt(a+sa*2-1)){
                    ans--;
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 37128
#include<cstdio>
#include<vector>

using namespace std;

int main() {
	long long N, K;
	scanf("%lld %lld", &N, &K);
	vector<int> a;
	vector<int> right;
	vector<int> any;
	for (int i = 0; i < N; i++) {
		int temp;
		scanf("%d", &temp);
		a.push_back(temp);
		right.push_back(0);
		any.push_back(0);
	}
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j ++) {
			if (a[i] > a[j]) {
				any[i] ++;
				if (i < j) {
					right[i]++;
				}
			}
		}
	}
	long long mod = 1000000007LL;
	long long ans = 0;
	long long x = (K * (K - 1) / 2) % mod;
	for (int i = 0; i < N; i++) {
		ans += (any[i] * x) % mod;
		ans %= mod;
		ans += (right[i] * K) % mod;
		ans %= mod;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 888
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        // 宣言
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> octBalls = new ArrayList<>();
        
        // 入力値取得
        int n = sc.nextInt();
        
        for(int i=0;i<n;i++){
            octBalls.add(sc.nextInt());
        }
        
        int total = 0;
        int pattern = (n * (n-1)) / 2; 
        // 
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(!(k <= j)){
                    total = total + (octBalls.get(j) * octBalls.get(k));                    
                }
                continue;
            }
        }

        System.out.println(total);
    }
}


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

int main(){
  string A,B;
  cin >> A;
  cin >> B;
  if(A.size()>B.size()){
    cout << "GREATER" << endl;
  }else if(A.size()<B.size()){
    cout << "LESS" << endl;
  }else{
    for(long long i=0;i<A.size();i++){
      if(A[i]>B[i]){
        cout << "GREATER" << endl;
        return 0;
      }else if(A[i]<B[i]){
        cout << "LESS" << endl;
        return 0;
      }else if(i==A.size()-1){
        cout << "EQUAL" << endl;
        return 0;
      }
    }
  }
  return 0;
}

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

ll lcm(ll c, ll d) { return c / __gcd(c, d) * d; }

ll f(ll x, int c, int d) {
  ll res = x;
  res -= x / c;  // 全体からcで割り切れる数をひく = cで割り切れない数
  res -= x / d;  // 全体からdで割り切れる数をひく = dで割り切れない数

  // 全体から重複して引いた数を足し戻す（cとdの最小公倍数の倍数の数）
  res += x / lcm(c, d);

  return res;
}

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

  ll a, b;
  int c, d;
  cin >> a >> b >> c >> d;

  ll ans = f(b, c, d) - f(a - 1, c, d);

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
/*
int main(){
	int n,m,tmp1,tmp2;
	cin>>n>>m;
	vector<int> a(n);
	vector<int> map(100000,0);
	rep(i,n) cin>>a[i];
	rep(i,m){
		cin>>tmp1>>tmp2;
		if(map[tmp1]<tmp2&&tmp1<tmp2){
			map[tmp1]=tmp2;
		}
	}
	int sum=0;
	rep(i,n){
		if(a[i]<map[a[i]]){
			sum+=map[a[i]];
			cout<<map[a[i]]<<endl;
		}else{
			sum+=a[i];
			cout<<a[i]<<endl;
		}
	}
	cout<<sum<<endl;
	return 0;
}
*/
class Pair{
	public:
		int x,y;
		Pair(void){};
		Pair(int a,int b):x(a),y(b){};
	bool operator <(const Pair &r)const{
		return (y>r.y);
	}
};
	
int main(){
	int n,m,tmp1,tmp2;
	cin>>n>>m;
	vector<int> a(n);
	vector<Pair> b(m);
	rep(i,n) cin>>a[i];
	rep(i,m){
		cin>>tmp1>>tmp2;
		Pair tmp(tmp1,tmp2);
		b[i]=tmp;
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	//rep(i,n) cout<<a[i]<<' ';
	//cout<<endl;
	int head=0;
	rep(i,m){
		rep(j,b[i].x){
			if(head<a.size()){
				if(a[head]<b[i].y){
					a[head]=b[i].y;
					head++;
				}else{
					break;
				}
			}else{
				break;
			}
		}
	}
	long long int sum=0;
	//rep(i,n) cout<<a[i]<<' ';
	//cout<<endl;
	rep(i,n) sum+=a[i];
	cout<<sum<<endl;

	return 0;
}

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

int main()
{

  int test,i,j,num,m;
  cin>>num;
  cin>>m;
  
  int arr[num];
   int total=0;

   for(i=0;i<num;i++){
    cin>>arr[i];
    total+=arr[i];
}
  
 

int count=0;
for(i=0;i<num;i++)
{
	if(4*m*arr[i]>=total)
		count++;
}

if(count>=m)
cout<<"Yes"<<endl;

else 
cout<<"No"<<endl;

return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;


int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i,n) cin >> a[i];
  vector<ll> num(n+1,0);
  rep(i,n) num[i+1] = num[i] + a[i];
  ll x = num[n] / 2;
  auto itr = lower_bound(num.begin(), num.end(), x) - num.begin();
  ll res1 = abs(num[itr] - (num[n] - num[itr]));
  ll res2 = abs(num[itr-1] - (num[n] - num[itr-1]));
  cout << min(res1, res2) << endl;
  return 0;
} 

Measured memory_bytes: 3328
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

char s[111111];
int n,a,b,now,nowb;

int main()
{
   cin>>n>>a>>b;
    cin>>s;
    now =0;
    nowb=0;
    for (int i = 0; i < n; ++i){
        if(s[i]=='a'){
            if (now<a+b)
            {
                cout<<"Yes"<<endl;
                now++;
            }else cout<<"No"<<endl;
        }
        if(s[i]=='b'){
            if (now<a+b&&nowb<b)
            {
                cout<<"Yes"<<endl;
                now++;
                nowb++;
            }else cout<<"No"<<endl;
        }
        if(s[i]=='c'){
            cout<<"No"<<endl;            
        }
    }








    return 0;
}

Measured memory_bytes: 768
n, m = (int(i) for i in input().split())
p = [None] * m
s = [None] * m
for i in range(m):
    p[i], s[i] = (j for j in input().split())
    p[i] = int(p[i])
    
pena = [0] * n
ac   = [0] * n

for i in range(m):
    q_index = p[i]-1
    if s[i] == 'AC': 
        ac[q_index] = 1
    if s[i] == 'WA':
        if ac[q_index] == 0: pena[q_index] += 1
        
ac_num = 0
pena_num = 0
for i in range(n):
    if ac[i] == 1:
        ac_num += 1
        pena_num += pena[i]

print(ac_num, pena_num)
        

Measured memory_bytes: 14884
#C
X,N=map(int,input().split())
P=list(map(int,input().split()))

flag=[False for i in range(102)]

for i in P:
    flag[i]=True

d=0
while True:
    if not flag[X-d]:
        ans=X-d
        break
    elif not flag[X+d]:
        ans=X+d
        break
    d+=1
print(ans)

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

#define fi first
#define se second
#define long long long
typedef pair<int,int> ii;

int main()
{
	// freopen("input.in", "r", stdin);
	int x, y;
	scanf("%d %d", &x, &y);
	if(x == 1 && y == 1) printf("1000000\n");
	else printf("%d\n", ((x > 3)? 0 : (4-x)*100000)+((y > 3)? 0 : (4-y)*100000));
}

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

using namespace std;

int main() {
    string S;
    cin >> S;

    if (S == "SUN")
    {
        cout << 7 << endl;
    }
    else if (S == "MON")
    {
        cout << 6 << endl;
    }
        else if (S == "TUE")
    {
        cout << 5 << endl;
    }
        else if (S == "WED")
    {
        cout << 4 << endl;
    }
        else if (S == "THU")
    {
        cout << 3 << endl;
    }
        else if (S == "FRI")
    {
        cout << 2 << endl;
    }
        else if (S == "SAT")
    {
        cout << 1 << endl;
    }
    
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int main() {
    int n;
    long long A=1,B=1;
    cin>>n;
    for(int i=1;i<=n;i++) {
	int x=gi(),y=gi();
	A=(A+x-1)/x*x,B=(B+y-1)/y*y;
	B=max(B,A/x*y),A=max(A,B/y*x);
    }
    cout<<A+B;
    return 0;
}

Measured memory_bytes: 256
//QWsin
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

typedef long long ll;
const int INF=1<<30;

const int maxn=100+10;

int a[maxn],k,n;
char s[maxn];

ll Pow(ll x,int p){
	ll ret=1;
	rep(i,1,p) ret*=x;
	return ret;
}

ll C(int n,int m){
	if(n<0||m<0||n<m) return 0;
	ll ret=1;
	rep(i,0,m-1) ret*=(n-i);
	rep(i,1,m) ret/=i;
	return ret;
}


int main()
{
	scanf("%s%d",s+1,&k);
	n=strlen(s+1);
	rep(i,1,n) a[i]=s[i]-'0';
	rep(i,1,n/2) swap(a[i],a[n+1-i]);
	ll ans=C(n-1,k)*Pow(9,k);//最高位为0 
	int p1=n-1,p2;
	while(p1>=1 && a[p1]==0) --p1;
	p2=p1-1;
	while(p2>=1 && a[p2]==0) --p2;
	 
	if(k==1)
	{ 
		ans+=(a[n]);
	}
	if(k==2)
	{
		ans+=(a[n]-1)*C(n-1,k-1)*Pow(9,k-1);//最高位小 
		if(p1>0)ans+=1*C(p1-1,k-1)*Pow(9,k-1);
		if(p1>0)ans+=(a[p1]);//最高位一样 ，次高位不为0 
	}
	if(k==3)
	{
		ans+=(a[n]-1)*C(n-1,k-1)*Pow(9,k-1);//最高位小 
		if(p1>0)ans+=1*C(p1-1,k-1)*Pow(9,k-1);//最高位抵着，次高位为0 
		if(p1>0)ans+=(a[p1]-1)*(p1-1)*9;//最高位抵着，次高位小 
		if(p2>0)ans+=1*1*(p2-1)*9;//最高位抵着，次高位抵着，次次高位为0 
		if(p2>0)ans+=(a[p2]);	
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())

ashiba_list = list(map(int,input().split()))

dp = [0 for _ in range(n)]

for i,ashiba in enumerate(ashiba_list):
    if i==1:
        dp[i] = abs(ashiba_list[i]-ashiba_list[i-1])
    elif i>1:
        costs = []
        for jump in range(1,k+1):
            if jump <=i:
                costs.append(dp[i-jump]+abs(ashiba_list[i]-ashiba_list[i-jump]))
        dp[i] += min(costs)
print(dp[n-1])

Measured memory_bytes: 56192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,a[100000];
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  ll ans=a[0]-1,t=2;
  for(int i=1;i<n;i++){
    if(a[i]==t)t++;
    if(a[i]>t){
      if(a[i]%t)ans+=a[i]/t;
      else ans+=((a[i]-t)/t);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W; 
  
  for (int i=0; i < W+2; i++){
  cout << "#" ;
  }
 
  cout << endl;
  
 for(int j=0; j<H; j++){
  
  cout << "#";
  
  string S;
  cin >> S;
  
  cout << S << "#" <<endl;
   
 }
for (int i=0; i < W+2; i++){
  cout << "#" ;
  }
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
const int K = 4226;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int mod = 1e9 + 7;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
int smdi(int a)
{
	int sum = 0;
	while(a)
	{
		sum += (a % 10);
		a = a / 10;
	}
	return sum;
}
		
signed main(){
	int n; cin >> n;
	int ans = 1e8;
	for(int i = 1 ; i < n ; ++i)
	{
		int a = i, b = n - i;
		ans = min(ans , smdi(a) + smdi(b));
	}
	cout << ans;
}
		
	

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll D, N;
    cin >> D >> N;
    ll times = pow(100, D);
    if (N == 100) {
        cout << times * (N + 1) << endl;
    } else {
        cout << times * N << endl;
    }
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
#include <math.h>
using namespace std;
int main(){
    int n,m;
    string s="Impossible";
    cin>>n>>m;
    if(n%3==0||m%3==0||((n+m)%3==0)){
        s="Possible";
    }
    cout<<s<<endl;
    
    return 0;
}


Measured memory_bytes: 3632
N, K = map(int, input().split())
lst = [0]
for x in [int(x) for x in input().split()]:
    lst.append(lst[-1] + ((1 + x) / 2))

ret = 0
for i in range(N - K + 1):
    ret = max(ret, lst[i + K] - lst[i])
print(ret)


Measured memory_bytes: 25188
#include <stdio.h>

double roundoff (double a, double b);

int main () {
	double coe[6], x, y, numeratorX, numeratorY, denominator;
	int i;
	//Initialization
	i = 0;
	x = 0;
	y = 0;
	numeratorX = 0;
	numeratorY = 0;
	denominator = 0;
	
	for (i = 0;i < 6;i++) {
		coe[i] = 0;
	}
	
	while (scanf ("%lf %lf %lf %lf %lf %lf", &coe[0], &coe[1], &coe[2], &coe[3], &coe[4], &coe[5]) != EOF) {
		numeratorX = coe[4] * coe[2] - coe[1] * coe[5];
		numeratorY = coe[0] * coe[5] - coe[2] * coe[3];
		denominator = coe[0] * coe[4] - coe[1] * coe[3];
		x = roundoff (numeratorX, denominator);
		y = roundoff (numeratorY, denominator);
		printf ("%.3lf %.3lf\n", x, y); 
	}
	return 0;
}

double roundoff (double a, double b) {
	if (a == 0) {
		return 0.000;
	} else if ((a / b) < 0) {
		return -((int) (-(a/b) * 1000 + 0.5)) / 1000.0;
	} else {
		return ((int) ((a/b) * 1000 + 0.5)) / 1000.0;
	}
}

Measured memory_bytes: 652
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}
fn solve(aa: Vec<usize>) -> Vec<usize> {
    let n = aa.len();
    let mut b = vec![0; n];

    for (i, &a) in aa.iter().rev().enumerate() {
        if i % 2 == 0 {
            b[i/2] = a;
        } else {
            b[n-1 - i/2] = a;
        }
    }

    b
}

fn main() {
    read_line!();

    let aa = parse_vec!(usize);
    println!("{}", solve(aa).iter().map(|a| a.to_string()).collect::<Vec<String>>().join(" "));
}

#[test]
fn solve_test() {
    assert_eq!(solve(vec![1,2,3,4]), vec![4,2,1,3]);
    assert_eq!(solve(vec![1,2,3]), vec![3,1,2]);
    assert_eq!(solve(vec![1000000000]), vec![1000000000]);
}


Measured memory_bytes: 18540
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n,q;
  cin>>n>>q;
  using T = tuple<double, double, double>;
  vector<T> v;
  REP(i,n) {
    double s,t,x;
    cin>>s>>t>>x;
    v.emplace_back(s-0.5-x,t-0.5-x,x);
  }
  sort(ALL(v));
  set<tuple<double,double,double>> active_ranges;
  active_ranges.emplace(1e10, -1e10, 1e10);
  auto itr = begin(v);
  REP(i,q) {
    double d;
    cin>>d;
    while (itr != end(v)) {
      double s,t,x;
      tie(s,t,x) = *itr;
      if (s > d) {
        break;
      }
      active_ranges.emplace(x, s, t);
      ++itr;
    }
    while (true) {
      double x,s,t;
      tie(x,s,t) = *begin(active_ranges);
      if (t > d) {
        break;
      }
      active_ranges.erase(begin(active_ranges));
    }
    double dist = get<0>(*begin(active_ranges));
    if (dist < 1e10) {
      cout << static_cast<int>(dist) << endl;
    } else {
      cout << -1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 19692
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRTV(v) sort(v.begin(),v.end())
#define SRTAG(a,n) sort(a,a+n,greater<>())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    //入力
    string s;
    cin >> s;
  	bool ans = true;
    //処理
  	REP(i,0,s.length()){
    	REP(j,i+1,s.length()){
        	if(s[i]==s[j]) ans = false;
        }
    }
  
    //出力
    if(ans) cout << "yes" << ENT;
    else cout << "no" << ENT;
    return 0;
}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

// nCr mod を計算する O(n)
const int MAX_N = 1000010;
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX_N; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
    ll x,y;
    cin>>x>>y;

    if((2*y-x)%3!=0 || (2*x-y)%3!=0){
        cout<<0<<endl;
        return 0;
    } 

    int a=(2*y-x)/3,b=(2*x-y)/3;
    
    COMinit();
    cout<<COM(a+b,a)<<endl;

}




Measured memory_bytes: 23680
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
template <typename T>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};
#define Graph(type) vector< vector< Edge<type> > >

int main() {
    int V, E, start;
    cin >> V >> E >> start;

    Graph(int) G(V);
    for(int i=0; i<E; i++) {
        int s, t, d; cin >> s >> t >> d;
        G[s].push_back(Edge<int>(t, d));
    }

    map<int, int> m;
    vector<bool> inq(V, false);
    queue<int> que;
    vector<int> rec(V, 1 << 30);
    que.push(start);
    inq[start] = true;
    rec[start] = 0;

    while(!que.empty()) {
        int point = que.front(); que.pop();
        inq[point] = false;
        for(size_t i=0; i<G[point].size(); i++) {
            Edge<int> next = G[point][i];
            int to = next.to, cost = next.cost;
            if(rec[to] > rec[point] + cost) {
                rec[to] = rec[point] + cost;
                if(!inq[to]) {
                    if(++m[to] >= V) {
                        cout << "NEGATIVE CYCLE" << endl;
                        return 0;
                    }
                    inq[to] = true;
                    que.push(to);
                }
            }
        }
    }
    for(int i=0; i<V; i++) {
        if(rec[i] != 1<<30) cout << rec[i] << endl;
        else cout << "INF" << endl;
    }
    return 0;
}

Measured memory_bytes: 3188
from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Measured memory_bytes: 94356
# -*- coding: utf-8 -*-

a, b, c, d = map(str, input())

sign = "+-"
for i in range(2):
    for j in range(2):
        for k in range(2):
            if int(eval(a+sign[i]+b+sign[j]+c+sign[k]+d)) == 7:
                print(str(a+sign[i]+b+sign[j]+c+sign[k]+d) + "=7")
                exit()



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

#define ll long long 
#define d  double 
#define endl "\n"

const ll int MOD=1e9+7;

void solve()
{
	int x,n,y,z,ans,i;
	cin >> x >> n;
	vector<int> v(n);
	for(i=0;i<n;i++)
		cin >> v[i];
	sort(v.begin(),v.end());
	y=x;
	while(binary_search(v.begin(),v.end(),y)!=0)
		y++;
	z=x;
	while(binary_search(v.begin(),v.end(),z)!=0)
		z--;
	if(abs(x-z)<=abs(x-y))
		ans = z;
	else
		ans = y;
	cout << ans << endl;
}

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

	solve();
	return 0;
}

Measured memory_bytes: 3656
#include<iostream>
#include<cstdlib>
#include<stack>
using namespace std;

int main() {
    stack<int> S;
    int a, b, x;
    string s;
    
    while( cin >> s) {
        if( s[0] == '+') {
            a = S.top(); S.pop();
            b = S.top(); S.pop();
            S.push(a + b);
        } else if (s[0] == '-') {
            b = S.top(); S.pop();
            a = S.top(); S.pop();
            S.push(a - b);
        } else if (s[0] == '*') {
            a = S.top(); S.pop();
            b = S.top(); S.pop();
            S.push(a * b);
        } else {
            S.push(atoi(s.c_str()));
        }
    }
    cout << S.top() << endl;
    
    return 0;
}


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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <class F,class ...S> void dbg(const F& f, const S&...s){cerr <<f <<": "; dbg(s...);}

typedef tuple<int, int, int> T3;
int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	
	VI sk(n+100);
	
	rep2(i, 1, n+1){
		for(int j=0; j<=n ; j+=i) sk[j]++;
	}
	ll ans = 0;
	rep2(i, 1, n+1) ans += (ll)i * sk[i];
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 42220
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         long N = Long.parseLong(st.nextToken());
         long K = Long.parseLong(st.nextToken());
         long res = N%K;
         if(res > 0)
            res = Math.min(res, K-res);
         System.out.println(res);
      }
   }

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

int main(){

    string s;
    int k;

    cin >> s >> k;

    set<string> a;

    for(int i=1;i<=min((int)s.size(),k);i++){
        for(int j=0;j+i<=s.size();j++){
            string t=s.substr(j,i);
            a.insert(t);
        }
    }

    auto it=a.begin();

    rep(i,k-1) it++;

    cout << *it << endl;

    return 0;
}

Measured memory_bytes: 1664
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<time.h>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<limits>
using namespace std;
const int INF = 0x3f3f3f3f;
using ll = long long;
using vs = vector<string>;
using vi = vector<int>;

int cntDigists(ll n){
    int digits = 1;
    while(n/10)
    {
        digits++;
        n = n/10;
    }
    return digits;
}


void p2() {
    string O,E;
    cin >> O;
    cin >> E;
    string result;

    for(int i=0; i<O.size(); ++i){
        result += O[i];
        if(i < E.size())
        result += E[i];
    }

    cout << result << endl;

}


int main()
{
   //freopen("in.txt", "r", stdin);
    p2();
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    int H,W;
    for(int a = 0; a < 100; a++){
        cin >> H >> W ;
        if (H == 0 && W == 0) break;
        for(int b = 0; b < H; b++){
            for(int c = 0; c < W; c++){
                if(b == 0 || c == 0 || c == W - 1 || b == H - 1){
                    cout << "#";
                } else {
                    cout << ".";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


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

typedef long long ll;

vector<vector<ll>> dp_arr;
ll calcDiff(vector<ll>& arr, int i, int j)
{
	if(i > j)
		return 0;
	if(dp_arr[i][j] != -1)
		return dp_arr[i][j];
	ll a = arr[i] - calcDiff(arr, i+1,j);
	ll b = arr[j] - calcDiff(arr, i,j-1);
	dp_arr[i][j] = max(a,b);
	return dp_arr[i][j];
}

int main()
{
	int n;
	cin >> n;
	vector<ll> arr(n);
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	dp_arr.resize(n+1, vector<ll>(n+1, -1));
	ll res = calcDiff(arr, 0, n-1);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 70912
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
def lcm(x, y):
    return (x * y) // gcd(x, y)
n=int(input())
tmp1=int(input())
ans=tmp1
for i in range(n-1):
    tmp2=int(input())
    ans=lcm(tmp1,tmp2)
    tmp1=ans
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
int main(){
    int a,h,m,m1,s;
    scanf("%d%d",&a,&m);
    if(a>m)printf("a > b\n");
    else if(a<m)printf("a < b\n");
    else if(a==m)printf("a == b\n");
    return 0;
}



Measured memory_bytes: 2048
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}

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

    string a ;
    cin >> a;

    rep(i ,a.size()){
        if(i == 0) continue;
        if(a[i] == a[i-1]){
            cout << "Bad" << endl ;
            return 0;
        }
    }

    cout << "Good" << endl;

    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


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

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

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

  sort(word,word+n);

  for( int i=0; i<n; i++ ){
    cout << word[i];
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))
cnt = 0
for i in range(n):
    while h[i] > 0:
        for j in range(i, n):
            if h[j] != 0:
                h[j] -= 1
            else:
                cnt += 1
                break
        else:
            cnt += 1
print(cnt)

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

const long long MAX = 2000005;
const long long MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    COMinit();
    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    cout << (COM(r2+c2+2,r2+1)-COM(r2+c1+1,r2+1)-COM(r1+c2+1,r1)+COM(r1+c1,r1)+MOD+MOD)%MOD << endl;
}


Measured memory_bytes: 47104
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll mod = 1000000007;
int main(){
  int K, A, B;
  cin >> K;
  cin >> A >> B;

  for(int i=A;i<=B;i++){
    if(i%K==0){
      cout << "OK" <<endl;
      return 0;
    }
  }
  cout << "NG" <<endl;


  return 0;
}


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

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

  int ans = 0;
  for (ans = 1; ans <= 1000; ans++) {
    int a, b;
    a = floor(ans * 0.08);
    b = floor(ans * 0.10);

    if ((a == A) && (b == B)) {
      cout << ans << endl;
      return 0;
    }
  }

  cout << -1 << endl;
  return 0;
}


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

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 998244353;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

const ll MAX = 2000000;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll pow_mod(ll n, ll k)
{
    if (k == 0)
    {
        return 1;
    }
    else if (k % 2 == 1)
    {
        return pow_mod(n, k - 1) * n % MOD;
    }
    else
    {
        ll t = pow_mod(n, k / 2);
        return t * t % MOD;
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    COMinit();
    ll n;
    cin >> n;
    vector<ll> x(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        (ans += pow_mod(2, n - i) * ((pow_mod(1 + x[i - 1], i) - pow_mod(1 + x[i - 1], i - 1) + MOD) % MOD)) %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 57352
import java.util.*;
import java.io.InputStreamReader;
import java.io.BufferedReader;


public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] t = new int[n+1];
        int[] x = new int[n+1];
        int[] y = new int[n+1];
        
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            t[i+1] = Integer.parseInt(s[0]);
            x[i+1] = Integer.parseInt(s[1]);
            y[i+1] = Integer.parseInt(s[2]);
        }
        
        int diff;
        boolean flag = true;
        for (int i = 1; i <= n; i++) {
            diff = Math.abs(x[i]-x[i-1]) + Math.abs(y[i]-y[i-1]);
            if (t[i]-t[i-1] >= diff && (t[i]-t[i-1])%2 == diff%2) continue;
            else {
                flag = false;
                break;
            }
        }
        
        System.out.println(flag?"Yes":"No");
    }
}





Measured memory_bytes: 45196
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
    int sum,n,m,p,q,t,a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    sum=1200000000;
    n=a*x+b*y;
   if(x>=y)
   {
      m=2*y*c+(x-y)*a;
   }else m=1200000000;
   if(y>=x)
   {
       p=2*x*c+(y-x)*b;
   }else p=1200000000;
   if(x>=y)
   {
       q=2*c*x;
   }else q=1200000000;
   if(y>=x)
   {
       t=2*c*y;
   }else t=1200000000;
   if(n<sum)
    sum=n;
   if(m<sum)
    sum=m;
   if(p<sum)
    sum=p;
   if(q<sum)
    sum=q;
   if(t<sum)
    sum=t;
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256