akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>
using namespace std;

int H,W;
char S[25][25];

//
// スタート位置をゴール位置を渡した時の
// 最短距離
//
int D[25][25];
int vx[4] = {0,-1,0,1};
int vy[4] = {1,0,-1,0};

int bfs(int sx,int sy,int gx,int gy){
    if(S[sx][sy] != '.' || S[gx][gy] != '.' || (sx == gx && sy == gy) ){
        return -2;
    }

    // 初期化
    for(int y = 1;y < H + 1;y++){
        for(int x = 1;x < W + 1;x++){
            D[x][y] = -1;
        }
    }

    int way = -1;
    pair<int,int> p;
    queue < pair<int,int> > Q;
    
    Q.push(make_pair(sx,sy));
    D[sx][sy] = 0;

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

        for(int i = 0;i < 4;i++){
            int nx = p.first + vx[i];
            int ny = p.second + vy[i];

            if(1 <= nx && nx <= W && 1 <= ny && ny <=H && S[nx][ny] == '.' && D[nx][ny] == -1){
                Q.push(make_pair(nx,ny));
                D[nx][ny] = D[p.first][p.second] + 1;

                // ゴール判定
                if(nx == gx && ny == gy){
                    way = D[nx][ny];
                    break;
                } 
            }
        }

    }

    return way;
}

