akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define stop exit(0)
#define pb push_back
#define skip continue
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    vector<long long>v,u;
    pair<string, long long> n;
    set<long long> y;
    long long a,b,c,d=0,e=0,i,f=0,g=0,j,k=1,l=0,r=0,z,m,h[27],p[27];
    string t,s,x,q;
    double w;
    cin>>a;
    cout<<a+a*a+a*a*a;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 105

int N;

struct Point{

	void set(int arg_x,int arg_y){
		x = arg_x;
		y = arg_y;
	}
	int x,y;
};

struct Edge{
	Edge(int arg_left,int arg_right){
		left = arg_left;
		right = arg_right;
	}
	bool operator<(const struct Edge &arg) const{
		if(left != arg.left){

			return left < arg.left;

		}else{
			return right < arg.right;
		}
	}
	int left,right;
};

//http://www.ipsj.or.jp/07editj/promenade/4501.pdf

Point point[NUM];

void compute_x(int i,int y,int *xl,int *xr){

	int den,num,w;

	den =  point[i+1].y-point[i].y;
	num = (y-point[i].y)*(point[i+1].x-point[i].x);
	w = point[i].x+num/den;

	if(num%den == 0){
		*xl = w;
		*xr = w;
	}
	else if((num%den)*den < 0){
		*xl = w-1;
		*xr = w;
	}else{
		*xl = w;
		*xr = w+1;
	}
}

int calc_S(int under_y){

	vector<Edge> V;
	int xla,xra,xlb,xrb;

	//under_y～under_y+1を走る辺を求める
	for(int i = 0; i < N; i++){
		if((point[i].y <= under_y && point[i+1].y <= under_y) ||
			(point[i].y >= under_y+1 && point[i+1].y >= under_y+1))continue;

		compute_x(i,under_y,&xla,&xra); //y == yとの交点
		compute_x(i,under_y+1,&xlb,&xrb); //y == y+1との交点

		V.push_back(Edge(min(xla,xlb),max(xra,xrb)));
	}

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

	int prev = -2000,ret = 0;

	for(int i = 0; i < V.size(); i += 2){
		ret += V[i+1].right-max(V[i].left,prev);
		prev = V[i+1].right;
	}

	return ret;
}

void func(){

	int y_min = BIG_NUM,y_max = -BIG_NUM;

	for(int i = 0; i < N; i++){

		scanf("%d %d",&point[i].x,&point[i].y);

		//入力のついでにy座標の最大値と最小値を求める
		y_min = min(y_min,point[i].y);
		y_max = max(y_max,point[i].y);
	}
	point[N] = point[0];

	int ans = 0;

	for(int under_y = y_min; under_y <= y_max-1; under_y++){

		ans += calc_S(under_y);
	}

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

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}



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

int x;

int main(){
	scanf("%d",&x);
	for(int i=1;i<=x;i++){
		int tmp = x-(i*100);
		if(tmp < 0) break;
		if(tmp <= i*5){
			printf("1\n");
			return 0;
		}
	}
	printf("0\n");
	return 0;
}


Measured memory_bytes: 384
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(), B = sc.nextInt();
        long ans = 0;
        for (int n = A; n <= B; n++) {
            int d5 = (n / 10000) % 10;
            int d4 = (n /  1000) % 10;
            int d2 = (n /    10) % 10;
            int d1 =  n          % 10;
            if (d5 == d1 && d4 == d2) ans += 1;
        }
        System.out.println(ans);
        sc.close();
    }
}


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

int main() {
    string s[4] = {"Sunny", "Cloudy", "Rainy", "Sunny"};
    string S;
    cin >> S;
    rep(i, 3) if (S == s[i]) {
        cout << s[i+1];
        return 0;
    }
}

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

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

typedef long long LL;

struct a{
  LL x;
  int num;
  bool operator<(const struct a & right) const{
    return x<right.x;
  }
};

