akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define llu unsigned long long 
#define pb push_back
#define loop(x) for(int i=0;i<x;i++)
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
#define dd fflush(stdout)
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mt make_tuple //use tie
#define eb emplace_back
typedef tuple<int,int,int> State;//use in dijkstra
ll mod=1e9+7;
// ll power(ll x,ll y,ll mod){
//  ll ans=1;
//  while(y>0){
//   if(y&1){
//     ans=ans*x;
//   }
//   x=x*x;
//   y=y/2;
//  }
//  return ans;
// }

int main(){
    // IOS;  
     int n,k;
     cin>>n>>k;
     //ll a[n+2];
     int x;
     vector<ll> dp(k+3);
     //dp[i] will store the number of ways to distributes 
     //i candies till now .
     dp[0]=1;
     ll sum[k+2]={0};
     for(int i=0;i<n;i++){
      cin>>x;
      for(int j=0;j<=k;j++)
      {
        sum[j]=(((j>0)?sum[j-1]:0)+dp[j])%mod;
      }
      for(int j=k;j>=0;j--){
        //here i can use only c candies.
        int r=j-1;
        int l=j-min(x,j);
        // cout<<l<<" "<<r<<endl;
        if(r>=l)
          dp[j]=(dp[j]+sum[r]-((l>0)?sum[l-1]:0)+mod)%mod;
         
      }
     }
     cout<<dp[k]<<endl;
 }
 

Measured memory_bytes: 1792
N = int(input())
X = list(map(int,input().split()))
X_sorted = sorted(X)
midNL = X_sorted[N//2-1]
midNR = X_sorted[N//2]
for i in range(N):
    if X[i] <= midNL:
        print(midNR)
    else:
        print(midNL)

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

const int N = 105;
typedef long long LL;

int n;
char s[N];
LL ans, f[N][3], k, g[N][3];

int main() {
	cin>>(s + 1)>>k;
	n = strlen(s + 1);
	f[1][0] = 0, f[1][1] = 0, f[1][2] = 1;
	g[1][0] = 1, g[1][1] = 1e9, g[1][2] = 1;
	for(int i = 2; i <= n; i++) {
		if(s[i] == s[i - 1]) {
			f[i][1] = f[i - 1][2];
			f[i][2] = f[i - 1][0] + 1;
			g[i][1] = g[i - 1][2];
			g[i][2] = g[i - 1][0] + 1;
		}
		else {
			f[i][1] = f[i - 1][0];
			f[i][2] = f[i - 1][0] + 1;
			g[i][1] = g[i - 1][0];
			g[i][2] = g[i - 1][0] + 1;
		}
		g[i][0] = min(g[i][1], g[i][2]);
		f[i][0] = min(f[i][1], f[i][2]);
	}
	if(s[1] != s[n]) 
		cout<<f[n][0]*k<<endl;
	else {
		ans = min(f[n][2]*(k - 1) + f[n][0], g[n][0]*(k - 1) + f[n][0]);
		if(k&1) ans = min(ans, f[n][0]*(k + 1)/2 + g[n][2]*(k - 1)/2);
		else ans = min(ans, f[n][0]*k/2 + g[n][2]*(k/2 - 1) + g[n][0]);
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define rep2(i, s, n) for (int i = s; i < (int)n; i++)
#define all(obj) obj.begin(), obj.end()
#define debug(x) cerr << #x << ":" << x << "\n"
#define vdebug(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define YN(f) cout << (f ? "YES" : "NO") << endl
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main () {
	int N, Q; cin >> N >> Q;
	vi val(N + 1);
	vector<set<int>> out(N + 1);	
	int a, b;
	rep(i, N - 1) {
		cin >> a >> b;
		out.at(a).insert(b);
		out.at(b).insert(a);
	}
	int p, x;
	rep(i, Q) {
		cin >> p >> x;
		val.at(p) += x;
	}

	queue<int> q;
	q.push(1);
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int v : out.at(u)) {
			val.at(v) += val.at(u);
			q.push(v); out.at(v).erase(u);
		}
	}	

	rep2(i, 1, N + 1) cout << val.at(i) << " ";
}

Measured memory_bytes: 31872
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
struct Job {
	char name[20];
	int time;
	Job() {}
	Job(char *c, int t) {
		strcpy(name, c);
		time = t;
	}
};
struct Queue {
	int b, e, len;;
	Job j[100000];
	Queue() {
		len = 100000;
		b = 0;
		e = 0;
	}
	Job front() {
		Job ret = j[b];
		b = (b + 1) % len;
		return ret;
	}
	void push(Job in) {
		j[e] = in;
		e = (e + 1) % len;
	}
	bool empty() {
		return b == e;
	}
};
signed main() {
	int n, q; cin >> n >> q;
	int now = 0;
	static Queue m;
	rep(i, 0, n) {
		char c[20]; int t;
		scanf("%s %d", c, &t);
		m.push(Job(c, t));
	}
	while (!m.empty()) {
		Job tmp = m.front();
		//printf("debug : %s %d\n", tmp.name, tmp.time);
		int x = min(q, tmp.time);
		now += x;
		tmp.time -= x;
		if (tmp.time == 0) {
			printf("%s %d\n", tmp.name, now);
		}
		else {
			m.push(tmp);
		}
	}
	return 0;
}

Measured memory_bytes: 5552
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) { 
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

bool f(const vector<pint> &data1, const vector<pint> &data2) {
  int sum1 = 0, sum2 = 0;
  REP(i, data1.size()) {
    if(sum1 - data1[i].first < 0) return false;
    sum1 += data1[i].second;
  }
  REP(i, data2.size()) {
    if(sum2 - data2[i].first < 0) return false;
    sum2 += data2[i].second;
  }
  //  cout << sum1 << ";" << sum2 << endl;
  return sum1 == sum2;
}

int main() {
  int N; cin>>N;
  vector<string> S(N);
  REP(i,N) cin>>S[i];
  vector<pint> data1, data2;
  REP(i,N) {
    int cnt = 0;
    REP(j, S[i].length()) {
      if(S[i][j] == '(') cnt++;
      else cnt--;
    }
    const int diff = cnt;
    cnt = 0;
    int min_v = 0;
    if(diff >= 0) {
      REP(j, S[i].length()) {
	if(S[i][j] == '(') cnt++;
	else cnt--;
	chmin(min_v, cnt);
      }
      data1.push_back(make_pair(-min_v, diff));
    } else {
      for(int j = S[i].length() - 1; j >= 0; j--) {
	if(S[i][j] == ')') cnt++;
	else cnt--;
	chmin(min_v, cnt);
      }
      data2.push_back(make_pair(-min_v, -diff));
    }
  }
  sort(data1.begin(), data1.end());
  sort(data2.begin(), data2.end());
#ifdef DEBUG
  REP(i, data1.size()) {
    cout << data1[i].first << "," << data1[i].second << endl;
  }
  REP(i, data2.size()) {
    cout << data2[i].first << ":" << data2[i].second << endl;
  }
#endif
  bool ret = f(data1, data2);
  YesNo(ret);
  return 0;
}


Measured memory_bytes: 34300
#include<bits/stdc++.h>
using namespace std;
int a[3005][3005];
signed main()
{
	string s,t;
	cin>>s>>t;
	int l=s.length();
	int n=t.length();
	for(int i=0; i<=l; i++)
	{
		for(int j=0; j<=n; j++)
		{
			if (min(i,j)==0)
				a[i][j]=0;
			else if (s[i-1]==t[j-1])
				a[i][j]=a[i-1][j-1]+1;
			else
				a[i][j]=max(a[i-1][j],a[i][j-1]);
		}
	}
	string ans="";
	int i=l,j=n;
	while(i>0 && j>0)
	{
			if (s[i-1]==t[j-1])
			{
				ans+=s[i-1];
				i-=1;
				j-=1;
			}
			else if (a[i-1][j]>a[i][j-1])
				i-=1;
			else
				j-=1;
	}
	reverse(ans.begin(),ans.end());
	cout<<ans;
}

Measured memory_bytes: 35456
from sys import stdin
n = int(stdin.readline())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*n for _ in range(n)]
dp1 = [[0]*n for _ in range(n)]
for i in range(n-1):
    dp1[i][i] = arr[i]
    dp[i][i+1] = arr[i]+arr[i+1]
    dp1[i][i+1] = arr[i]+arr[i+1]
dp1[-1][-1] = arr[-1]
for i in range(n-3,-1,-1):
    for j in range(i+2,n):
        dp[i][j] = 10**20
        for k in range(j-1,i-1,-1):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp1[i][k]+dp[k+1][j]+dp1[k+1][j])
        dp1[i][j] = dp1[i][j-1]+arr[j]