int main(){
    cin >> H >> W;
    for(int y = 1;y < H + 1;y++){
        for(int x = 1;x < W + 1;x++){
             cin >> S[x][y];
        }
    }

    int ans = 0;
    int p = 0;

    for(int sx = 1;sx < W+1;sx++){
        for(int sy = 1;sy < H+1;sy++){
            for(int gx = 1;gx < W+1;gx++){
                for(int gy = 1;gy < H+1;gy++){

                    p = bfs(sx,sy,gx,gy);
                    if( ans <= p){
                        ans = p;
                    }

                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>
// C - : (Colon)

using namespace std;

#define PI 3.141592653589793

int main() {
    int A,B,H,M,tot1;
    double ang1,ang2,dif,C;

    scanf("%d%d%d%d",&A,&B,&H,&M);

    tot1 = (H % 12) * 60 + M;
    ang1 = PI / 360 * tot1;
    ang2 = PI / 30 * M;

    dif = abs(ang1 - ang2);
    dif = max(dif,2 * PI - dif);

    C = sqrt(A * A + B * B - 2 * A * B * cos(dif));
    printf("%.10f\n",C);

    return 0;
}


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

using namespace std;

int main()
{
    int n,x,sum=0,countt=0;
    cin>>n>>x;
    int l[n];
   //arr[0]=0;
    for(int i=0;i<n;i++)
    {
        cin>>l[i];
    }
    for(int i=0;i<n;i++)
    {
        sum=sum+l[i];
        if(sum<=x)
        {
            countt++;
        }
    }
    cout<<countt+1<<endl;


    return 0;
}


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

// ??\???:?§??????????S???
// ??????:h:m:s => h:??????, m:???, s:?§? ?????????

int main(){
	int S, h, m, s;
	cin >> S;
	h = S/3600;
	m = S%3600/60;
	s = S%3600%60;

	cout << h << ":" << m << ":" << s << endl;
}

Measured memory_bytes: 1168
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

use std::collections::BTreeMap;

fn f(mut n: u32, bm: &mut BTreeMap<u32, u32>) {
    let mid = (n as f64).sqrt() as u32;
    while n > 1 {
        let mut i = 2;
        while i < mid + 3 {
            if n % i == 0 {
                let v = *bm.get(&i).unwrap_or(&0);
                bm.insert(i, v + 1);
                n /= i;
                break;
            }
            i += 1;
        }
        if i == mid + 3 {
            let v = *bm.get(&n).unwrap_or(&0);
            bm.insert(n, v + 1);
            n = 1;
        }
    }
}

fn main() {
    let n: u32 = read();
    let mut bm: BTreeMap<u32, u32> = BTreeMap::new();
    f(n, &mut bm);
    let mut ans = 1;
    for (p, k) in bm {
        ans *= p.pow(k - 1) * (p - 1);
    }
    println!("{}", ans);
}



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

int used[410][410];
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};

ll bfs(int sy, int sx, const vector<string>& s, int h, int w) {
	queue<pair<int, int>> que;
	que.push(make_pair(sy, sx));
	used[sy][sx] = true;

	int black = 0, white = 0;

	while (not que.empty()) {
		int y = que.front().first, x = que.front().second;
		que.pop();
		if (s[y][x] == '#') black++;
		else white++;

		rep(i, 4) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (not (0 <= ny and ny < h and 0 <= nx and nx < w))
				continue;
			if (used[ny][nx])
				continue;
			if (s[y][x] != s[ny][nx]) {
				used[ny][nx] = true;
				que.push(make_pair(ny, nx));
			}
		}
	}
	return (ll)black * white;
}

int main(int argc, char const *argv[])
{
	int h, w; cin >> h >> w;
	vector<string> s(h); rep(i, h) cin >> s[i];
	ll ans = 0;
	rep(i, h)rep(j, w) {
		if (not used[i][j]) 
			ans += bfs(i, j, s, h, w);
	}
	cout << ans << endl;
	return 0;
}


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

long long x,k,d;

int main(void){
    cin >> x >> k >> d;
    x=llabs(x);
    long long tmp=min(k,x/d);
    k-=tmp;
    x-=tmp*d;
    if(k%2==0)
        cout << x << endl;
    else 
        cout << d-x << endl;
    
    return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)


int main() {
	cin.sync_with_stdio(false);
	ll N, K;
	cin >> N >> K;
	vector<ll>n;
	map<ll, ll>mp;
	int a, b;
	rep(i, N) {
		cin >> a >> b;
		mp[a] += b;
		n.push_back(a);
	}
	sort(n.begin(), n.end());
	n.erase(unique(n.begin(), n.end()), n.end());
	ll count = 0;
	rep(i, n.size()) {
		count += mp[n[i]];
		if (count >= K) {
			cout << n[i] << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 4980
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <bitset>
using namespace std;
typedef long long int lli;
int main(void)
{
    int N;
    string s;
    cin >> N;
    cout << N + N * N + N * N * N << endl;
    return 0;
}


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

int sumCount(long long n){
  int res = 0;
  while(n > 0){
    n /= 10;
    res++;
  }
  return res;
}

int findCount(long long a){
  long long b, c, d, e;
  long long f = 9999999999;
  for(long long i = 1; i <= sqrt(a); i++){
    if(a % i == 0){
      b = a / i;
      c = sumCount(i);
      d = sumCount(b);
      e = max(c, d);
    }
    f = min(e, f);
  }
  return f;
}
  

int main(){
  long long N, ans;
  cin >> N;
  ans = findCount(N);
  cout << ans << endl;
}

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

int main () {

    int N;

    scanf("%d", &N);

    int A[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &A[i][j]);
        }
    }

    ll ans = 0;

    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            ans += A[i][j];
            
            for (int k = 0; k < N; k++) {
                if (A[i][j] > A[i][k] + A[k][j]) {
                    printf("-1\n");
                    return 0;
                }
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (k != i && k != j && A[i][j] == A[i][k] + A[k][j]) {
                    ans -= A[i][j];
                    break;
                }
            }
        }
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 640
import sys
input = sys.stdin.readline

N=int(input())
S=list(input().strip())
mod=10**9+7

for i in range(2*N):
    if S[i]=="B":
        S[i]=0
    else:
        S[i]=1

    if i%2==1:
        S[i]=(S[i]+1)%2


ones=0
ANS=1

if S.count(1)!=S.count(0):
    print(0)
    sys.exit()

for i in range(2*N-1,-1,-1):
    if S[i]==1:
        ones+=1

    else:
        ANS=ANS*ones%mod
        ones-=1


for i in range(1,N+1):
    ANS=ANS*i%mod


print(ANS)
        



Measured memory_bytes: 65264
import sys
sys.setrecursionlimit(10**5)

n,m,k=map(int,input().split())
fr=[0 for _ in range(n)]
frl=[[] for i in range(n)]
frlist=[]
for i in range(m):
    a,b=map(int,input().split())
    frl[a-1].append(b)
    frl[b-1].append(a)
    frlist.append([a,b])

treelist=[]
hitobito=set()

def saiki(c,tmpi):
    global hitobito
    global tmpset
    global trbl
    
    if frl[c-1] == []:
        hitobito.add(c)
        tmpset.add(c)
        trbl[c-1]=tmpi
    
    for tsugi in frl[c-1]:
        if not tsugi in hitobito:
            hitobito.add(tsugi)
            tmpset.add(tsugi)
            trbl[tsugi-1]=tmpi
            saiki(tsugi,tmpi)

index=0
trbl=[None for _ in range(n)]
for i in range(n):
    tmpset=set()
    saiki(i+1,index)
    if not tmpset == set():
        treelist.append(tmpset)
        index+=1

bl=[0 for _ in range(n)]
bll=[[] for i in range(n)]
bllist=[]
for i in range(k):
    a,b=map(int,input().split())
    bll[a-1].append(b)
    bll[b-1].append(a)
    bllist.append([a,b])

for fre in frlist:
    if trbl[fre[0]-1] == trbl[fre[1]-1]:
        fr[fre[0]-1]=fr[fre[0]-1]+1
        fr[fre[1]-1]=fr[fre[1]-1]+1

for blo in bllist:
    if trbl[blo[0]-1] == trbl[blo[1]-1]:
        bl[blo[0]-1]=bl[blo[0]-1]+1
        bl[blo[1]-1]=bl[blo[1]-1]+1

output=[]
for i in range(n):
    tmpsum=fr[i]+bl[i]
    output.extend([str(len(treelist[trbl[i]])-tmpsum-1)," "])

print("".join(output))    




Measured memory_bytes: 98564
#include <iostream> 



  



using namespace std; 



  



int main() 



{ 



   int x, y; 



   cin >> x >> y; 



   if (x < y) { 



       cout << "a < b" << endl; 



   } 



   else if (x > y) { 



      cout << "a > b" << endl;  



   } 



   else { 



      cout << "a == b" << endl;  



   } 



        



   return 0; 



} 


Measured memory_bytes: 3028
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> vec={1,10,100};
for (int i = 0; i < 3; i++) {
  cin >> vec.at(i);
}
 if( N%vec.at(1)==7 || (N/vec.at(1))%10==7 || N/vec.at(2)==7){
 cout<<"Yes"<<endl;}
   else
     cout<<"No"<<endl;
  return 0; 
}


Measured memory_bytes: 3592
// ConsoleApplication1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;


int main()
{
	int N;
	cin >> N;
	vector <int> a(N);
	int sum = 0;
		for (int i = 0; i < N; i++) {
			cin >> a.at(i);
		}
		for (int i = 0; i < N; i++) {
			while (a.at(i) % 2 == 0) {
				sum++;
				a.at(i) /= 2;
			}

		}
		cout << sum << endl;

}
// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこの,プロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します

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

using namespace std;
using VI = vector<int>;
using VPI = vector<pair<int, int>>;

#define FOR(a,n) for(int i=a;i<n;i++)
#define rFOR(a,n) for(int i=n-1;i>=a;i--)
#define IN(n,a) for(int i=0;i<n;i++) cin>>a[i]
#define pIN(n,t) for(int i=0;i<n;i++){int a,b; cin>>a>>b; t.emplace_back(a,b);}
#define SORT(a) sort(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()

int main()
{
	int n;
	cin >> n;
	VPI t;
	FOR(0, n)
	{
		int a;
		cin >> a;
		t.emplace_back(a, i + 1);
	}

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

	FOR(0, n) cout << t[i].second << " ";
}

Measured memory_bytes: 1780
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

signed main() {
    int n, p;
    cin >> n >> p;
    int ans = 1;
    map<int, int> m;
    for (int i = 2; i * i <= p; ++i) {
        if (p % i == 0) {
            int cnt = 0;
            while (p % i == 0) {
                cnt++;
                p /= i;
            }
            m[i] += cnt;
        }
    }
    if (p > 1)
        m[p]++;

    for (auto && x : m) {
        if (x.second >= n)
            ans *= pow(x.first, (x.second / n));
    }
    cout << ans << "\n";
}

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

int main(){
    int n,m,e;
    cin >> n >> m;
    int a[n][m];
    int b[m];
    int c[n];
    e = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    
    for(int k=0;k<m;k++){
        cin >> b[k];
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            e = e + a[i][j]*b[j];
        }
        c[i] = e;
        e = 0;
    }
    
    for(int i=0;i<n;i++){
        cout << c[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3128
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
using namespace std;
const int MOD = 1e9 +7;


int main(){
    string s;
    cin >>s;
    long long ans=0;
    for(int bit=0;bit<(1<<s.size()-1);bit++){
        long long num = s[0] -'0';
        for(int i =0;i<s.size()-1;i++){
            if( bit & (1<<i)){
                ans +=num;
                num =0;
            }
            num =num *10 +s[i+1] -'0'; 
        }
        ans +=num;
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m,k=f()
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]
l=[0]*n
for _ in range(m):
  a,b=f()
  unite(a-1,b-1)
  l[a-1]-=1
  l[b-1]-=1
for _ in range(k):
  c,d=f()
  if same(c-1,d-1):
    l[c-1]-=1
    l[d-1]-=1
for i in range(n):
  l[i]+=size(i)-1
print(*l)

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(2e5 + 5);

int n, k;
int p[MAX_N];

int q[MAX_N];

int counter_mono_part() {
  p[n] = -1;

  int ret = 0;

  int cnt = 1;

  for (int i = 1; i <= n; ++i) {
    if (p[i - 1] < p[i])
      cnt += 1;
    else {
      if (cnt >= k) ret += 1;
      cnt = 1;
    }
  }

  return ret;
}

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &k);

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

  set<int> st;

  for (int i = 0; i < k; ++i) {
    st.insert(p[i]);
  }

  int cnt = 1;

  int mono_part = counter_mono_part();

  for (int i = 1; (i + k - 1) < n; ++i) {
    int last_begin_ind = i - 1;
    int last_begin = p[last_begin_ind];

    int cur_end = p[i + k - 1];

    int last_max = *(--st.end());

    st.erase(st.find(last_begin));

    int cur_min = *(st.begin());

    if (!(last_begin < cur_min && last_max < cur_end)) {
      cnt += 1;
    }

    st.insert(cur_end);
  }

  int ans = cnt;

  if (mono_part >= 1) {
    ans -= mono_part;
    ans += 1;
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 10368
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,k,a,b;
	cin>>n>>k;
	a=n%k;
	b=abs(a-k);
	if(a>b)
	{
		cout<<b<<endl;
	}
	else
	{
		cout<<a<<endl;
	}
}

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

const int inf=1000000007;
const int MOD=1000000007;
const long long INF=1000000000000000007;


int n, A, B, C;
int l[10];

int dfs(int cur, int a, int b, int c, int rest) {
  if (cur == n) {
    if (min(a, min(b, c)) > 0) {
      return abs(A - a) + abs(B - b) + abs(C - c) + (n - rest - 3) * 10;
    } else {
      return inf;
    }
  }

  int ret1 = dfs(cur + 1, a, b, c, rest);
  int ret2 = dfs(cur + 1, a + l[cur], b, c, rest - 1);
  int ret3 = dfs(cur + 1, a, b + l[cur], c, rest - 1);
  int ret4 = dfs(cur + 1, a, b, c + l[cur], rest - 1);
  return min(ret1, min(ret2, min(ret3, ret4)));
}


int main() {
  cin >> n >> A >> B >> C;
  rep(i, n) {
    cin >> l[i];
  }

  cout << dfs(0, 0, 0, 0, n) << endl;
}


Measured memory_bytes: 256
n = int(input())
rooms = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
x = 0

for a in range(n):
    b, f, r, v = map(int, input().split())
    rooms[b-1][f-1][r-1] += v

for i in rooms:
    for j in i:
        for k in j:
            print(' %d'%k, end='')
        print()
    x += 1
    if x < 4:
        print('#' * 20)


Measured memory_bytes: 5628
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
 
long long int calcGcd(long long int a, long long int b){
	if(b == 0){
		return a;
	}
	
	return(calcGcd(b, a%b));
}
 
int main()
{
	int K;
	long long int res = 0;
 
	cin >> K;
 
	for(int i=1; i<=K; i++){
		res += i;
	}
 
	if(K == 1){
		cout << res;
		return 0;
	}
 
	for(int i=1; i<=K; i++){
		for(int j=i+1; j<=K; j++){
			res += (calcGcd(i, j) * 6);
		}
	}
 
	if(K == 2){
		cout << res;
		return 0;
	}
 
	for(int i=1; i<=K; i++){
		for(int j=i+1; j<=K; j++){
			for(int k=j+1; k<=K; k++){
				res += (calcGcd(calcGcd(i, j), k) * 6);
			}
		}
	}
	
	cout << res;
 
	cin >> K;
 
	return 0;
}

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

vector<vector<int>> dist;
vector<vector<bool>> vacant;
int N;
ll ans = 0;
vector<int> dx = {0,0,1,-1}, dy = {1,-1,0,0};

void dfs(int x, int y) {
    for (int i = 0; i <= 3; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx <= -1 || nx >= N || ny <= -1 || ny >= N) continue;
        int ndist = dist[x][y];
        if (!vacant[x][y]) ndist++;
        if (ndist < dist[nx][ny]) {
            dist[nx][ny] = ndist;
            dfs(nx, ny);
        }
    }
    return;
}

int main() {
    cin >> N;
    
    vector<int> P(N*N);
    for (int i = 0; i < N*N; i++) {
        cin >> P[i];
        P[i]--;
    }
    
    dist = vector<vector<int>>(N, vector<int>(N, 0));
    vacant = vector<vector<bool>>(N, vector<bool>(N, false));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = min(min(i, N-1-i), min(j, N-1-j));
        }
    }
    
    for (int i = 0; i < N*N; i++) {
        int x = P[i]/N, y = P[i]%N;
        ans += dist[x][y];
        vacant[x][y] = true;
        dfs(x, y);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 28440
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		while (k-- > 0) {
			int a = in.nextInt() - 1;
			if (a > n / 2) {
				a = n - (a + 1);
			}
			int b = in.nextInt() - 1;
			if (b > n / 2) {
				b = n - (b + 1);
			}
			System.out.println(Math.min(a, b) % 3 + 1);
		}
	}
}

Measured memory_bytes: 25188
//#pragma GCC optimize("O3", "no-stack-protector")
//#pragma GCC target("sse4", "avx", "popcnt", "lzcnt", "sse3", "sse4.1", "sse4.2", "sse2", "tune=native")
//#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using old = long double;

const int N = 3010;

int a[N];
ll dp[N][N];

ll solve(int l, int r, int p = 0) {
    if (l == r) {
        return dp[l][r] = a[l] * (p ? -1 : 1);
    }
    if (dp[l][r] < LLONG_MAX) {
        return dp[l][r];
    }
    ll res = 0;
    if (p == 0) {
        res = a[l] + solve(l + 1, r, p ^ 1);
        res = max(res, a[r] + solve(l, r - 1, p ^ 1));
    } else {
        res = -a[l] + solve(l + 1, r, p ^ 1);
        res = min(res, -a[r] + solve(l, r - 1, p ^ 1));
    }
    return dp[l][r] = res;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = LLONG_MAX;
        }
    }
    cout << solve(0, n - 1);
    return 0;
}

