akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const int MOD = 1000000007;

int dp[100005][2][2];

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

  dp[0][0][0] = 1;
  dp[0][1][1] = 1 * 2;
  REP(i,1,L.size()){
    if(L[i]=='0'){
      dp[i][1][0] += dp[i-1][1][0];
      dp[i][1][0] %= MOD;
      dp[i][1][0] += dp[i-1][1][1];
      dp[i][1][0] %= MOD;

      dp[i][0][0] += dp[i-1][0][0];
      dp[i][0][0] %= MOD;
      dp[i][0][0] += dp[i-1][0][1];
      dp[i][0][0] %= MOD;

      dp[i][0][1] += dp[i-1][0][0];
      dp[i][0][1] %= MOD;
      dp[i][0][1] += dp[i-1][0][1];
      dp[i][0][1] %= MOD;
      dp[i][0][1] *= 2;
      dp[i][0][1] %= MOD;
    }else{
      dp[i][1][1] += dp[i-1][1][0];
      dp[i][1][1] %= MOD;
      dp[i][1][1] += dp[i-1][1][1];
      dp[i][1][1] %= MOD;
      dp[i][1][1] *= 2;
      dp[i][1][1] %= MOD;

      dp[i][0][0] += dp[i-1][0][0];
      dp[i][0][0] %= MOD;
      dp[i][0][0] += dp[i-1][0][1];
      dp[i][0][0] %= MOD;
      dp[i][0][0] += dp[i-1][1][0];
      dp[i][0][0] %= MOD;
      dp[i][0][0] += dp[i-1][1][1];
      dp[i][0][0] %= MOD;

      dp[i][0][1] += dp[i-1][0][0];
      dp[i][0][1] %= MOD;
      dp[i][0][1] += dp[i-1][0][1];
      dp[i][0][1] %= MOD;
      dp[i][0][1] *= 2;
      dp[i][0][1] %= MOD;
    }
  }

  int ret = 0;
  ret += dp[L.size()-1][0][0];
  ret %= MOD;
  ret += dp[L.size()-1][0][1];
  ret %= MOD;
  ret += dp[L.size()-1][1][0];
  ret %= MOD;
  ret += dp[L.size()-1][1][1];
  ret %= MOD;
  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 2048
#include <iostream>
    #include<math.h>
    using namespace std;

    int main()
    {
      long long  a,b,k;
      cin>>a>>b>>k;
       if(a-k<0)
       {
           k=k-a;
           a=0;
           if(b-k<0) b=0;
            else b=b-k;
       }
       else a=a-k;
       cout<<a<<' '<<b<<endl;
        return 0;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b; string s;
    cin>>a>>b;
    cin>>s;
    bool done = true;
    for(int i=0; i<a+b+1; ++i) {
        if(i != a)
        {
            if(!isdigit(s[i]))
            {
                done = false;
                break;
            }
        }
        else
        {
            if(!(s[i] == '-'))
            {
                done = false;
                break;
            }
        }
    }
    if(done)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;


    return 0;
}



Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
int main() {
	while (true) {
		int n, w, d;
		cin >> n >> w >> d;
		if (w == 0) return 0;
		vector<pair<int, int>> inputs;
		inputs.push_back(make_pair(w, d));
		REP(i, n) {
			int a, b;
			cin >> a >> b;
			a--;
			b %= (inputs[a].first + inputs[a].second);
			if (b <= inputs[a].first) {
				int geko = min(b, inputs[a].first - b);
				int tea = inputs[a].second;
				inputs.push_back(make_pair(geko, tea));
				geko = inputs[a].first - geko;
				inputs.erase(inputs.begin() + a);
				inputs.push_back(make_pair(geko,tea));
			}
			else{
				b -= inputs[a].first;
				int geko = min(b, inputs[a].second - b);
				int tea = inputs[a].first;
				inputs.push_back(make_pair(tea, geko));
				geko = inputs[a].second - geko;
				inputs.erase(inputs.begin() + a);
				inputs.push_back(make_pair(tea, geko));
			}
		}
		vector<int> neko;
		REP(q, inputs.size()) {
			neko.push_back(inputs[q].first * inputs[q].second);
		}
		sort(neko.begin(), neko.end());
		cout << neko[0];
		for (int q = 1; q < neko.size();++q) {
			cout << " " << neko[q];
		}
		cout << endl;
	}
}


Measured memory_bytes: 3008
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = float('inf')

N, K = list(map(int, input().split()))     # スペース区切り連続数字
A = list(map(int, input().split()))     # スペース区切り連続数字

for i in range(K, N):
    r = i - K
    l = i
    if A[r] >= A[l]:
        print("No")
    else:
        print("Yes")


Measured memory_bytes: 94304
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n,M[MAX][MAX];
int prim(){
  int u,minv;
  int d[MAX],p[MAX],color[MAX];
  for(int i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }
  d[0]=0;
  while(1){
    minv=INFTY;
    u=-1;
    for(int i=0;i<n;i++){
      if(minv > d[i] && color[i] != BLACK){
	u=i;
      minv=d[i];
    }
  }
  if(u==-1) break;
  color[u]=BLACK;
  for(int v=0;v<n;v++){
    if(color[v] != BLACK && M[u][v] != INFTY){
      if(d[v]>M[u][v]){
	d[v]=M[u][v];
	p[v]=u;
	color[v]=GRAY;
      }
    }
  }
  }
  int sum=0;
  for(int i=0;i<n;i++){
    if(p[i] != -1) sum += M[i][p[i]];
  }
  return sum;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      int e; cin>>e;
      M[i][j] = (e==-1) ? INFTY : e;
    }
  }
  cout << prim() << endl;
  return 0;
}



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