print(dp[0][-1])

Measured memory_bytes: 79832
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <math.h>
#include <queue>

using namespace std;
using ll = long long;

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

	ll div = N / (A + B);
	ll mod = N % (A + B);

	ll ans = div * A;
	if (mod > A) {
		ans += A;
	}
	else {
		ans += mod;
	}

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


Measured memory_bytes: 3636
using System;
using System.Linq;
using System.Collections.Generic;


namespace Test1 {

    class ClassMain {


        public static void rikuSearch(int[,] map, int y, int x) {
            if (y < 0 || map.GetLength(0) <= y || x < 0 || map.GetLength(1)<=x) { return; }
            if (map[y, x] == 0) { return; }
            map[y, x] = 0;
            rikuSearch(map, y + 1, x);
            rikuSearch(map, y - 1, x);
            rikuSearch(map, y , x+1);
            rikuSearch(map, y , x-1);
            rikuSearch(map, y + 1, x+1);
            rikuSearch(map, y + 1, x-1);
            rikuSearch(map, y - 1, x+1);
            rikuSearch(map, y - 1, x-1);        
        }

        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                int[] ints = line.Split(' ').Select(int.Parse).ToArray();
                int n = ints[0]; 
                //int n = int.Parse(line);                
                if(n==0){break;}
                int m = ints[1];

                int[] taros = new int[n];
                int tarosum = 0;
                int[] hanas = new int[m];
                int hanasum = 0;
                for (int i = 0; i < n; i++) {
                    int ttt = int.Parse(Console.ReadLine());
                    tarosum += ttt;
                    taros[i] = ttt;
                }
                for (int i = 0; i < m; i++) {
                    int hhh =  int.Parse(Console.ReadLine());
                    hanasum += hhh;
                    hanas[i] = hhh;
                }

                int minWa = int.MaxValue;
                int taroPass = -1;
                int hanaPass = -1;
                for (int i = 0; i < n; i++) {
                    tarosum -= taros[i];
                    hanasum += taros[i];
                    for (int j = 0; j < m; j++) {
                        hanasum -= hanas[j];
                        tarosum += hanas[j];

                        if (hanasum == tarosum) {
                            if (taros[i] + hanas[j] < minWa) { 
                                minWa = taros[i] + hanas[j];
                                taroPass = taros[i];
                                hanaPass = hanas[j];
                            }
                        }

                        hanasum += hanas[j];
                        tarosum -= hanas[j];
                    }
                    tarosum += taros[i];
                    hanasum -= taros[i];
                }
                if (minWa == int.MaxValue) {
                    Console.WriteLine(-1);
                }
                else {
                    Console.WriteLine(taroPass + " " + hanaPass);
                }



            }   
        }   
    }
}