Measured memory_bytes: 71168
def abc079_c():
    stlist = input()

    def DFS(i,sum,li):
        if i == len(stlist)-1:
            if sum == 7:
                print(str(stlist[0])+str(li[0])+str(stlist[1])+str(li[1])+str(stlist[2])+str(li[2])+str(stlist[3])+"=7")
                exit()
            return

        #+
        li[i]="+"
        DFS(i+1,sum+int(stlist[i+1]),li)

        #-
        li[i]="-"
        DFS(i+1,sum-int(stlist[i+1]),li)

    DFS(0,int(stlist[0]),[[] for i in range(3)])










abc079_c()


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
typedef double DOUBLE;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll LL_INF = 1e17 + 10;
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

ll pow_mod(ll a, ll st) {
	ll ans = 1ll;
	for(; st; st >>= 1ll) {
		if (st & 1) {
			ans = (ans * a) % MOD;
		}
		a = (a * a) % MOD;
	}
	return ans;
}

void solve(){
	ll h, w, t;
	cin >> h >> w >> t;
	ll n = gcd(h, t);
	ll m = gcd(w, t);
	ll n1 = h / n;
	ll m1 = w / m;
	ll ans = (pow_mod(2, n1) + pow_mod(2, m1) - 1) % MOD;
	ll g = gcd(n1, m1);
	ll add = (pow_mod(2, g) + MOD - 2) % MOD;
	ans = (ans + add) % MOD;
	ans = pow_mod(ans, n * m);
	cout << ans << endl;
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
#include <iostream>
typedef long long ll;
using namespace std;
ll N;
ll nagosan(int nana,int go,int san,ll now_num,int now_keta,int keta){
  if(now_keta == keta){
    if(nana == 0 || go == 0 || san == 0 || now_num > N){
      return 0;
    }
    else return 1;
  }

  return nagosan(nana+1,go,san,now_num*10+7,now_keta+1,keta)+nagosan(nana,go+1,san,now_num*10+5,now_keta+1,keta)+nagosan(nana,go,san+1,now_num*10+3,now_keta+1,keta);
}


int main(){
  cin >> N;
  ll n = N;
  int keta = 0;
  while(n){
    n /=10;
    keta++;
  }

  ll ans = 0;

  for(int i = 3;i <= keta;i++){
    ans += nagosan(0,0,0,0,0,i);
  }

  cout << ans << endl;
}


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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int H,W;
    int A[500][500],B[500][500];
    cin >> H >> W;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> A[i][j];
            B[i][j]=A[i][j];
        }
    }

    int cnt=0;
    for(int i=0;i<H-1;i++){
        for(int j=0;j<W;j++){
            if(A[i][j]%2==1){
                cnt++;
                A[i+1][j]++;
            }
        }
    }
    for(int j=0;j<W-1;j++){
        if(A[H-1][j]%2==1){
            cnt++;
            A[H-1][j+1]++;
        }
    }
    cout << cnt << endl;
    for(int i=0;i<H-1;i++){
        for(int j=0;j<W;j++){
            if(B[i][j]%2==1){
                cout << to_string(i+1) << " " << to_string(j+1) << " " << to_string(i+2) << " " << to_string(j+1) << endl;
                B[i+1][j]++;
            }
        }
    }
    for(int j=0;j<W-1;j++){
        if(B[H-1][j]%2==1){
            cout << to_string(H) << " " << to_string(j+1) << " " << to_string(H) << " " << to_string(j+2) << endl;
            B[H-1][j+1]++;
        }
    }
    
    return 0;
}

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