int main(){
  int n,K;
  cin >> n >> K;
  vector<struct a> X(n),Y(n);
  LL x,y;
  for(int i=0;i<n;i++){
    cin >> x >> y;
    X[i]={x,i};
    Y[i]={y,i};
  }
  sort(X.begin(),X.end());
  sort(Y.begin(),Y.end());
  vector<int> tox(n),toy(n);
  for(int i=0;i<n;i++){
    tox[X[i].num]=i;
    toy[Y[i].num]=i;
  }
  vector<vector<int>> field(n+1,vector<int>(n+1,0));
  for(int i=0;i<n;i++){
    field[toy[i]+1][tox[i]+1]=1;
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      field[i][j]=field[i][j]+field[i-1][j]+field[i][j-1]-field[i-1][j-1];
    }
  }
  // for(int i=0;i<=n;i++){
  //   for(int j=0;j<=n;j++){
  //     cout << field[i][j];
  //   }
  //   cout << endl;
  // }
  LL ans=4000000000000000000;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      for(int k=i+1;k<=n;k++){
        for(int l=j+1;l<=n;l++){
          // cout << i << j << k << l << " " << field[k][l]-field[i-1][l]-field[k][j-1]+field[i-1][j-1]<< endl;
          if(field[k][l]-field[i-1][l]-field[k][j-1]+field[i-1][j-1]>=K){
            // cout << i << j << k << l << " " << endl;
            ans=min(ans,(X[l-1].x-X[j-1].x)*(Y[k-1].x-Y[i-1].x));
          }
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
for b, c in BC:
    if b in d:
        total += d[b] * (c-b)
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        d[b] = 0
    print(total)

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;


long long int n,cnt=0,ans=0,a[ohara],b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin>>n;
      rep(i,3*n)cin>>a[i];
      sort(a,a+3*n);
      reverse(a,a+3*n);
      rep(i,3*n){
        if(i%2==1){
        ans+=a[i];
        cnt++;
        }
        if(cnt==n)break;
      }
      Cout(ans);
      
     

       
return 0;
}


Measured memory_bytes: 4352
package main
import "fmt"
import "sort"
func main(){
    // Your code here!
    var n, m int
    fmt.Scan(&n, &m)
    
    t := make([]int, n)
    for i := 0; i < n; i++ {
         fmt.Scan(&t[i])
    }
    
    sort.Sort(sort.Reverse(sort.IntSlice(t)))
    var sum int
    for i := 0; i < len(t); i++{
        sum += t[i]        
    }
    
    for i := 0; i < m; i++{
        if float64(t[i]) < float64((float64(sum))/float64((4*m))){
            fmt.Println("No")
            return
        }
    }
    fmt.Println("Yes")
}


Measured memory_bytes: 512
lines = [];
readline = require("readline");

rl = readline.createInterface({
  input: process.stdin,
  output:process.stdout
});

rl.on('line',function(x){
  lines.push(x);
})

rl.on('close',function(){
  var n = Number(lines[0].split(" ")[0]);
  var a = Number(lines[0].split(" ")[1]);
  var b = Number(lines[0].split(" ")[2]);

  var max = (a < b)? a : b;
  var min = (n < (a+b))? a+b-n : 0;

  console.log(max,min);

})


Measured memory_bytes: 22336
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL =LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}


int main() {
    int n;cin>>n;
    vector<int>L(2*n);cin>>L;
    sort(all(L));
    int ans = 0;
    rep(i,n){
        ans += L[2*i];
    }
    cout<<ans<<endl;
    
    
    return 0;
}








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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;
typedef vector<unordered_map<lli,lli>> graph;

lli n;
vll a;
vll b;
lli ans = 0;

int main(){
  cin >> n;
  a = vll(n);
  for(lli i = 0;i < n;i++) cin >> a[i];
  while(true){
    b = vll(n);
    for(lli i = 0;i < n;i++){
      b[i] = a[i]/n;
      a[i] %= n;
    }
    lli c = accumulate(b.begin(),b.end(),0ll);
    if(c == 0) break;
    ans += c;
    for(lli i = 0;i < n;i++){
      a[i] += c-b[i];
    }
  }
  cout << ans << endl;
  return 0;
}


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

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

    int N = S.size();
    ll ans = 0;
    rep(i, (1 << (N - 1))) {
        ll t = S[0] - '0';
        rep(j, N - 1) {
            if (i & (1 << j)) {
                ans += t;
                t = S[j+1] - '0';
            } else {
                t *= 10;
                t += S[j+1] - '0';
            }
        }
        ans += t;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int w, h, nw, nh;
	int i;
	int n;
	char tile[101][101];
	
	while (1){
		scanf("%d %d", &h, &w);
		
		if (w == 0 && h == 0) break;
		
		for (i = 0; i < h; i++){
			scanf("%s", tile[i]);
		}
		
		nw = nh = n = 0;
		
		while (n < w * h && tile[nh][nw] != '.'){
			if (tile[nh][nw] == '>'){
				nw++;
			} else if (tile[nh][nw] == '<'){
				nw--;
			} else if (tile[nh][nw] == '^'){
				nh--;
			} else if (tile[nh][nw] == 'v'){
				nh++;
			}
			n++;
		}
		
		if (tile[nh][nw] == '.'){
			printf("%d %d\n", nw, nh);
		} else {
			printf("LOOP\n");
		}
	}
	
	return (0);
}

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, R;
    cin >> N >> R;
    cout << R + 100 * max(0, 10 - N) << endl;
    return 0;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int mask = a[0] ^ a[1];
  for (int i = 2; i < n; i+=2) {
    mask ^= (a[i] ^ a[i + 1]);
  }
  for (int i = 0; i< n; ++i) {
    if (i > 0) cout << ' ';
    cout << (mask ^ a[i]);
  }
}


Measured memory_bytes: 3984
n, m = map(int, input().split())
L = []
R = []
for i in range(m):
  t1, t2 = map(int, input().split())
  L.append(t1)
  R.append(t2)

maxl = max(L)
minr = min(R)
ans = minr - maxl + 1

if ans <= 0:
  print(0)
else:
  print(ans)

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

int main() {
	int a, b, sum;
	string s;
	int ans;
	cin >> a >> b;
	s = to_string(a) + to_string(b);
	ans = sqrt(stoi(s));
	sum = stoi(s);
	if (ans*ans != sum) {
		cout << "No";
		return 0;
	}
	cout << "Yes";
}

Measured memory_bytes: 256
N, A, B = map(int, input().split())

if(A==0 & B==0):
  print("0")

else:
  r=N//(A+B)
  s=N%(A+B)
  if(A<s):
    s=A
  if(A!=0):
    t=(A*r)+s
  else:
    t=0
  print(t)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
  int n,t;
  cin>>n>>t;
  int c[1010],a[1010],ans=1010;
  for(int i=0;i<n;i++){
    cin>>c[i]>>a[i];
    if(a[i]<=t){
      if(c[i]<ans)ans=c[i];
    }
  }
  if(ans==1010)cout<<"TLE"<<endl;
  else cout<<ans<<endl;
}

