akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int N = (int)2e5;

pair<long long, long long> dat[N+5];

int main() {
    int n; scanf("%d", &n);
    long long d,a; scanf("%lld %lld", &d, &a);
    for (int i=1; i<=n; i++) {
        scanf("%lld %lld", &dat[i].first, &dat[i].second);
        dat[i].second = (dat[i].second + a - (long long)1) / a;
    }

    sort(dat+1, dat+1+n);

    queue< pair<long long, long long> > effect;
    while (!effect.empty()) effect.pop();

    long long res = 0;
    long long curr = 0;
    for (int i=1; i<=n; i++) {
        while (!effect.empty() && effect.front().first < dat[i].first) {
            curr -= effect.front().second;
            effect.pop();
        }

        dat[i].second = max((long long)0, dat[i].second - curr);

        curr += dat[i].second;
        effect.push(make_pair(dat[i].first + d + d, dat[i].second));

        res += dat[i].second;
    }

    printf("%lld\n", res);
    return 0;
}


Measured memory_bytes: 6656
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
const Int MAX = 30*30;
using BS = bitset<MAX*2>;
using mat = vector<BS>;

void gauss(mat &v){
  int n=v.size();
  for(Int i=0;i<n;i++){
    for(Int k=i;k<n;k++){
      if(v[k][i]){
	swap(v[i],v[k]);
	break;
      }
    }
    for(Int k=0;k<n;k++)
      if(i!=k&&v[k][i]) v[k]^=v[i];
  }
}

int mrank(mat v,int m){
  int n=v.size();
  int r=0,c=0;
  for(int i=0;i<n;i++){
    int s=-1;
    while(c<m){
      for(int j=i;j<n;j++){
	if(v[j][c]){
	  s=j;
	  break;
	}
      }
      if(~s) break;
      c++;
    }
    if(c>=m) break;
    
    swap(v[i],v[s]);
    for(int j=0;j<n;j++)
      if(i!=j&&v[j][c]) v[j]^=v[i];
    
    r++;c++;
  }
  return r;
}

mat mul(const mat &a,const mat &b){
  int n=a.size();
  vector<vector<int> > tmp(n,vector<int>(n,0));
  mat res(n,BS(0));
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      for(int k=0;k<n;k++)
	tmp[i][j]+=(a[i][k]&b[k][j]);
  
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      res[i][j]=tmp[i][j]&1;
  
  return res;
}

mat mat_pow(mat v,int k){
  int n=v.size();
  mat res(n,BS(0));
  for(int i=0;i<n;i++)
    res[i][i]=1;
  while(k){
    if(k&1) res=mul(res,v);
    v=mul(v,v);
    k>>=1;
  }
  return res;
}

signed main(){
  int m,n,d;
  while(cin>>m>>n>>d,m){
    vector<vector<int> > s(n,vector<int>(m));
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
	cin>>s[i][j];

    mat v(n*m,BS(0));
    auto idx=[&](int y,int x){return y*m+x;};
    auto in=[&](int y,int x){return 0<=y&&y<n&&0<=x&&x<m;};
    auto bfs=[&](int y,int x){
      int z=idx(y,x);
      v[z][z]=1;
      v[z][n*m]=s[y][x];
      
      vector<vector<int> > dp(n,vector<int>(m,-1));
      using P = pair<int, int>;
      queue<P> q;
      dp[y][x]=0;
      q.emplace(y,x);
      int dy[]={0,0,1,-1};
      int dx[]={1,-1,0,0};
      while(!q.empty()){
	tie(y,x)=q.front();q.pop();
	if(dp[y][x]==d) v[z][idx(y,x)]=1;
	for(int k=0;k<4;k++){
	  int ny=y+dy[k],nx=x+dx[k];
	  if(!in(ny,nx)||~dp[ny][nx]) continue;
	  dp[ny][nx]=dp[y][x]+1;
	  q.emplace(ny,nx);
	}
      }
    };
    
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
	bfs(i,j);
    
    int a=mrank(v,n*m);
    int b=mrank(v,n*m+1);
    cout<<(a==b)<<endl;
  }
  return 0;
}



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

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

	vector<int> v(n), c(n);

	for (auto& i : v) {
		cin >> i;
	}
	for (auto& i : c) {
		cin >> i;
	}

	int ret = 0;
	for (int i = 0; i < n; ++i) {
		int diff = v[i] - c[i];
		if (0 < diff) {
			ret += diff;
		}
	}

	cout << ret << endl;

	return 0;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  char A[N][N];
  char B[M][M];
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++) cin >> A[i][j];
  }
  for(int i=0; i<M; i++){
    for(int j=0; j<M; j++) cin >> B[i][j];
  }
  int ans=0;
  if(N==M){
    int cnt=0;
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        if(A[i][j]==B[i][j]) cnt++;
      }
    }
    if(cnt==N*N) ans++;
  }
  else{
    for(int i=0; i<N-M; i++){
    for(int j=0; j<N-M; j++){
      int cnt=0;
      for(int k=0; k<M; k++){
        for(int l=0; l<M; l++){
          if(A[k+i][l+j]==B[k][l]) cnt++;
        }
      }
      if(cnt==M*M) ans++;
    }
  }
  }
  if(ans>0) cout << "Yes" << endl;
  else cout << "No" << endl;
} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>

using namespace std;

void solve();

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