int main(){
	int n;
	while(cin >> n,n){
		int w,h;
		cin >> w >> h;
		int map[h][w];
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				map[i][j]=0;
			}
		}
		int x,y;
		for(int i=0;i<n;i++){
			cin >> x >> y;
			map[y-1][x-1]=1;
		}
		int s,t;
		cin >> t >> s;
		int m=0;
		for(int i=0;i<=h-s;i++){
			for(int j=0;j<=w-t;j++){
				int count=0;
				for(int k=0;k<s;k++){
					for(int l=0;l<t;l++){
						if(map[k+i][l+j]==1){
							count++;
						}
					}
				}
				m=max(m,count);
			}
		}
		cout << m << endl;
	}
}

Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll A,B;
    cin >>A>>B;
    if(A<=8 && B<=8){
        cout<<"Yay!"<<endl;
    }else{
        cout<<":("<<endl;
    }



    return 0;
    

}

Measured memory_bytes: 3600
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define all(a) (a).begin(),(a).end()

typedef pair<int,int> P;

// uf
struct unionfind {
  vector<int> par;
  unionfind(int n) : par(n) { for (int i = 0; i < n; ++i) par[i] = i; }
  
  int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  
  void unite(int x, int y) {
    par[find(x)] = par[find(y)] = find(x);
  }
  