Measured memory_bytes: 5904
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll a[maxn];
ll b[maxn];
int main() {
	int n;
	scanf("%d",&n);
	ll sum=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
	int num=(n-1)/2;
	ll res=sum;
//	printf("%d %d\n",num,sum);
	for(int i=1;i<=num;i++){
		res-=a[2*i-1]*2;
//		printf("%d\n",res);
	}
	b[n]=res;
	for(int i=n-1;i>=1;i--){
		b[i]=2*a[i]-res;
		res=b[i];
	}
	for(int i=1;i<=n;i++)printf("%lld ",b[i]);
	return 0;
}

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

int main()
{
  int n, k, q, a;
  cin >> n;
  cin >> k;
  cin >> q;
  
  vector<int> vec(n, k-q);  // length n, initial value k-q
  for (int i=0; i<q; i++){
	cin >> a;
	vec.at(a-1) += 1;
  }
  for (int i=0; i<n; i++){
	if (vec.at(i) > 0){
	  cout << "Yes" << endl;
	}else{
	  cout << "No" << endl;
	}
  }
}


Measured memory_bytes: 1024
L,R = map(int,input().split())

switch = (R-L+1)/2019
if switch < 1:
    answer = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            answer = min(answer, (i*j)%2019)
    print(answer)
else:
    print(0)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
#define mp make_pair
#define ff first
#define ss second
#define debug2(x,y) cout<<"("<<#x<<","<<#y<<") = ("<<(x)<<","<<(y)<<")\n"