// 問題文
// 12 月 30 日の M 時から次の年になるまでは何時間か、求めてください。
// 制約 1 ≦ M ≦ 23 入力は全て整数

int main()
{
  int M;

  cin >> M;
  cout << 24*2 -M << endl;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  string S;
  cin >> S;
  string m = {S[5],  S[6]};
  int month = stoi(m);
  string d = {S[8],  S[9]};
  int day = stoi(d);
  if((month == 4 && day == 31)||month > 4){
    cout << "TBD" <<endl;
  } else{
    cout << "Heisei" <<endl;
  }
}

Measured memory_bytes: 3652
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int main(){
  int M,K;cin>>M>>K;
  int N=1;
  int i,j;
  rep(i,M) N*=2;
  if(K>=N){
    cout<<-1<<endl;
    return 0;
  };
  if(M==1 and M==K){
    cout<<-1<<endl;
    return 0;
  }
  if(M==1 and K==0){
    cout<<0<<" "<<0<<" "<<1<<" "<<1<<endl;
    return 0;
  }
  vector<int> ans;
  rep(i,N){
    if(i==K) continue;
    ans.push_back(i);
    //cout<<i<<endl;
  }
  ans.push_back(K);
  for(i=N-1;i>=0;i--){
    if(i==K) continue;
    ans.push_back(i);
  }
  ans.push_back(K);
  rep(i,N*2) cout<<ans[i]<<" ";
  cout<<endl;
}


Measured memory_bytes: 2932
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    def main():
       s=input()
       for i in range(len(s)):
           for j in range(i+1,len(s)):
               if s[i]=='C' and s[j]=='F':
                   return 'Yes'
       return 'No'
    print(main())