  bool same(int x, int y) { return find(x) == find(y); }
};

struct edge {
  int u, v, cost;
  bool operator<(const edge& other) const {
    return cost < other.cost;
  }
};

int N, M;
int H[202];
int G[202][202];

// 連結でなくなる時間を求める
int getTime() {
  vector<P> lands;
  rep(i,N) lands.push_back(P(H[i], i));
  sort(all(lands));
  vector<int> enable(N, 1);
  rep(z,N) {
    unionfind uf(N);
    // enable の島だけで掛けられそうな橋をとりあえず掛ける
    rep(i,N) {
      if (!enable[i]) continue;
      rep(j,N) {
        if (!enable[j] || i == j || (G[i][j] <= 0)) continue;
        if (!uf.same(i,j)) {
          uf.unite(i,j);
        }
      }
    }
    // 連結であるか
    rep(i,N) {
      if (!enable[i] || i == lands[z].second) continue;
      if (!uf.same(i, lands[z].second)) {
        if (z == 0) return -1;
        return lands[z-1].first;
      }
    }
    enable[lands[z].second] = 0;    
  }
  return lands.back().first + 1;
}

int solve() {
  int time = getTime(), ans = 0;
  vector<P> lands;
  rep(i,N) lands.push_back(P(H[i], i));
  sort(all(lands), greater<P>());
  // 最初から連結でない
  if (time == -1) {
    return 0;
  }
  vector<edge> es;
  rep(i,N) rep(j,N) if (G[i][j]) es.push_back((edge){i, j, G[i][j]});
  sort(all(es));
  vector<int> on(N, 0);
  // 橋を掛ける  
  unionfind uf(N);
  rep(z,N) {
    on[lands[z].second] = 1;
    const int t = lands[z].first;
    if (t > time) continue;
    if ((z+1 < N) && (lands[z].first == lands[z+1].first)) continue;
    rep(i,es.size()) {
      edge e = es[i];
      int u = e.u, v = e.v;
      if (on[u] && on[v]) {
        if (G[u][v] && !uf.same(u, v)) {
          ans += e.cost;
          uf.unite(u, v);
        }
      }
    }
  }
  return ans;
}