//////////////////////////////////////////////////
//////////////////////////////////////////////////

class pos {
public:
	int x, y;
	pos(int _x, int _y):x(_x),y(_y){}
	pos():x(0),y(0){}
};

int H, W;
int map[50][50];
void bfs();

bool isIn(pos p) {
	if (p.x >= 0 && p.x < W && p.y >= 0 && p.y < H)return true;
	return false;
}

pos operator+(pos a,pos b) {
	return pos(a.x+b.x,a.y+b.y);
}

void solve() {
	cin >> H >> W;
	int black = 0;
	for (int y = 0; y < H; y++) {
		string s;
		cin >> s;
		for (int x = 0; x < W; x++) {
			if (s[x] == '#') {   //黒
				black++;
				map[x][y] = -1;   //通れない
			}
			else {
				map[x][y] = 50 * 50;
			}
		}
	}
	bfs();
	if (map[W-1][H-1] == 50*50)cout << "-1";
	else cout << H * W - map[W - 1][H - 1] - black;
	return;
}

void bfs() {
	queue<pair<pos, int>> q;
	q.push(pair<pos,int>(pos(0,0),1));
	while (!q.empty()) {
		pos p = q.front().first;
		int d = q.front().second;
		q.pop();
		if (map[p.x][p.y] <= d)continue;
		map[p.x][p.y] = d;
		pos vecs[4] = {pos(1,0),pos(0,1),pos(-1,0),pos(0,-1)};
		for (int v = 0; v < 4; v++) {
			pos n = p + vecs[v];
			if (!isIn(n))continue;
			if (map[n.x][n.y] == -1)continue;
			q.push(pair<pos,int>(n,d+1));
		}
	}
	return;
}

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

int main(void){
    string s;
    getline(cin, s);
    for(int i = 0; i < s.size(); i++)   {
        char c = s[i];
        if('A' <= c && c <= 'Z')  {
            //c = tolower(c);
            c = c + 32;
        }
        else if('a' <= c && c <= 'z')   {
            c = c -32;
        }
        cout << c;
    }
    cout  << endl;
    
}


Measured memory_bytes: 3200
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using E = System.Linq.Enumerable;
 
class Program
 {

        static void Main(string[] args)
        {
          //入力を受け取る
          var N = int.Parse(Console.ReadLine());
          string S = Console.ReadLine();
          //var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
          var front = S.Substring(0, N/2);
          var back =  S.Substring(N/2, N/2);
          
          if(N%2 == 0 && front == back){
            Console.WriteLine("Yes");
          }else{
            Console.WriteLine("No");
          }
        }
  
        // 最小公倍数
        public static long Lcm(long a, long b) {
            return a * (b / Gcd(a, b));
        }

        // ユークリッドの互除法 
        public static long Gcd(long a, long b) {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0) {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }
  
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int s = a * b;
	int t = c * d;

	if (s > t) cout << s << endl;
	else cout << t << endl;

	return 0;
}


Measured memory_bytes: 256
struct T{int a,b;}A[3333];long P[3333],M=1e9+7,F[2<<17],I[2<<17],X;i,j,k,t;
c(a,b)struct T*a,*b;{t=a->a-b->a?:a->b-b->b;}
p(a,b){return b?p(a%M*a%M,b/2)%M*(b%2?a:1)%M:1;}
f(a,b){return F[a+b]*I[a]%M*I[b]%M;}
main(s)
{
	for(*F=*I=1;++k<2<<17;)I[k]=p(F[k]=F[k-1]*k%M,M-2);
	for(k=A;~scanf("%d",k);k+=4)i++-1||gets(P);
	for(qsort(A,i/=2,8,c);j<i;P[j++]=X)
		for(X=f(s=A[k=j].a-=1,t=A[j].b-=1);k--;)t>=A[k].b?X=(X-f(s-A[k].a,t-A[k].b)*P[k]%M+M)%M:0;
	printf("%d",X);
}

Measured memory_bytes: 4352
s=str(input())
if(s=="SUN"):
    print("7")
elif(s=="MON"):
    print("6")
elif(s=="TUE"):
    print("5")
elif(s=="WED"):
    print("4")
elif(s=="THU"):
    print("3")
elif(s=="FRI"):
    print("2")
elif(s=="SAT"):
    print("1")


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