resolve()

Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main(){
    int H, W;
    
    while(true){
        cin >> H >> W;
        if(H == 0 && W == 0) break;
        for (int i = 0; i < H; i++){
            for ( int j = 0; j < W; j++){
                cout << "#" ;
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}



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

int l[10], r[10], s[10];
int n, x, m;

vector<int> ans;
int mx;

bool dfs(int num, vector<int>& lion) {
  
  if(num == n) {
    for(int i=0; i<m; i++) {
      int sum = 0;
      for(int j=l[i]; j<=r[i]; j++) sum += lion[j];
      if(sum != s[i]) { return false; }
    }
    
    int all = 0;
    for(int i=0; i<n; i++) {
      all += lion[i];
    }
    
    if(mx < all) {
      mx = all;
      ans = lion;
    }
    
    return true;
  }
  else {
    bool ok = false;
    for(int i=0; i<=x; i++) {
      lion[num] = i;
      ok |= dfs(num+1, lion);
    }
    return ok;
  }
}


int main() {
  
  cin >> n >> x >> m;
  
  mx = -1;
  
  for(int i=0; i<m; i++) {
    cin >> l[i] >> r[i] >> s[i];
    l[i] --; r[i] --;
  }
  
  mx = -1;
  vector<int> lion(n);
  
  bool valid = dfs(0, lion);
  
  if(valid) {
    for(int i=0; i<n; i++) {
      if(i) cout << " " << ans[i];
      else cout << ans[i];
    }
    cout << endl;
  }
  else {
    cout << -1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1216
#include <cstdio>
using namespace std;

int n, A[50];

int solve(int i, int m)
{
    if (m == 0){
        return 1;
        }
    if (i >= n ) {
        return 0;
    }
    int res = solve(i+1, m) || solve(i+1, m - A[i]);
    return res;
}

int main(void)
{
    int q;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
    }
    scanf("%d",&q);
    for (int i = 0; i < q; i++)
    {
        int m;
        scanf("%d", &m);
        int ans = solve(0,m);
        if (ans) 
            printf("yes\n");
        else
            printf("no\n");
    }
    
    return 0; 
}


Measured memory_bytes: 2696
///
// File:  c.cpp
// Author: ymiyamoto
//
// Created on Wed Oct  4 20:43:39 2017
//

#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;
static vector<int32_t> array;

int32_t main()
{
  uint32_t N;
  cin >> N;

  for (uint32_t i = 0; i < N; i++) {
    int32_t val;
    cin >> val;
    array.push_back(val);
  }

  int64_t cost = INT64_MAX;
  for (int32_t ave = -100; ave <= 100; ave++) {
    int64_t cost_at = 0;
    for (uint32_t i = 0; i < array.size(); i++) {
      cost_at += (array[i] - ave) * (array[i] - ave);
    }
    cost = min(cost, cost_at);
  }

  cout << cost << endl;

  return 0;
}


Measured memory_bytes: 256
fn solve(_n: &str) -> &str {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let a = s.split_whitespace().map(|x|x.parse::<u32>().unwrap()).filter(|x| x%2!=0).count();
    if a%2==0 { "YES" } else { "NO" }
}
fn main() {
    loop {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_right();
        if s=="" { break; }
        println!("{}",solve(&s));
    }
}

Measured memory_bytes: 1404
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define CR0(a) (memset(a,0,sizeof(a)))
#define CR1(a) (memset(a,-1,sizeof(a)))
#define CRf(a) (memset(a,0x3f,sizeof(a)))
using namespace std;
const int mod=1e9+7;

map<ll,ll> M;

ll solve(ll n){ 
    if(M[n]>0){
        return M[n];
    } 
    return M[n]=((solve(n/2)+solve((n-1)/2))%mod+solve((n-2)/2))%mod;
} 

int main(){   
#ifndef ONLINE_JUDGE
#endif
    ll n;cin>>n;
    M[0]=1;
    M[1]=2;
    cout<<solve(n)<<endl;
    return 0;
} 


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    int a, b;
    cin >> a >> b;
    if (a + b == 15) cout << '+' << endl;
    else if (a * b == 15) cout << '*' << endl;
    else cout << "x" << endl;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
using Pl = pair<ll, int>;

int ans = 0;
string s;
int n;

void dfs(int depth = 0, int tot = 0){
    if(depth == n){
        ans = max(ans, tot);
        return;
    }
    int now = s[depth] - '0';
    dfs(depth + 1, tot + now);
    if(n-1-depth > 0) dfs(n, tot + now-1 + 9*(n-1-depth));
}

void Main() {
	cin >> s;
    n = s.size();
    dfs();
    
    cout << ans << endl;
    return;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 256
def main34():
    nkdata = input().split()
    nk = []
    for i in range(2):
        nk.append(int(nkdata[i]))
    if nk[0] % nk[1] == 0:
        print(0)
    else:
        print(1)

if __name__ == "__main__":
    main34()

Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>

#define roop(i, n) for(int i=0;i<n;i++)
#define DIV 1000000007

using namespace std;
using ll = long long int;
using ull = unsigned long long;

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

ll combination(ll n, ll r) {
	if (n < 0 || r < 0 || r > n) return -1;

	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> num(r);
	vector<ll> den(r);

	for (ll i = 0; i < r; i++) {
		num[i] = n - r + i + 1;
		den[i] = i + 1;
	}

	for (ll p = 2; p <= r; p++) {
		ll pivot = den[p - 1];
		if (pivot > 1) {
			ll offset = (n - r) % p;
			for (ll k = p - 1; k < r; k += p) {
				num[k - offset] /= pivot;
				den[k] /= pivot;
			}
		}
	}
	ll result = 1;
	for (ll k = 0; k < r; k++) {
		if (num[k] > 1) result *= num[k];
	}
	return result;
}

int main() {
	int n,m;
	cin>>n>>m;
	vector<int> h(n+1),ma(n+1);
	for(int i=1;i<=n;i++) {
		cin>>h[i];
		ma[i]=0;
	}

	for(int i=0;i<m;i++) {
		int a,b;
		cin>>a>>b;
		ma[a]=max(ma[a],h[b]);
		ma[b]=max(ma[b],h[a]);
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=h[i]>ma[i];
	}
	cout<<ans<<endl;
	
	return 0;
}

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string d[7] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
  string S;
  cin >> S;
  int ans = 7;
  for (int i = 0; i < 7; ++i) if (S == d[i]) ans -= i;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){

  int r,c, i, j, sum=0, count=0, total=0;
  int number[101][101];

  scanf("%d %d", &r, &c);

  for(i = 1; i <= r; i++){
    for(j = 1; j <= c; j++){
      scanf("%d", &number[i][j]);
    }
  }
  
  for(i = 1; i <= r; i++){
    sum = 0;
    for(j = 1; j <= c; j++){
      printf("%d ", number[i][j]);
      sum = sum + number[i][j];
    }
    printf("%d\n", sum);
  }

  for(j = 1; j <= c; j++){
    count = 0;
    for(i = 1; i <= r; i++){
      count += number[i][j];
         } 
    total +=count; 
    printf("%d ", count);
  } 
  printf("%d\n", total);
  
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n;
  cin>>n;
  vector<int> a(n), b(n);
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];
  sort(b.rbegin(),b.rend());
  map<int,int> c;
  rep(i,n)c[a[i]]++;
  rep(i,n)c[b[i]]++;
  int saidai=0;
  for(auto p:c)chmax(saidai,p.second);
  if (saidai > n) {
      cout<<"No"<<endl;
      return 0;
  }
  cout<<"Yes"<<endl;
  rep(i,n){
    if(a[i]!=b[i])continue;
    else{
        rep(j,n){
          if(a[i]!=b[j]&&a[j]!=b[i]){
            swap(b[i],b[j]);
            break;
          }
        }
    }
  }
  rep(i,n)cout<<b[i]<<" ";
  cout<<endl;
  return 0;
}

Measured memory_bytes: 14352
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
const int MAX_V=100000;

int par[MAX_V];				//unionfind??¨ ????´????????£????????????????
int m[MAX_V];				//unionfind??¨ ????´??£?????????£???????????£???????????????????????????????????? ?????????????????????blog?????????
							//?????????????°??????????????????§?????????,semi???????°?????????????????????????????????£?????????(???????????????????????????)

int I;			//dfs?????¨??????id???????????¨
int parent[MAX_V];			//parent[v] = dfs??¨T??§???v??????
int vertex[MAX_V];			//vertex[i] = dfs??????i???????????????
int semi[MAX_V];			//semi[v] = v			if v?????????step2??????????????????
							//			sdom(v)???number		otherwise
int U[MAX_V];				//U[w] = w????????????,step3??§?±???????Cor1???u
int idom[MAX_V];			//idom[v] = idom(v) ???????????????
vector<int> bucket[MAX_V];		//bucket[v] = ???????????§??????sdom(x)=v?????????x?????????(?????????step3???????????£???????????????)
vector<int> G[MAX_V],rG[MAX_V];		//?????¨?????°????????¨,?????????????????????????????????

//unionfind????????????
void init(int N){
	rep(i,N) par[i]=i,m[i]=i;
}
int find(int v){
	if(par[v]==v) return v;
	int r=find(par[v]);
	if(semi[m[v]]>semi[m[par[v]]]) m[v]=m[par[v]];
	return par[v]=r;
}
int EVAL(int v){
	find(v);
	return m[v];
}
void LINK(int x,int y){
	par[y]=x;
}
//unionfind???????????§

void dfs(int v){			//dfs??¨
	semi[v]=I;
	vertex[I++]=v;
	for(int u:G[v]) if(semi[u]<0){
		parent[u]=v;
		dfs(u);
	}
}
void makedomtree(int N,int r){
	init(N);
	rep(i,N) semi[i]=-1;
	dfs(r);									//step1
	for(int i=N-1;i>0;i--){
		//step2
		int w=vertex[i];
		for(int v:rG[w]){
			int u=EVAL(v);
			chmin(semi[w],semi[u]);
		}
		bucket[vertex[semi[w]]].pb(w);		//bucket?????´??°
		LINK(parent[w],w);					//????????????
		//????????????step3
		for(int v:bucket[parent[w]]) U[v]=EVAL(v);
		bucket[parent[w]].clear();			//step3???????????£??????bucket???????¶????
	}
//	semi[0]=-1;
	//step4
	for(int i=1;i<N;i++){
		int w=vertex[i];
		int u=U[w];
//		show(w);
//		show(u);
		if(semi[w]==semi[u]) idom[w]=semi[w];
		else idom[w]=idom[u];
	}

	for(int i=1;i<N;i++){				//idom[w]????????????vertex id????????????????????????
		int w=vertex[i];
		idom[w]=vertex[idom[w]];
	}
	idom[r]=-1;
}
int main(){
	int N,M;
	cin>>N>>M;
	rep(i,M){
		int a,b;
		cin>>a>>b;
		a--,b--;
		G[a].pb(b);
		rG[b].pb(a);
	}
	makedomtree(N,0);
//	rep(v,N) printf("sdom[%d]=%d\n",v,semi[v]);
//	rep(v,N) printf("idom[%d]=%d\n",v,idom[v]);
	int Q;
	cin>>Q;
	rep(tt,Q){
		int v;
		cin>>v;v--;
		int ans=idom[v];
		if(ans==0) ans=v;
		cout<<ans+1<<endl;
	}
}

Measured memory_bytes: 22888
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

const int MOD = 1000000007, INF = 1111111111;
using namespace std;
using lint = long long;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (int i = 0; i < (int)vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}

#ifdef _DEBUG
template <class Head>
void dump(const char* str, Head &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + 1, t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

class UnionFind {
private:
	vector<int> data;
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }

public:
	UnionFind(int size) : data(size, -1) { }
	bool is_same(int x, int y) { return root(x) == root(y); }
	int size(int x) { return -data[root(x)]; }

	void unify(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
};

template<class T = lint>
struct Edge {
	int from, to;
	T cost;
	Edge() {}
	Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
	bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	struct town { int x, y, idx; };
	vector<town> t(N);
	for (int i = 0; i < N; i++) {
		cin >> t[i].x >> t[i].y;
		t[i].idx = i;
	}

	// 辺の候補をすべてpriority_queに入れる
	priority_queue<Edge<>, vector<Edge<>>, greater<Edge<>>> pq;
	// xが近い同士
	sort(t.begin(), t.end(), [&](town &r, town &l) {return r.x < l.x; });
	for (int i = 0; i < N - 1; i++) pq.emplace(t[i].idx, t[i + 1].idx, t[i + 1].x - t[i].x);
	// yが近い同士
	sort(t.begin(), t.end(), [&](town &r, town &l) {return r.y < l.y; });
	for (int i = 0; i < N - 1; i++) pq.emplace(t[i].idx, t[i + 1].idx, t[i + 1].y - t[i].y);

	// kruskal法
	UnionFind uf(N);
	lint ans = 0;
	while (!pq.empty()) {
		
		auto now = pq.top(); pq.pop();

		if (!uf.is_same(now.from, now.to)) {
			uf.unify(now.from, now.to);
			ans += now.cost;
		}
	
	}

	assert(uf.size(0) == N);

	cout << ans << "\n";

	return 0;
}

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

ll sum(long long n) {
  return n * (n + 1) / 2;
}

int main() {
  ll n;
  cin >> n;
  
  cout << sum(n) - sum(n / 3) * 3- sum(n / 5) * 5 + sum(n / 15) * 15 << endl;
  
  return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef priority_queue<long long> prque;
#define ain(i,n,a) for(long long i=0;i<(long long)(n);i++){cin>>a[i];}
#define aout(i,n,a) for(long long i=0;i<(long long)(n);i++){if(i){cout<<" ";}cout<<a[i];if(i==n-1){cout<<endl;}}
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define vsort(v) sort((v).begin(),(v).end())
#define vrsort(v) sort((v).rbegin(),(v).rend())
#define vreverse(v) reverse((v).begin(),(v).end())
#define pf(a) push_front(a)
#define pb(a) push_back(a)
#define INF 1998021900
#define MOD 1000000007
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //input
  vll j(3);cin>>j[0]>>j[1]>>j[2];vsort(j);
  if(((j[0]==j[1])&&(j[1]!=j[2]))||((j[2]==j[1])&&(j[1]!=j[0]))){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
  //caricurate
  //output
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
int main()
{
    ll que, ii, q;
    unsigned long long bit = 0, all = 0, none = 0LL;
    //bool flag = false;
    all = ~all;
    cin >> q;

    rep(i, q)
    {
        cin >> que;
        switch (que)
        {
        case 0: //test
            cin >> ii;
            cout << ((bit & (1LL << ii)) ? 1 : 0) << endl;
            break;
        case 1: //set_ok
            cin >> ii;
            bit |= 1LL << ii;
            break;
        case 2: //clear_ok
            cin >> ii;
            //ll mask = ~(1LL << ii);
            bit &= ~(1LL << ii);
            break;
        case 3: //flip
            cin >> ii;
            //ll mask = 1LL << ii;
            //bit ^= mask;
            //((bit & (1LL << ii)) ? (bit &= ~(1LL << ii)) : (bit |= (1LL << ii)));
            bit ^= (1LL << ii);
            break;
        case 4: //all
            cout << (~bit == 0) << endl;
            //cout << (((bit & all) == all) ? 1 : 0) << endl;
            break;
        case 5: //any
            //flag = false;
            cout << !(bit == 0) << endl;
            //cout << (((bit & none) == none) ? 1 : 0) << endl;
            //cout << flag << endl;
            break;
        case 6: //none
            cout << (bit == 0) << endl;
            //cout << (((bit & none) == none) ? 0 : 1) << endl;
            break;
        case 7: //count
            cout << bitset<64>(bit).count() << endl;
            break;
        case 8:
            // val
            cout << bit << endl;
            break;
        }
    }
}


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

int main() {

	int n, x, c;

	for (int h = 1;; h++) {
		cin >> n >> x;
		c = 0;
		if (n == 0 && x == 0) break;
		for (int i = 1; i <= n; i++) {
			for (int j = i+1; j <= n; j++) {
				for (int k = j+1; k <= n; k++) {
					if (!(i == j || j == k || k == i)) {
						if ((i + j + k) == x) c++;
					}
				}
			}
		}
		cout << c << "\n";
	}

	return 0;
}

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

int main(){
	list<int>ls;
	auto it=ls.end();
	int q;cin>>q;
	rep(i,q){
		int a;cin>>a;
		if(a==0){
			int b;cin>>b;
			it=ls.insert(it,b);
		}
		else if(a==1){
			int b;cin>>b;
			if(b>0)rep(i,b)it++;
			else rep(i,-b)it--;
		}
		else{
			it=ls.erase(it);
		}
	}
	for(auto i:ls)cout<<i<<endl;
}




Measured memory_bytes: 18644
import sys
a = [ list(map(int,input().split(" "))) for i in range(3)]
N=int(input())
c=0
for i in range(N):
  b=int(input())
  for j in range(3):
    
    for z in range(3):
      if a[j][z]-b==0:
        
        a[j][z]=0

if a[0][0]+a[1][1]+a[2][2]==0 or a[2][0]+a[1][1]+a[0][2]==0 or a[0][0]+a[0][1]+a[0][2]==0 or a[1][0]+a[1][1]+a[1][2]==0 or a[2][0]+a[2][1]+a[2][2]==0 or a[0][0]+a[1][0]+a[2][0]==0 or a[0][1]+a[1][1]+a[2][1]==0 or a[0][2]+a[1][2]+a[2][2]==0:
    print('Yes')
else:


    print('No')
      

Measured memory_bytes: 3064
#include <vector>
#include <iostream>
#include <queue>
#include <cassert>
#include <tuple>
#include <algorithm>

using namespace std;
typedef long long ll;

template<class D, int S>
struct WaveletTree {
    static const int N = 1<<S;
    typedef pair<D, int> P;
    int n;
    P x[N];
    int d[S+1][N];
    int lc[S][N];

    void built(int l, int r, int dps) {
        if (dps == S) return;
        int pl = l, md = (l+r)/2, pr = md;
        for (int i = l; i < r; i++) {
            if (d[dps][i] < md) {
                d[dps+1][pl++] = d[dps][i];
            } else {
                d[dps+1][pr++] = d[dps][i];
            }
            lc[dps][i] = pl-l;
        }
        built(l, md, dps+1);
        built(md, r, dps+1);
    }

    void init(int nn = N) {
        n = nn;
        for (int i = 0; i < N; i++) {
            x[i].second = i;
        }
        sort(x, x+n);
        for (int i = 0; i < N; i++) {
            d[0][x[i].second] = i;
        }
        built(0, N, 0);
    }
    //[l, r)??§k???????????°????????????
    int get(int l, int r, int k, int dps, int idx) {
        assert(1 <= k && k <= r-l);
        if (dps == S) {
            return d[dps][l];
        }
        int ls = (l > idx ? lc[dps][l-1] : 0);
        int c = lc[dps][r-1] - ls;
        if (k <= c) {
            return get(idx+ls, idx+ls+c, k, dps+1, idx);
        } else {
            int sz = 1<<(S-dps-1);
            return get(l+sz-ls, r+sz-(ls+c), k-c, dps+1, idx+sz);
        }
        return -1;
    }
    D get(int l, int r, int k) {
        return x[get(l, r, k, 0, 0)].first;
    }
    //[l, r)??§x?????????????????§?????????????????????????????????lower_bound
    int find(int l, int r, int x, int dps, int idx) {
        if (r <= l) return 1;
        if (dps == S) {
            return (x <= l) ? 1 : 2;
        }
        int ls = (l > idx ? lc[dps][l-1] : 0);
        int c = lc[dps][r-1] - ls;
        int sz = 1<<(S-dps-1);
        int md = idx+sz;
        if (x <= md) {
            return find(idx+ls, idx+ls+c, x, dps+1, idx);
        } else {
            return c+find(l+sz-ls, r+sz-(ls+c), x, dps+1, idx+sz);
        }
    }
    int find(int l, int r, D u) {
        return find(l, r, lower_bound(x, x+n, P(u, -1)) - x, 0, 0);
    }
};

WaveletTree<int, 17> st;
//StarrySkyTree<17> st;
int x[1<<17];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", x+i);
        st.x[i].first = x[i];
//        st.add(i, x[i]);
    }
    st.init(n);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r, e;
        scanf("%d %d %d", &l, &r, &e); l--;
        int mi = min(x[l], x[r-1]);
        int ma = max(x[l], x[r-1]);
        mi -= e;
        ma += e+1;
        int res = st.find(l, r, mi) + ((r-l) - st.find(l, r, ma));
        cout << res << endl;
    }
    return 0;
}    

Measured memory_bytes: 20580
n,k=map(int,input().split())
h=[int(i) for i in input().split()]
k=min(k,n-1)
dp=[0]

for i in range(1,k):
    x=[]
    for j in range(1,i+1):
        x.append(dp[i-j]+abs(h[i-j]-h[i]))
    dp.append(min(x))

for i in range(1,n-k+1):
    m=k+i-1
    x=[]
    for j in range(1,k+1):
        x.append(dp[m-j]+abs(h[m-j]-h[m]))
    dp.append(min(x))

print(dp[-1])


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

/* constant */

const int MAX_N = 16;
const int MAX_BITS = 1 << MAX_N;

const int INF = 1 << 29;

/* typedef */

typedef pair<int,int> pii;

/* global variables */

pii tms[MAX_N][MAX_N + 1];
int dp[MAX_BITS];

/* subroutines */

/* main */

int main() {
  for (;;) {
    int n;
    cin >> n;
    if (n == 0) break;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= n; j++) {
	cin >> tms[i][j].first;
	tms[i][j].second = j - 1;
      }
      sort(tms[i], tms[i] + (n + 1));
    }

    int max_bits = 1 << n;
    
    for (int bits = 0; bits < max_bits; bits++) dp[bits] = INF;
    dp[0] = 0;

    for (int bits = 0; bits < max_bits; bits++)
      if (dp[bits] < INF)
	for (int i = 0; i < n; i++) {
	  int bits0 = bits | (1 << i);
	  if (bits0 == bits) continue;

	  for (int j = 0; j <= n; j++) {
	    pii& tm = tms[i][j];
	    int k = tm.second;
	    if (k < 0 || bits & (1 << k)) {
	      int d = dp[bits] + tm.first;
	      if (dp[bits0] > d) dp[bits0] = d;
	      break;
	    }
	  }
	}

    cout << dp[max_bits - 1] << endl;
  }

  return 0;
}

Measured memory_bytes: 1420
#include <cstdio>
#include <algorithm>
using namespace std;
int n,w,i,x,y,q,j,k,q1,nr[7],a[7][104];
long long Max,v,s[7][104];
int main()
{
    scanf ("%d %d", &n, &w);
    for (i=1;i<=n;i++)
    {
        scanf ("%d %d", &x, &y);
        if (i==1)
            q=x;
        nr[x-q]++;
        a[x-q][nr[x-q]]=y;
    }
    for (i=0;i<=3;i++)
    {
        sort(a[i]+1,a[i]+nr[i]+1);
        reverse(a[i]+1,a[i]+nr[i]+1);
        s[i][0]=0LL;
        for (j=1;j<=nr[i];j++)
            s[i][j]=(0LL)+s[i][j-1]+a[i][j];
    }
    Max=0LL;
    for (i=0;i<=(w/q) && i<=nr[0];i++)
    {
        for (j=0;j<=(w-i*q)/(q+1) && j<=nr[1];j++)
        for (k=0;k<=(w-i*q-j*(q+1))/(q+2) && k<=nr[2];k++)
        {
            q1=(w-i*q-j*(q+1)-k*(q+2))/(q+3);
            if (q1>nr[3])
                q1=nr[3];
            v=(0LL)+s[0][i]+s[1][j]+s[2][k]+s[3][q1];
            if (v>Max)
                Max=(0LL)+v;
        }
    }
    printf ("%lld", Max);
    return 0;
}


Measured memory_bytes: 128
N, x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
count = 0
for i in range(N):
    ai = a[i]
    if i == N - 1:
        if ai == x:
            count += 1
    else:
        if ai <= x:
            count += 1
            x -= ai
        else:
            break
print(count)

Measured memory_bytes: 3060
#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef unsigned long long ul;
typedef long long ll;
typedef pair<ul, ul> P;
map<int, int> dp;
#define REP(i, n) for (ul i = 0; i < n; i++)
void divisor(const ul target, vector<ul>& div, ul num) {
  for (ul i = 1; i <= num; ++i) {
    if (target % i == 0) {
      // div.emplace_back(i);
      if (target / i != i) div.emplace_back(target / i);
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ul N;
  cin >> N;
  vector<ul> div;
  ul div_size = ul(sqrt(N));
  div.reserve(div_size);
  divisor(N, div, div_size);

  sort(div.begin(), div.end());
  ul ans = 0;
  for (auto& tmp : div) {
    if (N % (tmp - 1) != 0) ans += tmp - 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 888
S = input()
LEFT= int(S[:2])
RIGHT = int(S[2:])

left_m = False
right_m = False

if 1 <= LEFT <= 12:
    left_m = True
    
if 1<= RIGHT <= 12:
    right_m = True

if left_m == True and right_m == True:
    print('AMBIGUOUS')
elif left_m == True and right_m == False:
    print('MMYY')
elif left_m == False and right_m == True:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 3064
/*
    Author A.G.Maruf
    5 th seme :P
    code written 08:35PM; 07/13/2018
*/
#include <bits/stdc++.h>
#define gc              getchar
#define pc              putchar
#define pb              push_back
#define Sort_arr(n,x)   sort(n,n+x);
#define SortS(s)        sort(s.begin(), s.end());
#define SortRS(s)       sort(s.rbegin(), s.rend());
#define all(s)          s.begin(), s.end()
#define GCin(a)         getline(cin,a);
#define Sz(a)           a.size()
#define arr_rev(n)      sort(n.begin(), n.end(), greater<int>());
#define Gin(a)          getline(cin,a);
#define input(a)        cin>>a;
#define Sz(a)           a.size()
#define input2(a,b)     cin>>a>>b;
#define input3(a,b,c)   cin>>a>>b>>c;
#define input4(a,b,c,d) cin>>a>>b>>c>>d;
#define rep(n)          for(int i=1;i<n;i++)
#define Fast_read       ios_base::sync_with_stdio(false);
#define Unique(n)       sort(Search(n)),n.erase(unique(Search(n)),n.end());
#define PI              3.1415926535897932384626433832795l
#define Ignore          cin.ignore();
#define out(n)          cout<<n<<endl;
#define mem(n,i)        memset(n,i,sizeof n);
#define square(n)       (n*n)
#define cube(n)         (n*n*n)
#define F               first
#define S               second
#define mxin            -INFINITY
#define mnin            INFINITY
#define el              <<endl
using namespace std;

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

const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
int main (){
    int a,b,c;
    cin>>a>>b>>c;
    int mx,mn;
    mx=max(a,b);
    mx=max(mx,c);
    mn=min(a,b);
    mn=min(mn,c);
    cout<<mx-mn<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>

using namespace std;

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

int main() {
    int h, w, d;
    cin >> h >> w >> d;

    int a;
    array<array<int, 2>, 90001> xy;
    rep(i, h) {
        rep(j, w) {
            cin >> a;
            xy[a] = {i, j};
        }
    } 

    array<long, 90001> memo {0};
    int j;
    rep(i, h * w) {
        j = i + 1;
        if(j <= d) {
            memo[j] = 0;
        } else {
            memo[j] = memo[j-d] + abs(xy[j][0] - xy[j-d][0]) + abs(xy[j][1] - xy[j-d][1]);
        }
    }

    int q, l, r;
    cin >> q;

    rep(i, q) {
        cin >> l >> r;
        cout << memo[r] - memo[l] << endl;
    }
}

Measured memory_bytes: 4600
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,k;
void copy(ll *arr1,ll *arr2){
    arr2[0]=0;
    for(int i=0;i<=100000;i++)arr1[i]=arr2[i];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    ll dp1[100001],dp2[100001];
    set <int> s;
    s.insert(0);
    dp1[0]=0;
    for(int i=1;i<=100000;i++)dp1[i]=-1;
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        bool visit[100001];
        memset(visit,false,sizeof(visit));
        for(int j=0;j<=100000;j++){
            if(x+dp1[j]>k){
                if(visit[j]==false)dp2[j]=dp1[j];
                continue;
            }
            if(j!=0&&dp1[j]==-1){
                if(visit[j]==false)dp2[j]=dp1[j];
                continue;
            }
            visit[j+y]=true;
            s.insert(j+y);
            if(dp1[j+y]==-1)dp1[j+y]=100000000000000000;
            dp2[j+y]=min(dp1[j+y],dp1[j]+x);
        }
        copy(dp1,dp2);
    }
    cout<<*s.rbegin();
}

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

int main(){
  int H , W ; 
  cin >> H >> W ; 
  vector<vector<char>> a(H , vector<char>(W));
  vector<int> T(H) ,Y(W)  ; 
  
  for(int i = 0 ; i < H ; i++){
    for(int j = 0 ; j < W ; j++){
      cin >> a.at(i).at(j) ; 
      if(a.at(i).at(j) == '#'){
        T.at(i)++ ;
        Y.at(j)++ ; 
      }
    }
  }
  
  for(int i = 0 ; i < H ; i++){
    int cnt = 0 ; 
    
    for(int j = 0 ; j < W ; j++){
      if(T.at(i) != 0 && Y.at(j)!=0){
        cout << a.at(i).at(j) ;
        cnt++ ; 
      }
      
    }
          if(cnt > 0 )cout << endl ; 

  }
  
}

Measured memory_bytes: 3608
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("")
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int a, b; cin >> a >> b;
	Cout2(a*b, (a + b) * 2);
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
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 qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    int N, M, X;
    cin >> N >> M >> X;
    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M));
    ll ans = INFL;
    rep(i,N) {
        cin >> C[i];
        rep(j,M) {
            cin >> A[i][j];
        }
    }
    for(int s = 0; s < 1 << N; s++) {
        vector<int> B(M, 0);
        ll cost = 0;
        bool ok = true;
        rep(i,N) {
            if((s >> i) & 1) {
                cost += C[i];
                rep(j,M) B[j] += A[i][j];
            }
        }
        rep(i,M) if(B[i] < X) ok = false;
        if(ok) chmin(ans, cost);
    }
    cout << (ans == INFL ? -1 : ans) << endl;
    return 0;
}


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

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


string alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";

void solve() {
	unsigned n; cin >> n;
	string s; cin >> s;

	rep(i, s.size()) {
		unsigned p = 0;
		while (alp[p] != s[i]) p++;
		s[i] = alp[p + n];
	}

	cout << s << endl;
}

int main() {

	solve();

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <bitset>
#include <map>
#include <math.h>
#include <utility>

using namespace std;

int main(){

    long long N;
    cin >> N;

    long long ans = N - 1;
    long long j;
    for (long long i = 2; i*i <= N; i++){
        if (N % i == 0){
            j = N / i;
            ans = min(ans, i + j - 2);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string S;
	cin>>S;
	bool flag=true;
	for(int i=0;i<S.size();i++){
		if((i+1)%2!=0){
			if(S[i]=='L'){
				flag=false;
				break;
			}
		}
		else{
			if(S[i]=='R'){
				flag=false;
				break;
			}
		}
	}
	if(flag)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <fstream>
#include <sstream>
#include <unordered_map>
using namespace std;

const unsigned long long BASE = (unsigned long long)(1e9 + 7);

#define FROM_0(i, n) for(int i = 0; i < (n); i++)
#define FROM_S(i, s, e) for(int i = (s); i < (e); i++)
#define ITER_BEGIN_END(iter, vec) for(auto iter = vec.begin(); iter < vec.end(); iter++)

int main()
{
    int n;
    cin >> n;
    unsigned long long m = 0, sum = 0;
    FROM_0(i, n)
    {
        int a;
        cin >> a;
        if (a < m)
        {
            sum += m - a;
        }
        else
        {
            m = a;
        }
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 3620
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int n,s;
struct que
{
	int x;
	long long p;
}a[100005];
long long calc(int l,int r,int last)
{
	if(a[l].x>=s) return a[r].x-s;
	if(a[r].x<=s) return s-a[l].x;
	if(a[l].p>=a[r].p){a[l].p+=a[r].p;return calc(l,r-1,l)+((last==r)?a[r].x-a[l].x:0);}
	else {a[r].p+=a[l].p;return calc(l+1,r,r)+((last==l)?a[r].x-a[l].x:0);}
}
int main()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++) scanf("%d%lld",&a[i].x,&a[i].p);
	printf("%lld\n",calc(1,n,a[1].p<a[n].p?1:n));
}

Measured memory_bytes: 9000
#include <iostream>
 
  using namespace std;
  
 int main (void){
     int N,M;
     int total;
     cin >> N >> M;
   
    total = 0;
    for(int i=0;i < M;i++){
    int a;
      cin >> a;
      total += a;
    }
  
    if(total <= N){
      cout << N - total;
    }else{
      cout << -1;
    }
  
    return 0;
  }



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main(){
  int k; cin >> k;
  int n = 2 * ((k + 3)/4);
	if(k == 1){
		cout << 1 << endl;
		cout << 1 << endl;
		return 0;
	}
  cout << n << endl;
	vector<vector<int> > res(n, vector<int>(n, 0));
	int mx = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      int c = (i + j)%n;
      if(i&1) c += n;
	res[i][j] = c + 1;
    	mx = max(mx, c + 1);
	}
  }
	while(mx != k){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(res[i][j] == mx) res[i][j] -= n;
			}
		}
		mx--;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << res[i][j] << " \n"[j+1 == n];
		}
	}
  return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
#define INF 100000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 100005;
const int MOD = 1000000007;
int main(){
    int a,b;
    cin>>a>>b;
    OUT((a*3+b)/2);
    return 0;
}

Measured memory_bytes: 256
def f(a):
	q=a[:n];s=sum(q);heapify(q);yield s
	for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;n,*a=map(int,open(0).read().split());print(max(map(sum,zip(f(a),list(f([-e for e in a[::-1]]))[::-1]))))

Measured memory_bytes: 36308
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<int,int>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
int main(){
 ll n;
 cin>>n;
 V<int> ans;
 if(n==0){cout<<0<<endl;return 0;}
 while(n!=0){
     ans.push_back(abs(n%2));
     if(n<0)n=(n-1)/(-2);
      else n/=(-2);
 }
 reverse(all(ans));
 for(int v:ans){
     cout<<v;
 }
 cout<<endl;
}

Measured memory_bytes: 256
import sys
import math
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def calc_combi(n, m, mod=1000000007):
    """ nCmの組み合わせ数を数える """
    if n - m < m:
        return calc_combi(n, n - m)

    ans_mull, ans_div = 1, 1
    for i in range(m):
        ans_mull *= (n - i)
        ans_div *= (i + 1)
        ans_mull %= mod
        ans_div %= mod
    ans = ans_mull * pow(ans_div, mod - 2, mod) % mod
    return ans

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, M = map(int, input().rstrip().split())
    mod = 1000000007

    ans = 1
    for i in range(2, math.ceil(math.sqrt(M))):
        if M % i == 0:
            count = 0
            while M % i == 0:
                M /= i
                count += 1
            ans *= calc_combi(count + N - 1, N - 1, mod)
            ans %= mod
    if M != 1:
        ans *= calc_combi(N, 1, mod)
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

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


int main(){
  int i,k;
  long long n;
  cin >> n;
  vector<int> d(n);
  for(i=0;i<n;++i){
    cin >> d[i];
  }
  sort(d.begin(),d.end());
  if(d[n/2]==d[(n/2)-1]){
    k=0;
  }else{
    k=d[(n/2)]-d[(n/2)-1];
  }
  cout << k << endl;
  return 0;
}


Measured memory_bytes: 640