int main() {
  while (scanf("%d%d", &N, &M), N) {
    // G[][] 初期化
    rep(i,N) rep(j,N) G[i][j] = 0;
    rep(i,N) G[i][i] = 0;
    
    rep(i,N) scanf("%d", H+i);
    rep(i,M) {
      int a, b, c;      
      scanf("%d%d%d", &a, &b, &c);
      --a; --b;
      G[a][b] = G[b][a] = c;
    }
    printf("%d\n", solve());
  }
  return 0;
}

Measured memory_bytes: 2540
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#define int long long
#define endre getchar();getchar();return 0
#define moder 1000000007
#define inf 1000000000000000000
#define rep(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int kai(int x) {
	if (x == 0)return 1;
	return (kai(x - 1)*x) % moder;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
map<int, int> factor(int m) {
	map<int, int>res;
	for (int i = 2; i*i <= m; i++) {
		while (m%i == 0) {
			res[i]++;
			m /= i;
		}
	}
	if (m != 1)res[m]++;
	return res;
}

/*--------Library Zone!--------*/

struct cake
{
	int beauty, taste, popularity;
};

int n, m, ans;
cake c[1005];
signed main() {
	cin >> n >> m;
	rep(i, n) {
		cin >> c[i].beauty >> c[i].taste >> c[i].popularity;
	}
	rep(i, 8) {
		int cnt[1005];
		rep(j, n) {
			cnt[j] = 0;
			if ((i >> 0) & 1)cnt[j] += c[j].beauty;
			else cnt[j] += c[j].beauty*-1;
			if ((i >> 1) & 1)cnt[j] += c[j].taste;
			else cnt[j] += c[j].taste*-1;
			if ((i >> 2) & 1)cnt[j] += c[j].popularity;
			else cnt[j] += c[j].popularity*-1;
		}
		sort(cnt, cnt + n);
		reverse(cnt, cnt + n);
		int sum = 0;
		rep(j, m)sum += cnt[j];
		ans = max(ans, sum);
	}
	cout << ans << endl;
	endre;
}

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
const int M = 1e9 + 7;

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}


int modpow(int x, int p) {
    if (!p) return 1;
    int val = modpow(x, p / 2);
    val = (val * val) % M;
    if (p & 1) val = (val * x) % M;
    return val;
}

int inverse(int x) {
    return modpow(x, M - 2);
}

void solve() {
    string s;
    read(s);
    
    FOR(s.size()) {
        if (i % 2 == 0) write(s[i]);
    }
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
    //read(tt);
    FOR(tt) {
        //write("Case #", i + 1, ": ");
        solve();
        
    }
    
}


Measured memory_bytes: 3784
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)