int main(int argc, char const *argv[])
{
    int w, h, x, y; cin >> w >> h >> x >> y;
    double cw = double(w) / 2.0;
    double ch = double(h) / 2.0;

    if (cw == double(x) && ch == double(y)) {
        cout << fixed << setprecision(8) << double(w) * double(h) / 2.0 <<  " " << 1 << endl;
    } else if (cw == double(x) || ch == double(y)) {
        cout << fixed << setprecision(8) << double(w) * double(h) / 2.0 <<  " " << 0 << endl;
    } else {
        double angle = (ch - double(y)) / (cw - double(x));
        double y0 = ch - angle * cw;
        double yw = ch + angle * cw;
        double s = (y0 + yw) * double(w) / 2.0;
        cout << fixed << setprecision(8) << s << " " << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

const int SIZE = 531441;

int N;

int THREE[13];
char buf[200011];


VI normal(const string &s) {
    VI ret;
    int cnt = 0;
    REP (i, s.size()) {
	if (s[i] == 'S') {
	    if (cnt) ret.push_back(cnt);
	    cnt = 0;
	    if (ret.size() && ret.back() == -1) ret.pop_back();
	    else ret.push_back(-1);
	} else {
	    cnt++;
	}
    }
    if (cnt) ret.push_back(cnt);
    return ret;
}

vector<vector<int> > G[13];
vector<int> H[13];

void MAIN() {
    scanf("%d", &N);
    scanf("%s", buf);

#ifdef MYTEST
    N = 12;
    REP (i, 20000) {
	if (i % 4 == 0) buf[i] = 'S';
	else buf[i] = 'R';
    }
#endif

    THREE[0] = 1;
    REP (i, N) THREE[i+1] = THREE[i] * 3;
    REP (i, N+1) {
	G[i].resize(THREE[i]);
	H[i].resize(THREE[i]);
    }
    G[0][0] = normal(buf);

    REP (i, N) REP (s, THREE[i]) REP (a, 3) {
	const int val = a * THREE[i] + s;
	int x = a;
	const VI &g = G[i][s];
	VI t;

	REP (j, g.size()) {
	    if (g[j] == -1) {
		if (t.size() && t.back() == -1) t.pop_back();
		else t.push_back(-1);
		if (x) x = 3 - x;
	    } else {
		x += g[j];
		if (x / 3) {
		    if (t.size() && t.back() >= 0) t.back() += x/3;
		    else t.push_back(x/3);
		}
		x %= 3;
	    }
	}
	G[i+1][val] = t;
	H[i+1][val] = x * THREE[i] + H[i][s];
    }

    // REP (i, N) rprintf("%d", H[i].begin(), H[i].end());

    rprintf("%d", H[N].begin(), H[N].end());

}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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

int main(){
	string s;
	cin >> s;
	if(s.size() == 2){
		if(s[0] == s[1])puts("1 2");
		else puts("-1 -1");
	}
	else {
		for(int i = 0 ; i+2 < s.size() ; i ++){
			if(s[i] == s[i+1] || s[i+1] == s[i+2] || s[i] == s[i+2]){
				cout << i+1 << " " << i+3 << endl;
				return 0;
			}
		}
		puts("-1 -1");
	}
}

Measured memory_bytes: 512
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <cassert>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

char str[200005];
const int MM = 2019;

void solve()
{
    scanf("%s", str);
    int n = strlen(str);
    vector<int> z(MM);
    int i;
    int curr = 0;
    int tmp = 1;
    z[curr]++;
    for (i = 0; i < n; i++) {
        int a = (str[n - 1 - i] - '0');
        curr = (curr + a * tmp) % MM;
        z[curr]++;
        tmp = tmp * 10 % MM;
    }

    ll ans = 0;
    for (i = 0; i < MM; i++) {
        ans += (ll)z[i] * (z[i] - 1) / 2;
    }
    printf("%lld\n", ans);
    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 3440
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,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 fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll 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())

const int MAX = 510;
const int MOD = 1000000007;

// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll d[MAX][MAX];
bool maze[MAX][MAX];

void dfs(ll x , ll y){
  ll z = d[x][y] + maze[x][y];
  // 距離が減るところをdfsで減らす
  rep(i,4){
    ll nx = x + dx[i];
    ll ny = y + dy[i];
    if(nx < 0 or ny < 0) continue;
    if(d[nx][ny] > z){
      d[nx][ny] = z;
      dfs(nx , ny);
    }
  }
}

int main(){
  ll N; cin >> N;
  ll ans = 0;
  // 外周までの距離の初期設定
  rep(i,N) rep(j,N) d[i][j] = min( min(i, j) , min(N - i - 1 , N - j - 1) );
  // pの入力
  vector<ll> p(N * N); rep(i,N * N) cin >> p[i]; rep(i, N * N) p[i]--;
  // mazeの初期化、埋まったところからはそのままいける
  rep(i,MAX) rep(j,MAX) maze[i][j] = true;
  // dfsの操作
  rep(i, N * N){
    ll x = p[i] / N;
    ll y = p[i] % N;
    ans += d[x][y];
    maze[x][y] = false;
    dfs(x, y);
  }
  cout << ans << endl;
}


Measured memory_bytes: 22956
#include <iostream>
#include <cmath>

long long MAX = std::pow(10, 18);

int main(int argc, const char * argv[]) {
    long long N = 0;
    scanf("%lld", &N);

    long long ans = 0;
    scanf("%lld", &ans);

    for(int i=1; i<N; i++) {
        long long num = 0;
        scanf("%lld", &num);

        if(ans == -1 && num == 0) {
            ans = 0;
        } else if(ans == -1 && num > 0) {
            ans = -1;
        } else if(MAX/ans < num) {
            ans = -1;
        } else {
            ans *= num;
        }

        if(ans == 0) {
            break;
        }
    }

    std::cout << ans;

    return 0;
}


Measured memory_bytes: 3696
#include<bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define mod 1000000007
using namespace std;
int x[100010],y[100010];
signed main(){
	int a,b;
	cin>>a>>b>>y[0];
	x[0]=0;
	f(i,a-1){
		cin>>y[i+1];
		x[i+1]=mod;
		for(int j=0;j<=i&&j<b;j++){
			x[i+1]=min(x[i+1],abs(y[i+1]-y[i-j])+x[i-j]);
		}
	}
	cout<<x[a-1]<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
#define ll long long
int main() {
    ll n,h,a,b,ans=0,cnt=0;
    cin >> n >> h;
    vector<ll> a_1,b_1;
    for(ll i=0;i<n;i++){
        cin >> a >> b;
        a_1.push_back(a);
        b_1.push_back(b);
    }
    sort(b_1.begin(),b_1.end(),greater<ll>());
    ll max = *max_element(a_1.begin(),a_1.end());
    for(ll i=0;i<h;i++){
        if(b_1[i]>=max){
            cnt+=b_1[i];
            ans++;
        }
        if(b_1[i]<max){break;}
        if(cnt>=h){
            cout << ans << endl;
            return 0;
        }
    }
    if((h-cnt)%max!=0){cout << ans+(h-cnt)/max+1 <<endl;}
    else cout << ans+(h-cnt)/max << endl;

    return 0;
}

Measured memory_bytes: 2036
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<climits>
#include<algorithm>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<sstream>
#include<cstring>

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

using namespace std;

int main() {
  string s;
  cin >> s;
  rep(i,(int)s.size()) if( s[i] == ',' ) s[i] = ' ';
  cout << s << endl;
  return 0;
}


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

using namespace std;

int main() {
    int n,k,x,y;
    cin >> n >> k >> x >> y;
    int ans=0;
    if(n>k){
        ans+=k*x;
        ans+=(n-k)*y;
    }
    else{
        ans+=n*x;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
MOD = 10**9+7
S = int(input())
if S < 3:
    print(0)
elif S <= 5:
    print(1)
else:
    d = [0]*2001
    for i in range(6):
        d[i] = 1
    for i in range(6, S+1):
        for j in range(3, i-3+1):
            d[i] += d[i-j]
            d[i] %= MOD
        d[i] = (d[i]+1) % MOD
    print(d[S])


Measured memory_bytes: 64976
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main(){
  int n;
  int r;
  int a[100];
  int b[100];
  int p;
  int c;
  while(cin >> n >> r){
    if(n == 0 && r == 0){
      break;
    }
    for(int i = 0;i < n;i++){
      a[i] = n-i;
    }
    for(int i = 0;i < r;i++){
      cin >> p >> c;
      for(int j = p-1;j < p+c; j++){
        b[j-p+1] = a[j];//c block
      }
      for(int j = p-2;j >= 0;j--){
        a[j+c] = a[j];
      }
      for(int j = 0;j < c;j++){
        a[j] = b[j];
      }
      //cout << a[0] << a[1] << a[2] << a[3] << a[4] << endl;
    }
  cout << a[0] << endl;
  }
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
const ll MOD = 1e9+7; ll LLINF = 1LL << 60; int INF = INT_MAX;

//

int main(){
      ll n; cin>>n;
      vector<ll> a(n);
      rep(i,0,n) cin>>a[i];
      ll ans=0;
      rep(i,0,n){
            while(a[i]%2==0){
                  a[i]/=2;
                  ans++;
            }
      }
      cout<<ans<<endl;
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

#define INF 1e9


int main(){
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> S(H);
  REP(i, H){
    cin >> S[i];
  }
  vector<vector<int>> G(H, vector<int>(W, 0));
  REP(i, H){
    REP(j, W){
      G[i][j] = S[i][j] - '0';
    }
  }
  int ans = INF;
  REP(bit, 1<<(H-1)){
    vector<int> cnt(H, 0);
    int width = 0;
    bool end = false;
    REP(j, W){
      bool update = false;
      int h = 0;
      REP(i, H){
        cnt[h]+= G[i][j];
        if(cnt[h] > K){
          update = true;
          break;
        }
        if(bit>>i & 1){
          h++;
        }
      }
      if(update){
        width++;
        h=0;
        REP(i, H){
          cnt[i] = 0;
        }
        REP(i, H){
          cnt[h] += G[i][j];
          if(cnt[h] > K){
            end = true;
            break;
          }
          if(bit>>i & 1){
            h++;
          }
        }
        if(end){
          break;
        }
      }
    }
    if(end) continue;
    int height = 0;
    REP(i, H){
      if(bit >> i &1){
        height++;
      }
    }
    ans = min(ans, width+height);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

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

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}



int main(){
  int a;cin>>a;
  if(a==7 || a==5 || a==3)cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
n = int(input())
L = [[True for i in range(13)]for j in range(4)]
S = ("S","H","C","D")
for i in range(n):
    s,m = input().split()
    for j in range(4):
        if s==S[j]:
            L[j][int(m)-1]=False
for i in range(4):
    for j in range(13):
        if L[i][j]:
            print(S[i]+" "+str(j+1))


Measured memory_bytes: 5604
#include<iostream>
using namespace std;
int main(){
  int j[5];
  int jj,jk,jp;
  while(cin>>j[0]){
    if(j[0]==0) break;
    for(int i=1;i<5;i++) cin >> j[i];
    jj = 0;
    jk = 0;
    jp = 0;
    for(int i=0;i<5;i++){
      if(j[i]==1) jj++;
      else if(j[i]==2) jk++;
      else jp++;
    }
    if(jj!=0&&jk!=0&&jp!=0||jj==5||jk==5||jp==5){
      for(int i=0;i<5;i++) cout << 3 << endl;
    }
    else if(jj==0){
      for(int i=0;i<5;i++){
	if(j[i]==2) cout << 1 << endl;
	else cout << 2 << endl;
      }
    }
       else if(jk==0){
      for(int i=0;i<5;i++){
	if(j[i]==1) cout << 2 << endl;
	else cout << 1 << endl;
      }
    }
        else{
      for(int i=0;i<5;i++){
	if(j[i]==1) cout << 1 << endl;
	else cout << 2 << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1160
N=int(input())
A=[0]+[int(x) for x in input().split()]+[0]

t=sum(abs(A[i]-A[i-1]) for i in range(1,N+2))
for i in range(1,N+1):
  print(t-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))


Measured memory_bytes: 14048
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define upb upper_bound
#define lwb lower_bound
#define show(x) cout << #x << " is " << x << "\n";
const ll inf = 2e18;
const ll mod = 1e9 + 7;
const ld pi = 3.141592653589793238462643383279502884;

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

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y){
    if(y<=0) return 1;
    ll ans = 1;
    x %= mod;
    while(y){
        if(y&1)
            ans = (x * ans) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = (a - b); if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = (a + b); if(c >= mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

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

//const ll N = 2e5 + 1;
//vector<ll> adj[N];
//bool visited[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cout<<fixed<<setprecision(10);



	ll n, x, t;
	cin>>n>>x>>t;
	ll ans=(n+x-1)/x;
	cout<<ans*t;


    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intput(i) cout << i << endl
#define ll long long
#define stringput(s) cout << (string)(s) << endl

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


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		final int MAX = 9;
		Scanner sc = new Scanner(System.in);
		int[] data = new int [MAX*2+1];
		
		for(int i = 0; i <= MAX*2; i++){
			for(int k = 0; k <= i; k++){
				if (k <= MAX && (i-k)<= MAX){
					data[i]++;
				}
			}
		}
		
		while(sc.hasNext()){
			int n = 0;
			int in = sc.nextInt();
			if(in >= 0 && in <= MAX*4){
				for(int j = 0; j <= in; j++){
					if(j > MAX*2 || in-j > MAX*2){
						continue;
					}
					n += data[j] * data[in-j];
				}
			}
			System.out.println(n);
		}
	}
}

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

using namespace std;
typedef long long ll;

ll c[51][51];

void comb() {
    for (int i = 0; i <= 50; i++)
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) c[i][j] = 1;
            else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
}

int main(void) {
    comb();

    int n, a, b;
    cin >> n >> a >> b;
    
    vector<ll> v(n);
    map<ll, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        mp[v[i]]++;
    }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    
    double sum = 0;
    int p = 0, q = mp[v[a - 1]];
    for (int i = 0; i < a; i++) {
        sum += v[i];
        if (v[i] == v[a - 1]) p++;
    }

    ll ans = 0;    
    if (p != a) {
        ans = c[q][p];
    } else {
        for (int i = p; i <= min(q, p + b - a); i++)
            ans += c[q][i];
    }
    double ave = sum / (double)a;
    printf("%.10lf\n%lld\n", ave, ans);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb emplace_back
#define mp make_pair
#define nt _ll128
#define ld long double
long double PI =3.14159265358979323846;
using ll = long long;



const ll modo=1e9+7;
const ll inf=LONG_LONG_MAX;
const ll ms=(2e5)+5;

int  ar[ms]={0};

ll peil(ll a,ll b)
{
    if(a%b)return a/b+1;
    return a/b;
}
int main()
{
    idfc;
    ll a,b,x;
    cin>>a>>b>>x;
    ll ans= (b/x)+1-peil(a,x);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3612
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

ll MOD = 1e9 + 7;

template <typename T>
class SegmentTreeSum
{
private:
    int m_n;
    vector<T> m_dat;
public:
    SegmentTreeSum(int n) {
        m_n = 1;
        while (m_n < n) m_n *= 2;
        m_dat.resize(2 * m_n - 1, 0);
    }
    // k番目に値valを加算
    void update(int k, T val) {
        k += m_n - 1;
        m_dat[k] += val;
        m_dat[k] %= MOD;
        while (k > 0) {
            k = (k - 1) / 2;
            m_dat[k] = m_dat[k * 2 + 1] + m_dat[k * 2 + 2];
            m_dat[k] %= MOD;
        }
    }
    // [a, b)の範囲で合計を返す
    T query(int a, int b) {
        return queryInternal(a, b, 0, 0, m_n);
    }

private:
    T queryInternal(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return m_dat[k];
        else {
            T vl = queryInternal(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = queryInternal(a, b, k * 2 + 2, (l + r) / 2, r);
            return (vl + vr) % MOD;
        }
    }
};

class Bit
{
private:
    int m_n;
    vector<int> m_bit;
    
public:
    void init(int n) {
        m_n = n;
        m_bit.resize(n + 1);
    }

    // 要素1から要素iまでの和
    ll sum(int i) {
        ll s = 0;
        while (i > 0) {
            s += m_bit[i];
            s %= MOD;
            i -= i & -i;
        }
        return s;
    }
    
    void add(int i, ll x) {
        while (i <= m_n) {
            m_bit[i] += x;
            m_bit[i] %= MOD;
            i += i & -i;
        }
    }
};

int main(void)
{
    cin.sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;

    vector<ll> Ss(N);
    vector<ll> Ts(M);
    REP(n, N) cin >> Ss[n];
    REP(m, M) cin >> Ts[m];

    Bit st;
    st.init(M);
    map<int, vector<int>> t_to_locs;
    REP(m, M) {
        auto t = Ts[m];
        t_to_locs[t].pb(m);
    }
    
    for(auto s: Ss) {
        vector<ll> added;
        for(auto loc: t_to_locs[s]) {
            added.pb(st.sum(loc));
        }
        int i = 0;
        for(auto loc: t_to_locs[s]) {
            st.add(loc + 1, 1 + added[i]);
            ++i;
        }
    }
    ll ans = 1 + st.sum(M);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    ll x;
    cin >> x;
    cout << (x ^ 1) << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <set>
#include <deque>
#include <utility>
#include <map>
#include <algorithm>

int main() {
    long long n, m, l, r, d;
    bool ret = true;
    std::cin >> n >> m;
    std::vector<std::deque<std::pair<long long, long long>>> g(n);
    std::map<long long, long long> pos;
    std::vector<bool> done(n, false);

    for (auto i = 0ll; i < m; i++) {
        std::cin >> l >> r >> d;
        l--; r--;
        g[l].push_back({ r, d });
        g[r].push_back({ l, -d });
    }

    for (auto it = done.begin(); it != done.end(); it = std::find(it, done.end(), false)) {
        //std::cout << (it - done.begin()) << std::endl;
        std::deque<long long> q;
        q.push_back(it - done.begin());
        pos[it - done.begin()] = 0;
        while (!q.empty()) {
            auto curr = q.front();
            q.erase(q.begin());
            done[curr] = true;
            for (auto& el : g[curr]) {
                if (pos.find(el.first) == pos.end()) {
                    pos[el.first] = pos[curr] + el.second;
                    if (!done[el.first]) q.push_back(el.first);
                } else {
                    (ret &= (pos[el.first] == pos[curr] + el.second)) || (q.clear(), 1);
                }
            }
        }
        if (!ret) break;
    }

    std::cout << (ret ? "Yes" : "No") << std::endl;

    return 0;
}

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

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;

const char nl = '\n' ;
const ll MOD = 1e9 + 7;


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int n, k; cin >> n >> k;
   int a[n];
   for(int i = 0; i < n; i++)
      cin >> a[i];
   sort(a, a+ n);
   int sum = 0;
   for(int i = n-1; i >= n-k; i--)
   {
      sum += a[i];
   }
   cout << sum << nl;


   return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int INF = 987654321;
const int MOD = 1000000007;

int H,W;
char mat[401][401];
bool chk[401][401];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
ll ans = 0;
ll tmp = 0, cnt = 1;

void dfs(int sy, int sx, int idx){
  chk[sy][sx] = true;
  for(int i=0;i<4;i++){
    int y = sy+dir[i][0], x = sx+dir[i][1];
    if(y < 0 || y >= H || x < 0 || x >= W) continue;
    if(!chk[y][x] && mat[y][x] == (idx == 0 ? '.' : '#')){
      if(mat[y][x] == '.') tmp++;
      else cnt++;
      dfs(y,x,!idx);
    }
  }
}

int main(){
  scanf("%d %d",&H,&W);
  for(int i=0;i<H;i++)
    scanf("%s",mat[i]);
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(mat[i][j] == '#' && chk[i][j] == false){
        tmp = 0; cnt = 1;
        dfs(i,j,0);
        ans += cnt * tmp;
      }
    }
  }
  printf("%lld\n",ans);
}


Measured memory_bytes: 8064
#include <stdio.h>
#include <iostream>
#define INF 9999999999999.0
#define D 2
#define MAXN 200005
int M;
using namespace std;
struct Point{
    long long x[D];
}pt[MAXN];
long long dis[1<<D][MAXN],minx[1<<D],maxx[1<<D];
void Get(int N){
    int tot=(1<<D);
    for(int s=0;s<tot;s++){
        int coe[D];
        for(int i=0;i<D;i++)
        if(s&(1<<i)) coe[i]=-1.0;
        else coe[i]=1.0;

        for(int i=0;i<N;i++){
            dis[s][i]=0.0;
            for(int j=0;j<D;j++)
            dis[s][i]=dis[s][i]+coe[j]*pt[i].x[j];
        }
    }
}
void Solve(int N){
    int tot=(1<<D);
    long long tmp,ans;
    for(int s=0;s<tot;s++){
        minx[s]=INF;
        maxx[s]=-INF;
        for(int i=0;i<N;i++){
            if (minx[s]>dis[s][i]) minx[s]=dis[s][i];
            if (maxx[s]<dis[s][i]) maxx[s]=dis[s][i];
        }
    }
    ans=0.0;
    for(int s=0;s<tot;s++){
        tmp=maxx[s]-minx[s];
        if(tmp>ans) ans=tmp;
    }

    cout<<ans;
}

int main(){
    scanf("%d",&M);
    for(int i=0;i<M;i++){
        scanf("%lld%lld",&pt[i].x[0],&pt[i].x[1]);
    }
    Get(M);
    Solve(M);
    return 0;
}

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

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;

vector<vector<int>> graph;
vector<bool> visited;

pair<ll, ll> dfs(int v) {
    visited[v] = true;

    ll white = 1, black = 1;
    for (auto nv:graph[v]) {
        if (visited[nv])continue;
        auto now = dfs(nv);
        white *= now.first + now.second, white %= MOD;
        black *= now.first, black %= MOD;
    }

    return {white, black};
}

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

    graph.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b), graph[b].push_back(a);
    }

    visited.assign(n, false);
    auto ret = dfs(0);
    cout << (ret.first + ret.second) % MOD << endl;
    return 0;
}

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

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

int main()
{
    int n;
    scanf("%d", &n);

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

    sort(inp, inp + n);

    // 9 1 14 5 5 4 4 14
    // 1 4 4 5 5 9 14 14

    // 9 1 4 4 6 7
    // 1 4 4 6 7 9

    if (inp[n / 2 - 1] == inp[n / 2])
        printf("0\n");
    else
        printf("%d\n", inp[n / 2] - inp[n / 2 - 1]);

    return 0;
}


Measured memory_bytes: 640
use proconio::input;

// 1箇所に1個: シュミレーションすればいい
// 1箇所に2個以上: AならBCだとだめ。それ以外ならOK。
// 2箇所以上: OK

#[derive(PartialEq, Eq, Clone, Copy)]
enum Query {
    AB,
    AC,
    BC,
}

impl Query {
    fn to_ints(&self) -> (usize, usize) {
        use Query::*;

        match self {
            AB => (A, B),
            AC => (A, C),
            BC => (B, C),
        }
    }

    fn intersection(x: Query, y: Query) -> usize {
        use Query::*;

        match (x, y) {
            (AB, AC) | (AC, AB) => A,
            (AB, BC) | (BC, AB) => B,
            (AC, BC) | (BC, AC) => C,
            _ => x.to_ints().0,
        }
    }
}

const A: usize = 0;
const B: usize = 1;
const C: usize = 2;

const YES: &str = "Yes";
const NO: &str = "No";

fn main() {
    input! {
        n: usize,
        a: i64,
        b: i64,
        c: i64,
        queries: [String; n],
    }

    let mut state = vec![a, b, c];
    let mut ans = vec![];
    for i in 0..n {
        // dbg!(&state);

        let q = parse_query(&queries[i]);
        let next_q = queries.get(i + 1).map(|q| parse_query(q));
        let (choosed, other) = match choose(&state, q, next_q) {
            Some(v) => v,
            None => {
                println!("{}", NO);
                return;
            }
        };
        state[choosed] += 1;
        state[other] -= 1;
        ans.push(int_to_char(choosed));
    }

    // dbg!(&state);

    println!("{}", YES);
    for &c in &ans {
        println!("{}", c);
    }
}

fn parse_query(s: &str) -> Query {
    use Query::*;

    match s {
        "AB" => AB,
        "AC" => AC,
        _ => BC,
    }
}

fn int_to_char(x: usize) -> char {
    match x {
        0 => 'A',
        1 => 'B',
        _ => 'C',
    }
}

fn choose(state: &Vec<i64>, q: Query, next_q: Option<Query>) -> Option<(usize, usize)> {
    let (x, y) = q.to_ints();

    if state[x] == 0 && state[y] == 0 {
        return None;
    }

    // 選択肢がない場合
    if state[x] == 0 {
        return Some((x, y));
    }
    if state[y] == 0 {
        return Some((y, x));
    }

    // 選択肢がある場合
    if state[x] > 1 {
        return Some((y, x));
    }
    if state[y] > 1 {
        return Some((x, y));
    }

    // どちらも1

    // 最後ならどちらでも
    if next_q.is_none() {
        return Some((x, y))
    }

    // そうでないなら先読みする必要がある
    let next_q = next_q.unwrap();
    if next_q == q {
        // どっちでも
        return Some((x, y))
    }
    let is = Query::intersection(q, next_q);
    let other = if x == is { y } else { x };
    Some((is, other))
}


Measured memory_bytes: 8336
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define inf 500000000
#define IOS ios_base::sync_with_stdio(0)
#define meM(y,a) memset(y,a,sizeof y)
#define sC(a) scanf("%d",&a)
#define alL(a) a.begin(),a.end()
#define prinT(a,sz)  cout<<a[0];for(int i=1;i<sz;i++)cout<<" "<<a[i];cout<<endl
#define ranD srand(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int>pi;
typedef pair<ll,ll>pll;
//int fx[]={0,0,1,-1};
//int fy[]={1,-1,0,0};
//int gx[]={0,0,1,1,1,-1,-1,-1};
//int gy[]={1,-1,0,1,-1,0,1,-1};
const int N=100010;

int main()
{
    IOS;
    int k,n;cin>>k>>n;
    int mx=0;
    for(int i=0;i<n;i++)
    {
        int a;cin>>a;
        mx=max(a,mx);
    }
    k-=mx;
    if(mx>k)cout<<mx-k-1<<endl;
    else cout<<0<<endl;
}








Measured memory_bytes: 256
import java.io.*;

public class Main{
	public static void main(String args[]) throws IOException{
		InputStreamReader is = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(is);

		String str = br.readLine();

		int x = Integer.parseInt(str);


		System.out.println(x * x * x);

		
	}
}

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

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


vector<int> G[100010], RG[100010];
int dp[100010];
int dp2[100010];

int dfs3(int r){
  if( dp2[r] != -1 ) return dp2[r];
  int ans = 0;
  for( auto i : RG[r] ){
    ans = max(ans, dfs3(i) + 1);
  }
  return dp2[r] = ans;
}


int dfs(int r){
  if( dp[r] != -1 ) return dp[r];
  int ans = 0;
  for( auto i : G[r] ){
    ans = max(ans, dfs(i) + 1);
  }
  return dp[r] = ans;
}

int res[100010];

void dfs2(int r,int d ){
  //cout << r + 1 << "<" << endl;
  //cout << dfs(r) << " " << dfs3(r) << endl;
  for( auto i : G[r]){
    if( d + 1 == dfs3(i) ){
      assert(res[i] == -1);
      res[i] = r;
      dfs2(i, d + 1);
    }
  }
}


void solve(long long N, long long M, std::vector<long long> A,
           std::vector<long long> B) {
  memset(dp, -1, sizeof(dp));
  memset(dp2, -1, sizeof(dp2));


  for(int i = 0 ; i < A.size() ; i++) {
    G[A[i] - 1].push_back(B[i] - 1);
    RG[B[i]-1].push_back(A[i]-1);

  }

  memset(res, -1, sizeof(res));
  int mx = -1, root;
  for(int i = 0 ; i < N ; i++){
    if( mx < dfs(i) ) {
      mx = dfs(i);
      root = i;
    }
    //cout << i+1 << ": " << dfs(i) << " " << dfs3(i) << endl;
  }
  res[root] = -1;
  dfs2(root, 0);
  for(int i = 0 ; i < N ; i++)
    cout << res[i] + 1 << endl;




}

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


Measured memory_bytes: 20864
#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <queue>
#include <bits/stdc++.h>
#include <stack>
#include <vector>
#include <list>
#define NUMBER 100000001

using namespace std;

int main(){

  list<int> S;
  string s;
  cin >> s;
  for(int i = 0; i < s.length(); i++){
    char t=0;
    t = s.c_str()[i];
    if(t=='0')
      S.push_back(0);
    else if(t=='1')
      S.push_back(1);
    else{
      if(S.size()>0)
        S.pop_back();
    }
  }
  int n = S.size();
  while(n){
    int t = S.front();
    cout << t;
    S.pop_front();
    n--;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, a, n) for(int i=a; i<n; i++)
#define ll long long
#define all(x) begin(x), end(x)
#define toInt(x) (x - '0')
#define pll pair<ll, ll>
#define pli pair<ll, int>

const long long INF = 1LL<<60;
const int inf = 1 << 30;
const int mod = 1e9+7;


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


vector<pair<ll, int>> factrized(ll num){
  vector<pair<ll, int>>  res;
 
  for(ll i = 2; i * i <= num; i++){
    if(num % i)continue;
    res.emplace_back(i, 0);
    while(num % i == 0){
      num /= i;
      res.back().second++;
    }
  }
  if(num != 1) res.emplace_back(num, 1);
  return res;
}

bool solve(vector<pair<ll, int>> vp){

  if(vp.size() == 1 && (vp[0].first == 1 || vp[0].first == -1)){
    return true;
  }
  if(vp.size() == 1 && vp[0].second == 5){
    return true;
  }
  return false;
}

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

  // long long x_abs = abs(x);
  // long long ans_a = 0;
  // long long ans_b = 0;
  // for(int i=0; pow(i, 5) <= 1e+9; i++){
  //   long long a = pow(i, 5);
  //   long long b = a - x_abs;

  //   vector<pair<ll, int>> vp = factrized(b);

  //   if(solve(vp)){
  //     ans_a = i;
  //     ans_b = vp[0].first;
  //   }
  // }

  // if(x < 0){
  //   swap(ans_a, ans_b);
  // }
  // cout << ans_a << " " << ans_b << endl;

  // cout << pow(ans_a, 5) - pow(ans_b,5) << endl;
  string s;
  cin >> s;
  if (s == "ABC"){
    cout << "ARC" << endl;
  }else{
    cout << "ABC" << endl;
  }
}



Measured memory_bytes: 3524
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
template <class T> inline void dump(T &v){irep(i, v){cout<<*i<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-11;


// (a/b)%P の場合は，(a%P)*modinv(b)%P とする
ll modinv(ll a) {
    ll b = MOD, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}

ll kai(ll X){
    ll res=1;
    for(ll i=1;i<=X;i++){
        res*=i;
        res%=MOD;
    }
    return res;
}

int main() {

    ll x,y;
    cin>>x>>y;
    ll A=(2*x-y)/3;
    ll B=(2*y-x)/3;
    if((2*x-y)<0||(2*y-x)<0||(2*x-y)%3!=0||(2*y-x)%3!=0){
        fin(0);
        return 0;
    }
    ll ans=kai(A+B);
    ll bo=kai(A)*kai(B);
    bo%=MOD;
    cout<<ans*modinv(bo)%MOD<<endl;
    
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
  using namespace std;
 
int main(){
  int N;
  cin>>N;
  int count=0;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      for(int k=1;k<=N;k++){
        count++;
      }
    }
  }
  cout<<count<<endl;
}

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

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

using namespace std;
using ll = long long;

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

  int res = 0;
  rep(1, (int)a.size()) if(i % 2 == 1 && a.at(i) % 2 == 1) ++res;
  cout << res << endl;
}

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

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	int x,y;
	if(a>=b&&a>=c){x=b;y=c;}
	if(b>=a&&b>=c){x=a;y=c;}else{
		x=a;y=b;
	}
	cout<<(x*y)/2<<endl;
	// your code goes here
	return 0;
}

Measured memory_bytes: 256