int main(){
  int N,M;
  cin>>N>>M;
  vvi jobs(100010); // jobs[i]:=i日後にお金がもらえるバイトの報酬一覧
  // M=1でも1000日後報酬の仕事があるかも知れない
  int a,b;
  for(int i=0; i<N; i++){
    cin>>a>>b;
    jobs[a].pb(b);
  }
  priority_queue<int> que;

  int ans = 0;
  for(int i=1; i<M+1; i++){
    for(int x: jobs[i]){
      que.push(x);
    }
    if(que.empty())continue;
    int y = que.top();
    //debug2(y.ff, y.ss);
    que.pop();
    ans += y;
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 5632
#include<iostream>
#include<algorithm>
using namespace std;
int s[1000], k[10000], n, m, t, p, i, j;
int main() {
	while (true) {
		t = 0; p = 0;
		cin >> n >> m;
		if (n == -1) { break; }
		while (t < m) {
			n++;
			if (n < 2) { goto E; }
			for (i = 2; i*i <= n; i++) {
				if (n%i == 0) {
					goto E;
				}
			}
			s[t] = n;
			t++;
		E:;
		}
		for (i = 0; i < m; i++) { for (j = i; j < m; j++) { k[p] = s[j] + s[i]; p++; } }
		sort(k, k + p);
		cout << k[m - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

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

    vector<int> g(k+1);
    rep(x,k+1){
        set<int> s;
        rep(i,n)if(x-a[i] >= 0) s.insert(g[x-a[i]]);

        int r = 0;
        while(s.count(r)) ++r;
        g[x] = r;
    }

    string ans = "Second";
    if(g[k] != 0) ans = "First";
    cout << ans << "\n";
    return 0;
}


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

using namespace std;

typedef long long ll;

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

    double ans = (double) W * (double) H / 2;
    bool flag = x + x == W && y + y == H;
    printf("%lf %d\n", ans, flag);
}

Measured memory_bytes: 256
from collections import Counter

N = int(input())
a_list = list(map(int, input().split()))

res = 'Yes'

a_dict = Counter(a_list)


a_keys = list(a_dict.keys())
if len(a_keys) > 3:
    res = 'No'
elif len(a_keys) == 3:
    a, b, c = a_keys
    if a_dict[a] != a_dict[b]:
        res = 'No'
    if a_dict[a] != a_dict[c]:
        res = 'No'
    if a ^ b != c:
        res = 'No'
    if b ^ c != a:
        res = 'No'
    if c ^ a != b:
        res = 'No'
elif len(a_keys) == 2:
    a, b = a_keys
    if a_dict[a] == 2 * a_dict[b]:
        if b != 0:
            res = 'No'
    elif 2 * a_dict[a] == a_dict[b]:
        if a != 0:
            res = 'No'
    else:
        res = 'No'
else:
    a = a_keys[0]
    if a != 0:
        res = 'No'
print(res)


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

#define endl '\n'
#define int long long

const int N = 110, V = 1e5+9;
int cache[N][V], items[N][2], n, w;
bool vis[N][V];

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

	cin >> n >> w;
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j < 2; j ++) {
			cin >> items[i][j];
		}
	}
	cache[0][0] = w;
	vis[0][0] = 1;
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j <= V; j ++) {
			cache[i][j] = cache[i-1][j];
			vis[i][j] = vis[i-1][j];
		}
		for(int j = V; j >= 0; j --) {
			if(vis[i][j]) {
				if(cache[i][j] - items[i][0] >= 0) {
					cache[i][j + items[i][1]] = max(cache[i][j + items[i][1]], cache[i][j] - items[i][0]);
					vis[i][j + items[i][1]] = 1;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < V; i ++) {
		if(vis[n][i]) {
			ans = i;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 91504
import java.util.*;
 
public class Main { 
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long k = sc.nextLong();
		int[] to = new int[n+1];
		int[] moved = new int[n+1];
		for(int i=1; i<=n; i++){
			to[i] = sc.nextInt();
		}
		int now = 1;
		moved[now]++;
		int end = 0;
		int roopCount = 0;
		for(int i=0; i<=to.length; i++){
			if(moved[to[now]] > 0){
				end = to[now];
				roopCount++;
				break;
			}
			now = to[now];
			moved[now]++;
			roopCount++;
			if(k == roopCount){
				System.out.println(now);
				return;
			}
		}
		int roopStartCount = 0;
		if(end != 1){
			now = 1;
			for(int i=0; i<=to.length; i++){
				if(to[now] == end){
					roopStartCount++;
					break;
				} 
				now = to[now];
				roopStartCount++;
			}
		}
		roopCount -= roopStartCount;
		long mod = (k-roopStartCount)%roopCount;
		for(long i=mod; i>0; i--){
			end = to[end];
		}
		System.out.println(end);

	}
}


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

int main(){
	int N,K;
	cin >> N >> K;
	vector<long long> H(N);
	for(auto &i:H)cin >> i;
	sort(H.begin(),H.end());
	long long ans=0;
	for(int i=0;i<N-K;i++)ans+=H[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
#include <string>

using namespace std;

int a[8];
int d[4] = {-1, 1, -4, 4};

map<string, int> mymap;

void bfs() {
    queue<string> q;
    q.push("01234567");
    mymap["01234567"] = 0;
    
    while (!q.empty()) {
        string cur = q.front(); q.pop();
        string next;
        int p = (int)cur.find("0");
        for (int i = 0; i < 4; i++) {
            int np = p + d[i];
            if (np >= 0 && np < 8 && (p != 3 || d[i] != 1) && (p != 4 || d[i] != -1)) {
                next = cur;
                next[np] = '0';
                next[p] = cur[np];
                if (mymap.find(next) == mymap.end()) {
                    mymap[next] = mymap[cur] + 1;
                    q.push(next);
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    bfs();
    while (cin >> a[0]) {
        for (int i = 1; i < 8; i++) {
            cin >> a[i];
        }
        string s = "";
        for (int i = 0; i < 8; i++) {
            s += a[i] + '0';
        }
        if (mymap.find(s) == mymap.end()) {
            cout << -1 << endl;
        } else {
            cout << mymap[s] << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 5228
#include<bits/stdc++.h>
#define maxn 100005
#define LL long long
using namespace std;
LL mod=1e9+7;
LL Pow(LL x,int y)
{
	if(y==0) return 1ll;
	if(y==1) return x;
	LL a=Pow(x,y/2);
	a=(a*a)%mod;
	if(y&1) return (a*x)%mod;
	return a;
}
int a[maxn];
bool use[maxn];
LL fac[maxn],inv[maxn];
LL C(int n,int i)
{
	if(i>n) return 0ll;
//	cout<<n<<" "<<i<<endl;
	return (((fac[n]*inv[i])%mod)*inv[n-i])%mod;
}
int main()
{
	int n;
	int pos1,pos2;
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)
	{
		scanf("%d",&a[i]);
		if(use[a[i]]){pos2=i;break;}
		use[a[i]]=1;
	}
	for(int i=1;i<=n;i++)
		if(a[i]==a[pos2])
			{pos1=i;break;}
	inv[0]=fac[0]=1ll;
	for(int i=1;i<=n+1;i++)
		fac[i]=(fac[i-1]*i)%mod;
	inv[n+1]=Pow(fac[n+1],mod-2)%mod;
	for(int i=n;i>=1;i--)
		inv[i]=inv[i+1]*(LL)(i+1)%mod;
	n++;
	for(int i=1;i<=n;i++)
	{
		LL ans=C(n,i);
		ans-=C(n-pos2+pos1-1,i-1);
		while(ans<0) ans+=mod;
		printf("%lld\n",ans);
	}
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define int long long
using namespace std;
using Graph = vector<vector<int>>;
const int MOD = 1000000007;

signed main() {
  int H, W;
  cin >> H >> W;
  
  int ans = 10000000000;
  
  if( H%3 == 0 || W%3 == 0 ){
    cout << 0 << endl;
    return 0;
  }
  
  ans = min(H, W);
 
  //一度縦で分割
  for( int i = 1; i <= W; i++ ){
    int A = H*i;
    int B, C;
    if( H%2 == 0 ){
      B = (W-i)*(H/2);
      C = (W-i)*(H/2);
    }else{
      B = (W-i)*(H/2);
      C = (W-i)*(H/2+1);
    }
    int sa = max({abs(A-B), abs(A-C), abs(B-C)});
    if( ans > sa ) ans = sa;
  }
  
  //横で分割
  for( int i = 1; i <= H; i++ ){
    int A = W*i;
    int B, C;
    if( W%2 == 0 ){
      B = (H-i)*(W/2);
      C = (H-i)*(W/2);
    }else{
      B = (H-i)*(W/2);
      C = (H-i)*(W/2+1);
    }
    int sa = max({abs(A-B), abs(A-C), abs(B-C)});
    if( ans > sa ) ans = sa;
  }
  
  cout << ans << endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100009
#define MOD 1000000007ll
#define LL long long

int main(){
	LL n,m;
	cin>>n>>m;
	LL x[MAXN],y[MAXN];
	for(LL i=0;i<n;i++){
		cin>>x[i];
	}
	for(LL i=0;i<m;i++){
		cin>>y[i];
	}
	sort(x,x+n,greater<LL>());
	sort(y,y+m,greater<LL>());
	LL mul=(n-1);
	LL sumx=0;
	for(LL i=0;i<n;i++){
		sumx+=(mul*x[i])%MOD;
		mul-=2;
		sumx%=MOD;
		if(sumx<0){
			sumx+=MOD;
		}
	}
	mul=(m-1);
	LL sumy=0;
	for(LL i=0;i<m;i++){
		sumy+=(mul*y[i])%MOD;
		mul-=2;
		sumy%=MOD;
		if(sumy<0){
			sumy+=MOD;
		}
	}
	LL res = sumx*sumy%MOD;
	cout<<res;
	return 0;
}

Measured memory_bytes: 1792
N = int(input())
tells = []
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        x,y = map(int,input().split())
        tells.append([i+1,x,y])

truth = 0
for i in range(2**N):
    x = True
    sus = list(str(bin(i))[2:].zfill(N))
    for j in range(len(tells)):
        if sus[tells[j][0]-1] == "1":
            if sus[tells[j][1]-1] != str(tells[j][2]):
                x = False
                break
    if x == True:
        truth = max(truth,sus.count("1"))

print(truth)

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

int main(){
  string s;
  cin>>s;
  string hitachi = "";
  rep(i,5){
    hitachi+="hi";
    if (hitachi == s){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define pragi(a,b) for(ll i = a;i<b;i++)
#define pragj(a,b) for(ll j = a;j<b;j++)
#define pragk(a,b) for(ll k = a;k>=b;k--)
#define all(v) (v.begin(),v.end())
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define MP make_pair
#define MT make_tuple
#define F first
#define S second
#define KAKA ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int mod = 1e9 + 7;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef long double ld;
typedef pair<int, int> pii;
//typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef pair<ll, ll> pll;

void Compute(ll h,ll w,ll m)
{
    KAKA
    vector<pll> vec(m);
    map<pll,bool> is_bomb;
    map<ll,ll> mpx;
    map<ll,ll> mpy;
    pragi(0,m)
    {
        cin>>vec[i].F>>vec[i].S;
        mpx[vec[i].F]++;
        mpy[vec[i].S]++;
    }
    ll mx = 0,my = 0;
    for(auto p : mpx)
    {
        if(p.S > mx)
        {
            mx = p.S;
        }
    }
    for(auto p : mpy)
    {
        if(p.S > my)
        {
            my = p.S;
        }
    }
    vector<ll> vec1;
    vector<ll> vec2;
    for(auto p : mpx)
    {
       if(p.S == mx) vec1.eb(p.F);
    }
    for(auto p : mpy)
    {
        if(p.S == my) vec2.eb(p.F);
    }
    //for(auto ele : vec1)cout<<ele<<" ";
    //cout<<"\n";
    //for(auto ele : vec2) cout<<ele<<" ";
    //cout<<"\n";
    map<ll,bool> mp1;
    map<ll,bool> mp2;
    vector<vector<ll> > Adj(1e6);
    for(auto x : vec1)
    {
        mp1[x] = true;
    }
    for(auto y : vec2)
    {
        mp2[y] = true;
    }
    for(auto bombs : vec)
    {
        if(mp1[bombs.F])
        {
            if(mp2[bombs.S])
            Adj[bombs.F].eb(bombs.S);
        }
    }
    bool flag = false;
    
    for(auto x : vec1)
    {
        //cout<<mp2.size()<<" ";
       // cout<<Adj[x].size()<<"\n";
              if(Adj[x].size() < vec2.size())
      {
          flag = true;
          break;
      }
    }
    if(flag)
    {
        cout<<mx + my<<"\n";
    }
    else
    {
        cout<<(mx + my - 1)<<"\n";
    }
    
}
int main()
{
    KAKA
    ll h,w,m;
    cin>>h>>w>>m;
    Compute(h,w,m);
}

Measured memory_bytes: 120212
import numpy as np
import math

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

np_nums = np.array([list(map(int, input().split())) for _ in range(N)])


def calc_distance(y, z):
    # 二乗の総和の二乗根を取る
    return float(
        math.sqrt(
            sum([(np_nums[y][d] - np_nums[z][d]) ** 2 for d in range(D)])
        )
    )


ans = 0
for Y in range(N - 1):
    for Z in range(Y + 1, N):
        if calc_distance(Y, Z).is_integer():
            ans += 1

print(ans)

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

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

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();}

int main(){
    std::ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    int tmp = 0;
    int ans = 1 << 30;
    for(size_t i=0;i<s.length();++i)
    {
        if(s[i] == 'E')
        {
            tmp++;
        }
    }
    //dump(tmp);

    ans = tmp;
    for(size_t i=0;i<s.length();++i)
    {
        if(s[i] == 'E')
        {
            ans = min(ans, --tmp);
        }
        else
        {
            tmp++;
        }
    }
    cout << ans << endl;
}

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

int main()
{
    int a[5];
    int K;

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

    int remainder = 10;

    for (int i = 0; i < 5; i++)
    {
        int tmp = 0;
        tmp = a[i] % 10;
        if(tmp < remainder)
            if(tmp != 0)
                remainder = tmp;
    }

    int ans = 0;
    for (int i = 0; i < 5; i++)
    {
        if(a[i] % 10 != 0)
            a[i] = (a[i] / 10 + 1) * 10;
        ans = ans + a[i];
    }
    cout << ans - 10 + remainder << endl;
}

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

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999;
	public class Balloon
	{
		public long Height{get;set;}
		public long Speed{get;set;}
	}
	
	public static void Main(string[] args)
	{
		var s = Input();
		var a = Input().ToInt();
		var u = Console.ReadLine();
		if(s[0] == u)
		{
			Console.WriteLine("{0} {1}", a[0]-1, a[1]);
		}
		else if(s[1] == u)
		{
			Console.WriteLine("{0} {1}", a[0], a[1]-1);
		}
		else
		{
			Console.WriteLine("{0} {1}", a[0], a[1]);
		}
	}

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}


Measured memory_bytes: 13140
import numpy as np

H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1

# x軸正方向の集計
def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x

# y軸
def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)
# x軸
answer += F()
# 逆順
map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]

# y軸
answer += G()
# 逆順
map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(int a = 0;a < n;a++)
#define repi(a,b,n) for(int a = b;a < n;a++)

const ull mod = 1000000007;

int main(void)
{
	string L;
	cin >> L;
	ll s = L.size();
	vector<vector<ll>> dp(s + 1, vector<ll>(2,0));
	//00
	dp[0][0] = 1;
	//10,01
	dp[0][1] = 2;
	for (int i = 1; i < s; i++) {
		bool one = L[i] == '1';
		if (one) {
			//10,01
			(dp[i][0] += dp[i - 1][0] * 2) %= mod;
			(dp[i][1] += dp[i - 1][1] * 2) %= mod;
			//00
			(dp[i][0] += dp[i - 1][0]) %= mod;
			(dp[i][0] += dp[i - 1][1]) %= mod;

		}
		else {
			//00
			(dp[i][0] += dp[i - 1][0]) %= mod;
			(dp[i][1] += dp[i - 1][1]) %= mod;
			//10,01
			(dp[i][0] += dp[i - 1][0]*2) %= mod;
		}
	}
	auto sum = dp[s - 1][0] + dp[s - 1][1];
	sum %= mod;
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 5760
#include <numeric>
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
#include <sstream>
using namespace std;
long long inf=100000000000007;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
typedef pair<int,int>  P;
string alph("abcdefghijklmnopqrstuvwxyz");
struct edge{int to,cost;};
vector<edge> G[22];
vector<int> O[10];
P sg[10];
int d[1005][1005]={};
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
pair<int,double> s[1005];
int c=0;
int n,k;
int fi[1005][1005];
int ans[1005][1005]={};
void solve(int a,int b){
    for(int i=0; i<4;i++){
        if(fi[a+dx[i]][b+dy[i]]>fi[a][b]){
            if(!d[a+dx[i]][b+dy[i]]){
                ans[a+dx[i]][b+dy[i]]++;
                d[a+dx[i]][b+dy[i]]++;
            }
            solve(a+dx[i],b+dy[i]);
        }
    }
}

signed main(){
    int n,m;cin>>n>>m;
    int time=n*100+m*1800;
    rep(i,m)time*=2;
    cout<<time<<endl;
    return 0;
}

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

int main() {
	int N, A[100001];
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	A[N] = 0;
	ll ans = 0;
	ll sum = 0;
	for(int i = 0; i <= N; i++){
		if(A[i] == 0){
			ans += sum / 2;
			sum = 0;
		}else{
			sum += A[i];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a;
  string s;
  cin >> a >> s;
  cout << (a >= 3200 ? s : "red") << '\n';
  return 0;
}


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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a==b&&b==c){
    cout << 1 << endl;
  }else if(a!=b&&b!=c&&c!=a){
    cout << 3 << endl;
  }else{
    cout << 2 << endl;
  }
}

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

void dfs(int curr, vector<vector<int> > const &adj, map<int,bool> &visited, vector<int> &dp)
{
    if(visited[curr])
    return;
    visited[curr]=true;
    for(auto &i: adj[curr])
    {
        if(!visited[i])
        dfs(i, adj, visited, dp);
        dp[curr]=max(dp[curr],1+dp[i]);
    }
}

int solve(vector<vector<int> > const &adj)
{
    vector<int> dp(adj.size()+4,0);
    map<int,bool> visited;
    for(int i=0 ; i<adj.size() ; ++i)
    {
        if(!visited[i])
        dfs(i, adj, visited, dp);
    }
    int ans=0;
    for(int i=0 ; i<dp.size() ; ++i)
    ans=max(dp[i],ans);
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<vector<int> > adj(n,vector<int>());
    int x,y;
    for(int i=0 ; i<m ; ++i)
    {
        cin>>x>>y;
        --x;
        --y;
        adj[x].push_back(y);
    }
    cout<<solve(adj)<<endl;
    return 0;
}

Measured memory_bytes: 15616
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int A[100010];
int K;
bool isOk(int num) {
    //cout << "***" << num << "***" << endl;
    rep(i, K) {
        num -= (num % A[i]);
        //cout << i << " " << num << endl;
    }
    return num >= 2;
}

bool isOk2(int num) {
    //cout << "***" << num << "***" << endl;
    rep(i, K) {
        num -= (num % A[i]);
        //cout << i << " " << num << endl;
    }
    return num > 2;
}

int isok_num(int num) {
    rep(i, K) {
        num -= (num % A[i]);
        //cout << i << " " << num << endl;
    }
    return num;
}

int binary_search1() {
    int ok = INF2;
    int ng = 1;
    while(abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOk(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
int binary_search2() {
    int ok = INF2;
    int ng = 1;
    while(abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOk2(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> K;
    
    rep(i, K) cin >> A[i];
    int low = binary_search1();
    int high = binary_search2() - 1;
    if (isok_num(low) != 2) {
        cout << -1 << endl;
        return 0;
    }
    //cout << isok_num(low) << " " << isok_num(high) << endl;
    cout << low << " " << high << endl;

    return 0;
}


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

int main() {
	int n, t;
	cin >> n >> t;
	vector<P> p(n);
	rep(i, n) cin >> p[i].first >> p[i].second;
	sort(p.begin(), p.end());
	vector<int> dp(t + 1, 0);
	rep(i, n) {
		for (int j = t - 1; j >= 0; --j) {
			dp[min(t,j + p[i].first)] = max(dp[min(t,j + p[i].first)], dp[j] + p[i].second);
		}
	}
	cout << dp[t] << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pil;
typedef complex<double> xy_t;

const lint mod = 1e9 + 7;

int main(){
    string s;
    lint K;
    cin >> s >> K;
    int n = s.size();

    string t = s;
    lint tans = 0;
    rep(i, t.size()-1){
        if(t[i] == t[i+1]){
            ++tans;
            t[i+1] = '#';
        }
    }
    tans *= K;
    if(t[0] == t[s.size()-1]) tans += K-1;

    K *= n;

    int cur = 0;
    lint times = 0;
    int len = 0;
    lint num = 0;
    pii used[n];
    rep(i, n) used[i] = pil(-1, -1);
    clock_t start = clock();
    while(true){
        if(clock() - start > 1900){
            printf("%lld\n", tans);
            return 0;
        }

        if(cur == K){
            printf("%lld\n", times);
            return 0;
        }
        if(s[cur%n] == s[(cur+1)%n]){
            if(used[cur%n].fi >= 0){
                len = cur - used[cur%n].fi;
                num = times - used[cur%n].se;
                break;
            }
            used[cur%n] = pii(cur, times);
            ++times;
            cur += 2;
        }
        else ++cur;
    }

    lint ans = used[cur%n].se;
    ans += 1LL * num * ((K-used[cur%n].fi) / len);
    K = 1LL * (K-used[cur%n].fi) % len;
    while(K > 1){
        if(s[cur%n] == s[(cur+1)%n]){
            ++ans;
            cur += 2;
            K -= 2;
        }
        else{
            ++cur;
            --K;
        }
    }
    printf("%lld\n", ans);
}

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

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve(){
    llint n;
    vector<llint>a(5);
    cin >> n;
    llint mn=inf;
    for(int i=0;i<5;i++){
        cin >> a[i];
        mn=min(a[i],mn);
    }
    llint ans=0;
    if(n%mn==0){
        ans+=5+n/mn;
    }
    else ans+=6+n/mn;

    cout << ans-1 << endl;


}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 256
def main():
    n,h = map(int,input().split())
    ab=[]
    a_max=0
    for _ in range(n):
        a,b = map(int,input().split())
        ab.append([a,b])
        if a_max<a:
            a_max=a

    ab.sort(reverse=True,key=lambda x:x[1])
    for i in range(n-1,-1,-1):
        if ab[i][0]==a_max:
            index=i+1
            break
    ans=0
    cnt=0
    index2=0
    while index2!=n and ab[index2][1]>a_max:
        cnt+=ab[index2][1]
        ans+=1
        if cnt>=h:
            print(ans)
            return
        index2+=1
    if (h-cnt)%ab[index-1][0]==0:
        ans+=(h-cnt)//ab[index-1][0]
    else:
        ans+=(h-cnt)//ab[index-1][0]+1
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 64088
#include<iostream>
#include<cstdlib>
#include<climits>
#include<algorithm>
using namespace std;
int main(void){
  int n;
  cin>>n;
  int h[n+1],dp[n+1];
  for(int i=1;i<=n;i++)cin>>h[i];
  for(int i=3;i<=n;i++)dp[i]=INT_MAX;
  dp[0]=dp[1]=0;dp[2]=abs(h[1]-h[2]);
  for(int i=3;i<=n;i++)dp[i]=min({dp[i],dp[i-1]+abs(h[i-1]-h[i]),dp[i-2]+abs(h[i-2]-h[i])});
  cout<<endl<<dp[n];
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

// the number of total comparisons
int comparisons = 0;

// merge merges the A from left to mid and mid to right assuming that those sublists are already sorted.
void merge(int *A, int left, int mid, int right)
{
  int i;
  // allocate arrays to hold the two sorted sections to merge
  int *leftArray = (int *) malloc((mid-left+1)*sizeof(int));
  int *rightArray = (int *) malloc((right-mid+1)*sizeof(int));
  // assign the proper values to the subarrays
  for ( i = 0; i < mid-left; i++ )
    leftArray[i] = A[left+i];
  for ( i = 0; i < right-mid; i++ )
    rightArray[i] = A[mid+i];
  leftArray[mid-left] = INT_MAX;
  rightArray[right-mid] = INT_MAX;
  // merge the subarrays
  int j = 0, k = 0;
  for ( i = left; i < right; i++ )
    {
      comparisons++;
      if ( leftArray[j] <= rightArray[k] )
	A[i] = leftArray[j++];
      else
	A[i] = rightArray[k++];
    }
  return;
}

// mergeSort sorts the array A from left to right in ascending order.
void mergeSort(int *A, int left, int right)
{
  if ( left+1 < right )
    {
      int mid = (left + right)/2;
      mergeSort(A, left, mid);
      mergeSort(A, mid, right);
      merge(A, left, mid, right);
    }
  return;
}

int main()
{
  int length, *A, i;
  scanf(" %d", &length);
  A = (int *) malloc(length*sizeof(int));
  for ( i = 0; i < length; i++ )
    scanf(" %d", A+i);
  mergeSort(A, 0, length);
  for ( i = 0; i < length; i++ )
    printf("%d%c", A[i], i == length-1 ? '\n' : ' ');
  printf("%d\n", comparisons);
  return 0;
}



Measured memory_bytes: 64468
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt()

  val happy = Stream.range(0, n)
    .map(_ => (sc.nextLong(), sc.nextLong(), sc.nextLong()))
    .foldLeft(0L, 0L, 0L) {
      case ((am, bm, cm), (ai, bi, ci)) =>
        (
          math.max(bm + ai, cm + ai),
          math.max(cm + bi, am + bi),
          math.max(am + ci, bm + ci)
        )
    }

  println(Seq(happy._1, happy._2, happy._3).max)

}


Measured memory_bytes: 115400
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;

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;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    ll D;ll G;
    cin>>D>>G;
    vpii P(D);
    rep(i,0,D)cin>>P[i].first>>P[i].second;
    ll ans=INF;
    rep(i,0,1<<D){
        ll cnt=0,res=0;
        rep(j,0,D){
            if((i>>j)&1){
                res+=P[j].first*(j+1)*100+P[j].second;
                cnt+=P[j].first;
            }
        }
        if(res<G){
            irep(j,0,D){
                if(((i>>j)&1)==0){
                    if((res+(P[j].first-1)*(j+1)*100)<G)
                        break;
                    else{
                        rep(num,1,P[j].first){
                            res+=(j+1)*100,cnt++;
                            if(res>=G){
                                chmin(ans,cnt);
                                break;
                            }
                        }
                        break;
                    }
                }
            }
        }
        else
            chmin(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}




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

const int divisor = 1000000007;

int main(){
	vector<int> ansvec;

	// 100000!までの数をdivisorで割った余りを格納しておく
	long long* factmodary = new long long[100001];
	long long fact = 1;
	for (int i = 1; i <= 100000; i++){
		fact *= i;
		fact %= divisor;
		factmodary[i] = fact;
	}

	int* word = new int[100000] {0};

	for (;;){
		int N, R;
		cin >> N;
		if (N == 0) break;
		cin >> R;
		
		//まず0番目の単語を入れておく
		for (int i = 0; i < N; i++) word[i] = i + 1;

		for (int i = 0; i < R; i++){
			int s, t;
			cin >> s >> t;
			/* swap */
			int tmp = word[s - 1]; word[s - 1] = word[t - 1]; word[t - 1] = tmp;
		}

		//word[i]をkey, word[i]より小さい数がそれ以前にいくつ使われていたかをvalueとして格納するmap
		map<int, int> bubblehist;
		bubblehist[word[0]] = 0;

		long long ans = factmodary[N-1] * (word[0] - 1);

		for (int i = 1; i < N; i++){
			int facttime = word[i] - 1;
			int bubblenum;
			map<int, int>::iterator it = bubblehist.lower_bound(word[i]);

			if (it != bubblehist.end()){
				bubblenum = it->second;
				it--;
			}
			else {
				it--;
				bubblenum = it->second + 1;
			}
			pair<int, int> p;
			p.first = word[i];
			p.second = bubblenum;
			map<int, int>::iterator it2 = bubblehist.insert(it, p);
			//word[i]より大きい数はすべてvalueが1増える
			for (++it2; it2 != bubblehist.end(); it2++) ++(it2->second);

			facttime -= bubblenum;
			ans += factmodary[N - (i + 1)] * facttime;
			ans %= divisor;
		}
		ansvec.push_back((int)ans);
	}

	for (vector<int>::iterator it = ansvec.begin(); it != ansvec.end(); it++) cout << *it << "\n";

	delete[] word;
	delete[] factmodary;
	return 0;
}

Measured memory_bytes: 6816
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top,S[2000];

void push(int x){
	S[++top]=x;
}
int pop(){
	top--;
	return S[top+1];
}

int main(){
	int a,b;
	top=0;
	char s[100];
	while(scanf("%s",s)!=EOF){
		if(s[0]=='+'){
			a=pop();
			b=pop();
			push(a+b);
			}
		else if(s[0]=='-'){
			b=pop();
			a=pop();
			push(a-b);
		}
		else if(s[0]=='*'){
			a=pop();
			b=pop();
			push(a*b);
		}
		else{
			push(atoi(s));
		}
	}
	
	printf("%d\n",pop());
	return 0;
}


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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const ll MOD=1e9+7;

int main(){
    int N, M; cin >> N >> M;
    string S; cin >> S;
    int cur=N;
    vi res;
    while(cur > 0){
        bool ok=false;
        for(int i=M; i>=1; i--){
            if(cur-i < 0){
                i=cur+1;
                continue;
            }
            int next=cur-i;
            if(S[next] != '1'){
                ok=true;
                res.push_back(i);
                cur=next;
                break;
            }
        }
        if(!ok){
            cout << -1 << endl;
            return 0;
        }
    }
    reverse(all(res));
    for(int i=0; i<(int)res.size(); i++){
        if(i != 0) cout << " ";
        cout << res[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 4056
#define debug 0
#define test 0
#define CPLUS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#if CPLUS
#include <iostream>
#include <stack>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>
#include <queue>
#include <map>
#include <unordered_map>
#include <functional>
#include <iomanip>
using namespace std;
#endif



int main(void)
{
#if debug
	freopen("in.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int tmp;
		scanf("%d", &tmp);
		ans += (tmp - 1);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
N = int(input())
T = [[0,0,0]]+[ [int(x) for x in input().split()] for _ in range(N)]

flag = 'Yes'
i = 0
while flag=='Yes' and i<len(T)-1:
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    i += 1        
print(flag)

Measured memory_bytes: 26240