N,K = mint()
A = lint()
print((N-1-1)//(K-1)+1)

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define p(x) cout << (x) << endl
#define FOR(i,r,n) for(ll i=(ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n); i>=r; i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) REP(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define pb push_back

const int inf = (int)1e9;
const ll INF = (ll)1e18;

ll n,cnt=0, ans=0;
string s,t;


// vectorの中身をcout << vs;で表示
template <class T>
ostream &operator<<(ostream &o, const vector<T> &v)
{
    o << "{";
    for (int i = 0; i < (int)v.size(); i++) o << (i > 0 ? ", " : "") << v[i];
    o << "}";
    return o;
}

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

ll lcm (ll a, ll b) {
	return (a / gcd (a, b)) * b;
}

bool is_prime (ll n) {
		if (n < 2) return false;
		else if (n == 2) return true;
		else if (n % 2) return false;
		
		double sqrtn = sqrt(n);
		for (ll i = 0; i < sqrtn; i += 2) {
			if (n % i == 0) return false; 
		}
		return true;
}

// ==================== template ============================

ll ctoi(char c) {
	return (ll)c - 48;
}

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

	cin >> s;
	REP(i, s.size()) {
		cnt += ctoi(s.at(i));
	}

	cout << (stoi(s) % cnt == 0 ? "Yes" : "No") << endl;

}



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

int main(){
    int N;
    int C_list[510], S_list[510], F_list[510];
    cin >> N;
    for(int i=0; i<N-1; i++){
        cin >> C_list[i] >> S_list[i] >> F_list[i];
    }
    for(int i=0; i<N-1; i++){
        int t = 0;
        for(int j=i; j<N-1; j++){
            int k = ((t-S_list[j]) + F_list[j] -1 )/F_list[j];
            if(k >= 0){
                t = S_list[j] + k*F_list[j] + C_list[j];
            }else{
                t = S_list[j] + C_list[j];
            }
        }
        cout << t << endl;
    }
    cout << 0;
    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;

const string YES = "Yes";
const string NO = "No";

void solve(long long N){
	int u=1;
	while(u*2<=N){
		u*=2;
	}
	if(N==u){
		cout << NO << endl;
		return;
	}

	cout << YES << endl;
	int v=N;
	if(v%2==0){
		v--;
	}
	if(N%2){
		for(int i=2;i<=N;i++){
			cout << 1 << " " << i << endl;
			cout << i << " " << (i^1)+N << endl;
		}
		cout << N+1 << " " << N+2 << endl;
		return;
	}
	for(int i=2;i<N;i++){
		cout << 1 << " " << i << endl;
		cout << i << " " << (i^1)+N << endl;
	}
	cout << N+1 << " " <<  N+2 << endl;
	cout << N << " " << (N^u) << endl;
	cout << 2*N << " " << (u^1) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 2304
#include<cstdio>
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 200000
int n,a[MN+5],b[MN+5];
int cal(int x)
{
	int i,l,r;
	for(i=1;i<n<<1;++i)b[i]=a[i]>=x;
	for(l=n;l>1&&b[l-1]!=b[l];--l);
	for(r=n;r+1<n<<1&&b[r+1]!=b[r];++r);
	if(l==1&&r==n*2-1)return b[n]^(n&1)^1;
	return n-l<r-n?b[l]:b[r];
}
int main()
{
	int i,l,r,mid,ans;
	for(n=read(),i=1;i<n<<1;++i)a[i]=read();
	for(l=1,r=2*n-1;l<=r;)
		if(cal(mid=l+r>>1))ans=mid,l=mid+1;else r=mid-1;
	printf("%d",ans);
}

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

int cnt[51];
int main() {
  int N,M; cin >> N >> M;
  int a[51],b[51];
  for ( int i = 1; i <= M; i++ ) {
    cin >> a[i] >> b[i];
    cnt[a[i]]++;
    cnt[b[i]]++;
  }
  for ( int i = 1; i <= N; i++ ) {
    cout << cnt[i] << endl;
  }
  return 0;
}


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

#define Fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define ld long double
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) cin>>n
#define pl(n) cout<<n
#define sze(v) (int)(v.size())

typedef vector<int>Vl;
typedef pair<int,int>pii;
typedef vector<pii>Vll;
typedef vector<vector<int>>Vv;
typedef vector<pair<int,pii> >Vlll;
typedef priority_queue <int, vector<int>, greater<int>>PQL;
typedef unordered_map<int,int>ump;

const int mod=1e9+7;
const int modx=998244353;
const int Nx=1e5+2;
const int inf= (int)(1e19+10LL);

void solve(){
  int n;
  sl(n);
  int ans=(1000-n%1000)%1000;
  cout<<ans<<endl;

		
}
 
signed main(){
   int test=1;
   //sl(test);
   while(test--){
      solve();
 
   }
  return 0;
}


Measured memory_bytes: 3584
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if (a == b) {
            System.out.println(c);
        } else if (b == c) {
            System.out.println(a);
        } else {
            System.out.println(b);
        }
    }
}

Measured memory_bytes: 21844
import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

def BIT_update(tree,x,value):
    while x <= M:
        tree[x] += value
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        BIT_update(tree,L,1)
        BIT_update(tree,R+1,-1)
        long -= 1
    answer[m] = sum(BIT_sum(tree,x) for x in range(m,M+1,m)) + long

print('\n'.join(map(str, answer[1:])))

Measured memory_bytes: 104412
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja
//Coin Changing Problem
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in");
    //std::ifstream in("./input.txt");
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif    
    ll n,m; cin>>n>>m;
    vector<ll> cm(m);
    for(auto&& c:cm) cin>>c;