Measured memory_bytes: 256
n=int(input())
a=[int(input()) for i in range(n)]
cnt=0
for i in range(n):
    cnt+=1
    if i==0:
        osu=1
        hikaru=a[0]
    else:
        osu=hikaru
        hikaru=a[osu-1]
    if hikaru==2:
        print(cnt)
        break
else:
    print(-1)

Measured memory_bytes: 12708
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<queue>
#include<functional>
#include<cmath>
#include<map>
#include<tuple>
#include <numeric>
#define rep(i,n) for(int i=0; i<(int)n; i++)//n回繰り返す
#define rrep(i,n)for(int i=n-1;i>=0;i--)
#define REP(i,n) for (int i = 1; i <= (int)n; i++)//i=1からi=nまで
#define RREP(i,n)for(int i=n;i>=1;i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using graph = vector<vector<int>>;
const ll mod = pow(10, 9) + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const double pi = 3.14159265358979323846;
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; }


int main() {
    int N; cin >> N;
    vector<int> A(N);
    rep(i, N) {
        cin >> A[i];
    }
    ll ans = 0;
    rep(i, N) {
         
        if (i != 0) {
            if (A[i] < A[i - 1]) {
                ans += (A[i - 1] - A[i]);
                A[i] = A[i-1];
            }
        }
        
    }
    cout << ans << endl;
}































































Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin >> n;
    vector<int> b(n-1);
    for(int i=0; i<n-1; i++){
        cin >> b.at(i);
    }

    vector<int> a(n);
    a.at(0) = b.at(0);
    a.at(n-1) = b.at(n-2);

    for(int i=0; i<n-2; i++){
        a.at(i+1) = min(b.at(i), b.at(i+1));
    }

    int sum =0;
    for(int i=0; i<n; i++){
        sum += a.at(i);
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 20;
const int INF = 1 << 28;
 
int n, memo[10], ans;
char table[5][N], tmp[5][N*20];
 
void rec(int t, int c){
  if(t >= 10) ans = min(ans, c + n);
  else{
    if(memo[t] < c) return;
    for(int nc=c;nc-c<=n;nc++){
      int f = 1;
      for(int i=0;i<5;i++){
        for(int j=0;j<n;j++){
          if(table[i][j] == 'X' && tmp[i][nc+j] == 'X') f = 0;
        }
      }
      if(f){
        for(int i=0;i<5;i++){
          for(int j=0;j<n;j++){
            if(table[i][j] == 'X') tmp[i][nc+j] = 'X';
          }
        }
        rec(t+1, nc);
        for(int i=0;i<5;i++){
          for(int j=0;j<n;j++){
            if(table[i][j] == 'X') tmp[i][nc+j] = '.';
          }
        }
        memo[t] = min(memo[t], nc);
      }
    }
  }
}
 
main(){
  while(cin >> n && n){
    for(int i=0;i<5;i++){
      for(int j=0;j<n;j++){
        cin >> table[i][j];
      }
    }
    fill(tmp[0], tmp[5], '.');
    fill(memo, memo+10, INF);
    ans = INF;
    rec(0, 0);
    cout << ans << endl;
  }
}

Measured memory_bytes: 1160
import sys

input = sys.stdin.readline

h, w = map(int, input().split())
grid = []
for i in range(h):
    row = list(input().strip())
    grid.append(row)

dp = [[0 for _ in range(w)] for _ in range(h)]

dp[0][0] = 1
dirx = [0, 1]
diry = [1, 0]
for i in range(h):
    for j in range(w):

        for k in range(2):
            r = i + dirx[k]
            c = j + diry[k]

            if r < h and c < w and grid[r][c] == '.':
                dp[r][c] += dp[i][j]
                dp[r][c] %= int(1e9+7)

print(dp[h-1][w-1])


Measured memory_bytes: 90716
N = int(input())
T = []
XY = []
ans = "Yes"

for i in range(N):
  t,x,y = map(int,input().split())
  T.append(t)
  XY.append([x,y])

if T[0]>=abs(XY[0][0])+abs(XY[0][1]) and T[0]%2==(abs(XY[0][0])+abs(XY[0][1]))%2:
  None
else:
  ans = "No"

for i in range(1,N):
  dT=T[i]-T[i-1]
  dX=abs(XY[i][0]-XY[i-1][0])
  dY=abs(XY[i][1]-XY[i-1][1])
  if dT >= dX+dY and dT%2 == (dX+dY)%2:
    None
  else:
    ans = "No"

print(ans)

Measured memory_bytes: 24572
#include<iostream>
#include<algorithm>
#include<cstdint>
#include<cstring>
using namespace std;

const int MAX = 100000;

/**
 * 転倒数導出アルゴリズム
 */
int64_t invNum(int *a, int l, int r) {
	int64_t ret = 0;
	int n = r - l, m = l + (n >> 1);
	if (n <= 1) return ret;
	ret += invNum(a, l, m);
	ret += invNum(a, m, r);
	int *tmp = new int[n];
	for (int i = 0, j = m;i < n;++ i) {
		if (a[l] <= a[j]) {
			tmp[i] = a[l];
			++ l;
			if (l >= m) {
				memcpy(tmp + i + 1, a + j, sizeof(int) * (n - i - 1));
				break;
			}
		} else {
			tmp[i] = a[j];
			ret += m - l;
			++ j;
			if (j >= r) {
				memcpy(tmp + i + 1, a + l, sizeof(int) * (n - i - 1));
				break;
			}
		}
	}
	memcpy(a + r - n, tmp, sizeof(int) * n);
	return ret;
}

bool check(int x, int *a, int N) {
	int *b = new int[N + 1];
	b[0] = 0;
	for (int i = 0;i < N;++ i) b[i + 1] = b[i] + (a[i] < x ? -1 : 1);
	int64_t ret = ((int64_t)N * (N + 1) >> 1) - invNum(b, 0, N + 1);
	return ret >= (int64_t)N * (N + 1) >> 2;
}

int binarySearch(int *a, int N) {
	int min = 0, max = N;
	int b[MAX];
	memcpy(b, a, sizeof(int) * N);
	sort(b, b+N);
	for (int mid = max >> 1;max - min > 1;mid = min + (max - min >> 1)) {
		if (check(b[mid], a, N)) min = mid;
		else max = mid;
	}
	return b[min];
}
int main() {
	int N, a[MAX];
	cin >> N;
	for (int i = 0;i < N;++ i) cin >> a[i];
	cout << binarySearch(a, N);
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

おいまったく解けねーぞ！
解説AC
*/

Measured memory_bytes: 149504
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

const int mod = 1000000007;

struct mint {
    long long x;
    mint(long long x=0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
bool operator==(const mint& a, const mint& b) { return a.x == b.x;}

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

    string s;
    cin >> s;
    int d;
    cin >> d;
    int n = sz(s);
    auto dp = make_vec<mint>(n+1, d, 2);
    dp[0][0][0] = 1;
    rep(i, n) {
        rep(j, d) {
            rep(k, 2) {
                for (int x = 0; x <= (k ? 9 : s[i] - '0'); ++x) {
                    dp[i+1][(j+x)%d][k||x<s[i]-'0'] += dp[i][j][k];
                }
            }
        }
    }
    mint ans = dp[n][0][0] + dp[n][0][1] - mint(1);
    cout << ans << endl;
}


Measured memory_bytes: 58476
#include<iostream>
using namespace std;
int a[4][4];
int main(){
    for(int i = 1; i<= 3;i++) {
        for(int j = 1;j <= 3;j ++) {
            cin>>a[i][j];
        }
    }
    for(int k = -1000;k <= 1000;k++) {
        int a2,a3,b1,b2,b3;
        int a1 = k;
        b1 = a[1][1] - k;
        b2 = a[1][2] - k;
        b3 = a[1][3] - k;
        a2 = a[2][1] - b1;
        a3 = a[3][1] - b1;
        bool flg = false;
        if(a[2][2] != a2 + b2) flg = true;
        if(a[2][3] != a2 + b3) flg = true;
        if(a[3][2] != a3 + b2) flg = true;
        if(a[3][3] != a3 + b3) flg = true;
        if(!flg) {
            cout<<"Yes"<<endl;return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

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

int main(void)
{
    ll h, w;
    cin >> h >> w;
    // as bishop can not move at all
    if (h == 1 || w == 1) cout << 1 << endl;
    else cout << (h * w + 1) / 2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
ll sm[100010];
map<ll, int> mp;
int main(){
  ll n, m, x;
  while(cin>>n>>m){
    mp.clear();
    ++mp[0];
    ll ans=0;
    for(int i=0; i<n; ++i){
        cin>>x;
        if(i==0)
            sm[i]=x%m;
        else
            sm[i]=(sm[i-1]+x)%m;
        sm[i]%=m;
        ans+=mp[sm[i]];
        ++mp[sm[i]];
    }
    cout<<ans<<endl;
  }
  return 0;
}




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

using namespace std;


int main() {
  
    long int n;
    scanf("%ld",&n);
    string s[n];
    long int i,max=0,cnt=0;
    
    for(i=0;i<n;++i)
        cin>>s[i];
        
    sort(s,s+n);
    
    for(i=0;i<n-1;++i)
      {
          if(s[i]==s[i+1])
             cnt++;
             
          else
            {
                if(max<cnt)
                   max=cnt;
                   
                 cnt=0;  
            }
      }
      if(max<cnt)
         max=cnt;
         
         
      
      cnt=0;
       for(i=0;i<n;++i)
      {
          if(i!=n-1 && s[i]==s[i+1])
             cnt++;
             
          else
            {
                if(max==cnt)
                   cout<<s[i]<<endl;
                   
                 cnt=0;  
            }
      }
    
    
	return 0;
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long int ll;

ll mpow(ll m,ll t)
{
	if(t==0) return 1;
	ll ret=mpow(m,t/2);
	ret=ret*ret%MOD;
	if(t%2==1) ret=ret*m%MOD;
	return ret;
}
ll gcd(ll x,ll y)
{
	if(x==0) return y;
	return gcd(y%x,x);
}
ll solve(ll W,ll H)
{
	ll g=gcd(H,W);
	return (mpow(2,W)+mpow(2,H)-1+MOD+mpow(2,g)-2+MOD)%MOD;
}
int main()
{
	ll W,H,T;
	scanf("%lld %lld %lld",&W,&H,&T);
	ll gw=gcd(T,W),gh=gcd(T,H);
	printf("%lld\n",mpow(solve(W/gw,H/gh),gw*gh));
	return 0;
}

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

int main() {
	int n, q, k;
	cin >> n;
	vector<vector<pair<int, int>>> v(n);
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	cin >> q >> k;
	vector<int64_t> d(n, -1);
	stack<int> s;
	d[k - 1] = 0;
	s.push(k - 1);
	while (!s.empty()) {
		int i = s.top();
		s.pop();
		for (auto it = begin(v[i]); it != end(v[i]); it++) {
			if (d[it->first] == -1) {
				d[it->first] = d[i] + it->second;
				s.push(it->first);
			}
		}
	}
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		cout << d[x] + d[y] << endl;
	}
	return 0;
}


Measured memory_bytes: 8820
import sys
N = int(input())
D = []
for i in range(N):
    D.append(input().split())
cnt = 0
for i in range(N):
    if D[i][0] == D[i][1]:
        cnt += 1
        if cnt == 3:
            print("Yes")
            sys.exit()
    else:
        cnt = 0
print("No")

Measured memory_bytes: 62180
import sys
X, N = map(int, input().split())
if N == 0:
    print(X)
    sys.exit()
p = list(map(int, input().split()))

forbid = [True]*102

for i in range(len(p)):
    if forbid[p[i]]:
        forbid[p[i]] = False
        
pp = []

for i in range(len(forbid)):
    if forbid[i]:
        pp.append(i-X)

num = pp[len(pp)-1]        
for i in range(len(pp)-1,-1,-1):
    if abs(num) >= abs(pp[i]):
        num = pp[i]
        
print(num+X)


Measured memory_bytes: 9204
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

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

	Int r;
	cin >> r;

	Int D;
	cin >> D;

	Int x2000;
	cin >> x2000;

	Int temp=x2000;
	for (int i = 0; i < 10; i++) {
		temp = r * temp - D;
		cout << temp << "\n";
	}

}


Measured memory_bytes: 256
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

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

using namespace __gnu_pbds;
using namespace std;

#define deb(x) cout << #x << " is " << x << "\n";
#define int long long
#define mod 1000000007

const double PI = 2 * acos(0.0);
const long long INF = 1e18L + 5;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve() {
	int n;
	cin >> n;
	vector<double> p(n);
	for(int i = 0; i < n; i++)
		cin >> p[i];
	vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0.0));
	dp[0][0] = 1.0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= i; j++) {
			if(j == 0) {
				dp[i][j] = dp[i - 1][j] * (1.0 - p[i - 1]);
			}
			else {
				dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1];
			}
		}
	}
	double ans = 0.0;
	for(int i = (n + 1) / 2; i <= n; i++)
		ans += dp[n][i];
	cout << fixed << setprecision(10) << ans;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	return 0;
}


Measured memory_bytes: 70784
import java.util.Scanner;
public class Main{
	public static void main(String args[]){
    	Scanner sc=new Scanner(System.in);
      	int n=sc.nextInt();
      	int arr[]=new int[n];
      	for(int i=0;i<n;i++) arr[i]=sc.nextInt();
      	int dp[]=new int[n];
      	dp[0]=0;
      	dp[1]=Math.abs(arr[1]-arr[0]);
      	for(int i=2;i<n;i++){
        	dp[i]=Math.min(dp[i-1]+Math.abs(arr[i]-arr[i-1]),dp[i-2]+Math.abs(arr[i]-arr[i-2]));
        }
      	System.out.println(dp[n-1]);
    }
}

Measured memory_bytes: 48692
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
	int a,b;
  	vector<int> c;

      cin >> a >> b;
    c.push_back(a-b);
    c.push_back(a+b);
    c.push_back(a*b);

    sort(c.begin(), c.end());
    cout << c[2] << endl;
    return 0;
}
  	