#if 01
    vector<vector<ll>> dp(m+1,vector<ll>(n+1,INT32_MAX)); //[m種類コイン][n円]
    dp[0][0]=0;
    FOR(i,0,m){
        FOR(j,0,n+1){
            auto c=cm[i];
            if (dp[i][j]<INT32_MAX) chmin(dp[i+1][j],dp[i][j]);
            if(j-c>=0){
                if (dp[i][j-c]<INT32_MAX) chmin(dp[i+1][j],dp[i][j-c]+1);
                if (dp[i+1][j-c]<INT32_MAX) chmin(dp[i+1][j], dp[i+1][j-c]+1);
            }
        }
    }
    cout<<dp[m][n]<<endl;
#else
    vector<vector<ll>> dp(m+1,vector<ll>(n+1,INT32_MAX)); //[m種類コイン][n円]
    dp[0][n]=0;
    FOR(i,0,m){
        for(ll j=n;j>=0;--j){
            dp[i+1][j]=dp[i][j];
            auto c = cm[i];
            if(j-c>=0){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j-c]+1);
                dp[i+1][j]=min(dp[i+1][j],dp[i+1][j-c]+1);
            }
        }
    }
    cout<<dp[m][n]<<endl;
#endif
    return 0;
}


Measured memory_bytes: 11592
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);

int main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    cout << ((n == m) ? "Yes\n" : "No\n");
}

Measured memory_bytes: 256
#include<stdio.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
int main(void){
  char s[3]; scanf("%s",&s);
  if(s[0] == s[1]&&s[1] == s[2]){printf("No");  }
  else{printf("Yes");}
  return 0;
}

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

ll comb(int n, int r) {
    r = min(r, n - r);
    ll res = 1;
    for (int i = 0; i < r; ++i) {
        res *= (n - i);
    }
    for (int i = 0; i < r; ++i) {
        res /= (r - i);
    }
    return res;
}

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

    int N, P;
    cin >> N >> P;
    vector<int> cnt(2, 0);
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        cnt.at(A % 2)++;
    }

    ll res = pow(2, cnt.at(0));
    ll ans = 0;
    for (int x = P; x <= cnt.at(1); x += 2) {
        ans += res * comb(cnt.at(1), x);
    }

    cout << ans << endl;

    return 0;
}

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

int main()
{
    int N, T;
    cin >> N >> T;

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

    vector<vector<pair<int, int>>> dp(N + 1, vector<pair<int, int>>(T, make_pair(0, 0)));
    int a, b;
    for (int i = 0; i < N; i++)
    {
        a = A[i];
        b = B[i];
        for (int j = 0; j < T; j++)
        {
            if (dp[i + 1][j].first + dp[i + 1][j].second < dp[i][j].first + dp[i][j].second)
            {
                dp[i + 1][j] = dp[i][j];
            }

            if (dp[i + 1][j].first + dp[i + 1][j].second < dp[i][j].first + b)
            {
                dp[i + 1][j] = make_pair(dp[i][j].first, b);
            }

            if (a + j < T)
            {
                dp[i + 1][a + j] = make_pair(dp[i][j].first + b, dp[i][j].second);
            }
        }
    }

    int ans = 0;
    for (pair<int, int> p : dp.back())
    {
        ans = max(ans, p.first + p.second);
    }
    cout << ans << endl;
}


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

using namespace std;

int main(){
	string in;
	getline(cin,in);
	for(int i=0;i<in.length();i++){
		if(in.substr(i,5)=="apple")in.replace(i,5,"peach");
		else if(in.substr(i,5)=="peach")in.replace(i,5,"apple");
	}
	
	cout<<in<<endl;
	
}

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

int main() {
	string S,T;
	bool ans = false;
	cin >> S >> T;
	for(int i = 0; i < S.length(); i++){
		if(S == T){
			ans = true;
		}
		S = S.substr(1) + S[0];;
	}
	if(ans){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <iomanip>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
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 ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000
#define MAX_N 11
#define MAX_M 11

int n, m;
int k[MAX_N];
int s[MAX_M][MAX_N];
int p[MAX_M];

bool isValid(vector<int> v) {
  rep(i, 0, m) {
    int tmp = 0;
    rep(_v, 0, v.size()) {
      rep(j, 0, k[i]) if(v[_v] == s[i][j] - 1) ++tmp;
    }
    if(tmp % 2 != p[i]) return false;
  }
  return true;
}

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

  cin >> n >> m;
  rep(i, 0, m) {
    cin >> k[i];
    rep(j, 0, k[i]) cin >> s[i][j];
  }
  rep(i, 0, m) cin >> p[i];

  int rsl = 0;
  for(int bit = 0; bit < 1 << n; ++bit) {
    vector<int> v;
    rep(i, 0, n) {
      if(bit & 1 << i) {
        v.push_back(i);
      }
    }
    if (isValid(v)) ++rsl;
  }
  cout << rsl << endl;
}


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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	int a, b, h;
	cin >> a >> b >> h;

	cout << (a + b) * h / 2 << endl; 
	
	return 0;
}


Measured memory_bytes: 256