Measured memory_bytes: 256
import java.util.Scanner;
public class Main
{
	public static void main(String arg[])
	{
		Scanner in = new Scanner(System.in);
		int a[][]=new int[5][5];
		int n=in.nextInt();
		while(n-->0)
		{
			for(int i=0; i<5; i++)
				for(int j=0; j<5; j++)
					a[i][j]=in.nextInt();
			int max=0;
			for(int i=0; i<5; i++)
			{
				for(int j=0; j<5; j++) //ここまで始点決定の記述
				{
					for(int h=i;h<5;h++)
					{
						for(int w=j;w<5;w++)
						{
							boolean flag =true;
							int co=0;
							for(int x=i;x<=h;x++)
								for(int y=j;y<=w;y++)
								{
									if(a[x][y]==0)
										flag = false;
									else
										co++;
								}
							if(flag)
								max=Math.max(max, co);
						}
					}
				}
			}
			System.out.println(max);
		}
	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stdint.h>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int ,int> pp;
typedef long long ll;
const ll MOD = 1000000007;

int main(){
    ll n;
    ll a;
    ll sum = 0;
    cin>>n;
    vector<ll> v;
    for(int i = 0; i < n; i++){
        cin>>a;
        sum += a;
        v.push_back(a);
    }
    ll b = 0;
    ll i;
    for(i = 0; i < n; i++){
        b += v[i];
        if(2 * b >= sum) break;
    }
    ll c = b - v[i];
    ll ans = abs(sum - 2 * b);
    if(ans > abs(sum - 2 * c)) ans = abs(sum - 2 * c);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2420
A,B,N = map(int,input().split())

if N < B:
    print((A*N)//B)
elif N == B:
    NN = N-1
    print((A*NN)//B)
else:
    
    wN = N % B
    wwN = B * wN -1
    sahen1 = (A*wwN)//B
    uhen1 = A * (wwN//B)
    kouho1 = sahen1 - uhen1

    sahen2 = (A*N)//B
    uhen2 = A * (N//B)
    kouho2 = sahen2 - uhen2
    print(max(kouho1,kouho2))
        

Measured memory_bytes: 61928
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;


int main(){
long long X,Y,A,B,C,p,tmp;
cin>>X>>Y>>A>>B>>C;
long long ans=0;
long long mark=0;
//mark red 1,green 2, clear 3
vector<long long> red,green,clear;
for(long long i=0;i<A;++i){
    cin>>p;
    red.push_back(p);
}
red.push_back(0);
std::sort(red.begin(), red.end(), std::greater<long long>() );
for(long long i=0;i<B;++i){
    cin>>p;
    green.push_back(p);
}
green.push_back(0);
std::sort(green.begin(), green.end(), std::greater<long long>() );
for(long long i=0;i<C;++i){
    cin>>p;
    clear.push_back(p);
}
clear.push_back(0);
std::sort(clear.begin(), clear.end(), std::greater<long long>() );
//red,green,clearが何番までいったか？
long long mark_r=0;
long long mark_g=0;
long long mark_c=0;
for(long long i=0;i<X+Y;++i){
    mark=3;
    tmp=clear[mark_c];
    //赤を使ってOK
    if(mark_r<X && tmp<red[mark_r]){
        mark=1;
        tmp=red[mark_r];
    }
    if(mark_g<Y && tmp<green[mark_g]){
        mark=2;
        tmp=green[mark_g];
    }
    ans+=tmp;
    if(mark==1){
        mark_r+=1;
    }
    if(mark==2){
        mark_g+=1;
    }
    if(mark==3){
        mark_c+=1;
    }
}
cout<<ans<<"\n";
return 0;
}


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int n,a,b,ans=0,tmp;
    cin >> n >> a >> b;
    rep(i,n){
        tmp=(i+1)/10000+((i+1)/1000)%10+((i+1)/100)%10+((i+1)/10)%10+(i+1)%10;
        if(tmp>=a&&tmp<=b)ans+=i+1;
    }
    cout << ans << endl;
}


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

const int N=20,M=2e3;

int n,m,k,ans=INT_MAX;
char a[N][M];

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<n;i++) scanf(" %s",a[i]);

	for(int mask=0;mask<(1<<(n-1));mask++)
	{
		int rows=__builtin_popcount(mask)+1,cuts=rows-1;
		vector <int> dp(rows,0);
		bool invalid=false;
		for(int j=0;j<m and not invalid;j++)
		{
			bool ok=true;
			for(int i=0,ptr=0;i<n and ok;i++)
			{
				if(a[i][j]=='1') dp[ptr]++;
				if(dp[ptr]>k) ok=false;
				if(mask&(1<<i)) ptr++;
			}

			if(not ok)
			{
				cuts++;
				for(int i=0;i<rows;i++) dp[i]=0;
				ok=true;
				for(int i=0,ptr=0;i<n and ok;i++)
				{
					if(a[i][j]=='1') dp[ptr]++;
					if(dp[ptr]>k) ok=false;
					if(mask&(1<<i)) ptr++;
				}
				if(not ok)
				{
					invalid=true;
					break;
				}
			}
		}

		if(not invalid) ans=min(ans,cuts);
	}

	printf("%d",ans);
}

Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
  
signed main(){
  int n;
  cin >> n;
  int a[n-1],b[n-1];
  for(int i=0;i<n-1;i++){
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  int c[n];
  for(int i=0;i<n;i++) cin >> c[i];
  sort(c,c+n);
  reverse(c,c+n);
  int ans=0;
  for(int i=1;i<n;i++){
    ans+=c[i];
  }
  cout << ans << endl;
  int ret[n]={};
  int k=1;
  ret[0]=c[0];
  while(k<n){
    for(int i=0;i<n-1;i++){
      if(ret[a[i]]>0&&ret[b[i]]==0){
        ret[b[i]]=c[k];
        k++;
      }
      if(ret[b[i]]>0&&ret[a[i]]==0){
        ret[a[i]]=c[k];
        k++;
      }
    }
  }
  for(int i=0;i<n;i++){
    cout << ret[i] << " ";
  }
  cout << endl;
}


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

  

int main() {
  string S;
  cin>>S;
  
  string A=S;
  reverse(S.begin(),S.end());
  int sum=0;
  for(int i=0;i<S.size()/2;i++){
    if(A.at(i)!=S.at(i)) sum+=1;
  }
  
  cout<<sum<<endl;
  
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
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 All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
typedef long long ll;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int r;
    cin >> r;
    cout << r * r << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
edges = [[] for _ in range(n)]
 
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
 
def bfs(v):
    q = []
    depth = [n]*n
    q.append(v)
    depth[v] = 0
    i = 0
    while i < len(q):
        x = q[i]
        d = depth[x]
        for e in edges[x]:
            if depth[e] == n:
                depth[e] = d+1
                q.append(e)
        i += 1
    return depth
 
d1 = bfs(0)
d2 = bfs(n-1)
 
c = 0
for i in range(n):
    if d1[i] <= d2[i]:
        c += 1
if 2*c > n:
    print("Fennec")
else:
    print("Snuke")

Measured memory_bytes: 29788
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			BigDecimal x1 = new BigDecimal(a).divide(new BigDecimal("0.08"), 0, BigDecimal.ROUND_CEILING);
			if(x1.subtract(BigDecimal.ONE).multiply(new BigDecimal("0.08")).intValue() == a) {
				x1 = x1.subtract(BigDecimal.ONE);
			}
			BigDecimal x2 = new BigDecimal(a + 1).divide(new BigDecimal("0.08"), 0, BigDecimal.ROUND_FLOOR);
			if(new BigDecimal(a + 1).remainder(new BigDecimal("0.08")).equals(BigDecimal.ZERO)) {
				x2 = x2.subtract(BigDecimal.ONE);
			}
			BigDecimal y1 = new BigDecimal(b).divide(new BigDecimal("0.1"), 0, BigDecimal.ROUND_CEILING);
			if(y1.subtract(BigDecimal.ONE).multiply(new BigDecimal("0.1")).intValue() == b) {
				y1 = y1.subtract(BigDecimal.ONE);
			}
			BigDecimal y2 = new BigDecimal(b + 1).divide(new BigDecimal("0.1"), 0, BigDecimal.ROUND_FLOOR);
			if(new BigDecimal(b + 1).remainder(new BigDecimal("0.1")).equals(BigDecimal.ZERO)) {
				y2 = y2.subtract(BigDecimal.ONE);
			}

			int min = Math.max(x1.intValue(), y1.intValue());
			int max = Math.min(x2.intValue(), y2.intValue());
			if(min <= max) {
				System.out.println(min);
			} else {
				System.out.println("-1");
			}
		}

	}

}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

int const MAXN = 505;
int n, k, mod;
int f[MAXN][MAXN], g[MAXN][MAXN][MAXN];

void Solve2() {
  k >>= 1;
  f[0][0] = 1;
  for (RI i = 1; i <= n; ++i) {
    f[i][0] = f[i - 1][0];
    for (RI j = k; j; --j) {
      f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod;
      f[i][0] = (f[i][0] + f[i - 1][j]) % mod;
    }
  }
  int L = 0, R = 0;
  for (RI i = 0; i <= k; ++i) {
    L = (L + f[n / 2][i]) % mod;
    R = (R + f[(n + 1) / 2][i]) % mod;
  }
  cout << 1ll * L * R % mod << endl;
}

void Solve1() {
  g[0][0][0] = 1;
  for (RI i = 2; i <= k + n; i += 2) {
    for (RI j = 0; j <= n; ++j)
      for (RI l = 0; l <= k + 1; ++l)
        g[i][0][0] = (g[i][0][0] + g[i - 2][j][l]) % mod;
    if (i <= n) { // only L
      for (RI j = 1; j <= n; ++j)
        for (RI l = 0; l <= k + 1; ++l)
          g[i][j][0] = (g[i][j][0] + g[i - 2][j - 1][l]) % mod;
    }
    if (i - k > 0) { // only R
      for (RI j = 0; j <= n; ++j) {
        for (RI l = 0; l <= k + 1; ++l)
          if (l != 1)
            g[i][0][l] = (g[i][0][l] + g[i - 2][j][l - (l > 0)]) % mod;
      }
    }
    if (i <= n && i - k > 0) { // L and R
      for (RI j = 0; j <= k - 1; ++j)
        for (RI l = 0; l <= k; ++l)
          (g[i][j + 1][max(j + 2, l + 1)] += g[i - 2][j][l]) %= mod;
    }
  }
  int last = (n + k) - ((n + k) & 1), ans = 0;
  for (RI i = 0; i <= n; ++i)
    for (RI j = 0; j <= k + 1; ++j)
      ans = (ans + g[last][i][j]) % mod;
  cout << ans << endl;
}

int main() {

#ifdef LOCAL
  FILEIO("a");
#endif

  cin >> n >> k >> mod;
  if (k & 1) Solve1();
  else Solve2();

  cerr << (double)(clock()) / CLOCKS_PER_SEC * 1000 << "ms" << endl;

  return 0;
}

// created by Daniel yuan

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


void solve(long long N, std::vector<long long> A){
    set<ll> s;
    for(ll i=0; i< N; i++){
        if(!s.count(A[i])) s.insert(A[i]);
        else s.erase(s.find(A[i]));
    }
    cout << s.size() << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define pb push_back
#define yes(a) printf(a ? "yes\n" : "no\n")
#define Yes(a) printf(a ? "Yes\n" : "No\n")
#define YES(a) printf(a ? "YES\n" : "NO\n") 
const long double PI = acos(-1);
const long long INF = (1 << 30);
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;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  string s;
  cin >> s;
  ll n = s.size();

  ll ans = 0;
  vector<ll> b(n);
  ll cnt = 0;
  for(ll i = 0; i < n; i++){
    if(s[i] == 'B') cnt++;
    b[i] = cnt;
  }

  for(ll i = 0; i < n; i++){
    if(s[i] == 'W'){
      ans += b[i];
    }
  }
  cout << ans << endl;
  return 0;
}

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

namespace Practice
{
    class Program
    {
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }

        static void SolveA(string[] args)
        {
            int[] abc = ReadAndParseIntArr();
            int k = ReadAndParseInt();
            int target = abc.Max();

            int ans = -target + abc.Sum();
            for(int i=0;i<k;++i)
            {
                target *= 2;
            }
            ans += target;
            Console.WriteLine(ans);
         }
    }
}


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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int> a(n), dp(k+1);
    for (int i=0; i<n; ++i){
    	cin>>a[i];
    }
 	dp[0]=0;
    for (int i=1; i<=k; ++i){
    	for (auto &x: a){
    		if (i-x<0) break;
    		if (dp[i-x]==0){
    			dp[i]=1;
    		}
    	}
    }
    cout<<(dp[k]?"First":"Second");
    return 0;
}


Measured memory_bytes: 3660
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100001;

int s[maxn],t[maxn],c[maxn];
P b[maxn];
int main(){
  int f1,f2,f3,f4;
  int n;
  cin>>n;
  f1=f2=f3=f4=0;
  for(int i=0;i<n;i++){
    char tmp;
    cin>>tmp;
    if(tmp=='P')f1=1;
    if(tmp=='W')f2=1;
    if(tmp=='G')f3=1;
    if(tmp=='Y')f4=1;
  }
  int res=f1+f2+f3+f4;
  if(res==3)cout<<"Three"<<endl;
  else cout<<"Four"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
vector<int> datas[maxn];
int ans[maxn];
void bfs()
{
	queue<int> q;
	q.push(1);
	ans[1]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(auto v:datas[u])
		{
			if(ans[v]==0)
			{
				q.push(v);
				ans[v]=u;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		datas[u].push_back(v);
		datas[v].push_back(u);
	}
	bfs();
	for(int i=2;i<=n;i++)
	{
		if(ans[i]==0)
		{
			cout<<"No\n";
			return 0;
		}
	}
	cout<<"Yes\n";
	for(int i=2;i<=n;i++)
		cout<<ans[i]<<"\n";
	return 0;
}




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

using namespace std;

using ll = long long;
using P = pair<int, int>;

int calc_N(int L) {
    int res = 0;
    int cur = 1;
    while (L >= cur) {
        res++;
        cur <<= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int L;
    cin >> L;
    int n = calc_N(L);
    vector< vector<P> > g(n);
    int m = 0;
    for (int i = 0; i < n - 1; i++) {
        g[i].emplace_back(i + 1, 0);
        g[i].emplace_back(i + 1, (1 << i));
        m += 2;
    }

    int cur = (1 << (n - 1));
    for (int i = n - 2; i >= 0; i--) {
        if (cur >= L) break;
        int hoge = (1 << i);
        if (cur + hoge > L) continue;
        g[i].emplace_back(n - 1, cur);
        m++;
        cur += hoge;
        if (cur >= L) break;
    }

    cout << n << " " << m << endl;
    for (int i = 0; i < n; i++) {
        for (P& p : g[i]) {
            cout << i + 1 << " " << p.first + 1 << " " << p.second << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import math
n,k = map(int,input().split())
ans=0

for i in range(1,min(n,k)+1):
  j = float(math.ceil(math.log(k/i)/math.log(2)))
  ans += float((1/n)*(1/2)**j) 
if k<n:
  ans += float((n-k)*1/n)
  
print(ans)  

Measured memory_bytes: 3060
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair <int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

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

const int mod = 1e9 + 7;
const char nl = '\n';

const int N = 50000;

void solve() {
    int n, k, sum(0);
    cin >> n >> k;
    int ara[n];
    for(int i = 0; i < n; ++i){
        cin >> ara[i];
    }
    sort(ara, ara + n);
    for(int i = 0; i < k; ++i){
        sum += ara[i];
    }
    cout << sum << nl;
}

int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Measured memory_bytes: 3644
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int h = in.nextInt();
		int w = in.nextInt();
		String[] s = new String[h];
		for (int i = 0; i < h; i++)
			s[i] = in.next();
		System.out.println(solve(h, w, s));
		in.close();
	}

	private static int solve(int h, int w, String[] s) {
		int[][] hl = new int[h][w];
		int[][] wl = new int[h][w];
		for (int i = 0; i < h; i++) {
			if (s[i].charAt(0) == '.')
				wl[i][0] = 1;
			for (int j = 1; j < w; j++)
				if (s[i].charAt(j) == '.')
					wl[i][j] = wl[i][j - 1] + 1;
			for (int j = w - 2; j >= 0; j--)
				if (wl[i][j] > 0 && wl[i][j + 1] > 0)
					wl[i][j] = wl[i][j + 1];
		}
		for (int j = 0; j < w; j++) {
			if (s[0].charAt(j) == '.')
				hl[0][j] = 1;
			for (int i = 1; i < h; i++)
				if (s[i].charAt(j) == '.')
					hl[i][j] = hl[i - 1][j] + 1;
			for (int i = h - 2; i >= 0; i--)
				if (hl[i][j] > 0 && hl[i + 1][j] > 0)
					hl[i][j] = hl[i + 1][j];
		}
		int r = 0;
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				if (wl[i][j] + hl[i][j] - 1 > r)
					r = wl[i][j] + hl[i][j] - 1;
		return r;
	}
}

Measured memory_bytes: 67836
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int h, w, n;
    cin >> h >> w >> n;
    int ans = h, nowx = 0, nowy = 0, x, y;
    vector<set<int> > s(w, {114514810});
    for(int i=0;i<n;i++){
    	cin >> x >> y;
    	x--; y--;
    	s[y].insert(x);
    }
    while(nowx < h){
    	ans = min(ans, *s[nowy].upper_bound(nowx));
    	nowx++; nowy++;
    	if(nowy >= w) break;
    	while(s[nowy].count(nowx)) nowx++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 31392