akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;

ll n,m,k,a[N],b[N],ans,psuma[N],psumb[N];


bool ok(ll x,ll tim){
	return psumb[x]<=tim;
}
ll getb(ll tim){
	ll l=0, r=m;
	ll ans=0;
	//最好记忆，while是含=
	while(l<=r){
		ll mid=(r+l)/2;
		if(ok(mid,tim)) ans=mid, l=mid+1;
		else r=mid-1;
	}
	//ans已经记录
	return ans;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]), psuma[i]=psuma[i-1]+a[i];
	for(int i=1;i<=m;i++) scanf("%lld",&b[i]), psumb[i]=psumb[i-1]+b[i];
	
	for(ll i=0;i<=n&&psuma[i]<=k;i++){
		ans=max(ans,i+(upper_bound(psumb,psumb+m+1,k-psuma[i])-psumb-1));
	}
	cout<<ans<<endl;
	return 0;
}

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

int
main()
{
	string a1, a2;
	cin >> a1 >> a2;
	if (a1[0]==a2[2] && a1[1]==a2[1] && a1[2]==a2[0]) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  int a = t.size();
  if(s < t){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
	
}

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

using namespace std;

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define INF (int)1e9  //
#define LINF (ll)4e18  //
#define MOD (1e9)+7
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

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

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    YES(a[a.length() - 1] == b[0] && b[b.length() - 1] == c[0]);

    return 0;
}



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

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, z, w;
  cin >> n >> z >> w;
  vector<int> a(n);
  for (auto& e : a) {
    cin >> e;
  }
  if (n == 1) {
    cout << abs(a[0] - w) << "\n";
    return 0;
  }
  cout << max(abs(a[n-2] -a[n-1]), abs(a[n-1] - w)) << "\n";
}


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

using namespace std;

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

  int max_a = 0;
  vector<pair<int, int>> vec(n);
  for (auto &v : vec) {
    int a, b;
    cin >> a >> b;
    v = make_pair(a, b);
    max_a = max(max_a, a);
  }

  sort(vec.begin(), vec.end(),
       [](auto &lhs, auto &rhs) { return lhs.second > rhs.second; });

  int cnt = 0;
  for (auto &v : vec) {
    int a = v.first;
    int b = v.second;
    if (max_a < b) {
      h -= b;
      ++cnt;
    }
    if (h <= 0)
      break;
  }
  if (0 < h)
    cnt += h / max_a + (h % max_a != 0);
  cout << cnt << endl;
}


Measured memory_bytes: 4044
import java.util.Scanner;
 
public class Main {
 
	static final boolean debugMode = false;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		String s = sc.next();
		if (s.charAt(2) == s.charAt(3) && s.charAt(4) == s.charAt(5)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
 
	static int readInt(Scanner sc) {
		return Integer.parseInt(sc.next());
	}
 
	static void log(String s) {
		if (debugMode) {
			System.out.println(s);
		}
		return;
	}
}
 
class Pair {
	private int x;
	private int y;
 
	public int getX() {
		return x;
	}
 
	public void setX(int x) {
		this.x = x;
	}
 
	public int getY() {
		return y;
	}
 
	public void setY(int y) {
		this.y = y;
	}
 
	public Pair() {
 
	}
 
	public Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}
 
}

Measured memory_bytes: 23764
import sys
import heapq
import bisect
import itertools

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def LI_(): return([int(x)-1 for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    N = I()
    A = LI()

    IA = [[i+1,A[i]] for i in range(N)]
    IA.sort(key = lambda x: x[1])

    print(*[IA[i][0] for i in range(N)])

if __name__ == "__main__":
    main()


Measured memory_bytes: 74384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	
	int hasil=0;
	
	if (a>b)
	{
		hasil= hasil+a;
		a--;
	}
	else
	{
		hasil= hasil+b;
		b--;
	}
	
		if (a>b)
	{
		hasil= hasil+a;
		a--;
	}
	else
	{
		hasil= hasil+b;
		b--;
	}
	
	cout<<hasil<<"\n";
	return 0;
}

Measured memory_bytes: 256
using System;
class Program
 {
   	static void Main(string[] args)
        {
    　　	string a = Console.ReadLine(); //標準入力
		string[] aa = a.Split(' ');
		
	       	int X = int.Parse(aa[0]);
       		int Y = int.Parse(aa[1]);

      
      bool test = (2*X <=Y&& Y<=4*X&&Y%2==0);
		if(test){
     		Console.WriteLine("{0}", "Yes");
        }else{
          Console.WriteLine("{0}", "No");
        }
		
        }
 
  	
	static void changev(int h){
    
  	}
 }

Measured memory_bytes: 27500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll a, b, c;
    cin >> a >> b >> c;

    ll x = c - a - b;
    if(x < 0) {
        cout << "No" << endl;
        return 0;
    }
    if((4 * a * b) < x * x) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 1000000000
#define eps 1e-7
#define mod 1000000007
#define int ll
using namespace std;

int A[100000 + 10];
int dp[50][2]; //dp[d][smaller?]:上から，2^dの位まで決定した時の，暫定スコアの最小値 
//smaller=1：以降の桁について自由に決められる 
//smaller=0:以降の桁について自由に決められない

signed main(void) {
    int N, K;
    cin >> N >> K;
    rep(i, N) {
        cin >> A[i];
    }
    rep(i, 50) {
        dp[i][0] = 0;
        dp[i][1] = 0;
    }
    if (K==0) {
        cout << accumulate(A, A+N, 0LL) << endl;
        return 0;
    }
    /* まず,Kの最高位を発見する */
    int d;
    int ans = 0;
    for (d = 45; d >= 0; d--) {
        if ((1LL<<d & K) > 0) break;
        else {
            rep(i, N) {
                if ((A[i] & 1LL<<d) > 0) ans += (1LL<<d);
            }
        }
    }
    int bit_cnt = 0;
    rep(i, N) {
        if ((A[i] & 1LL<<d) > 0) bit_cnt++;
    }
    /* ここに0を置く場合 */
    dp[d][1] = (1LL<<d) * bit_cnt;
    /* ここに1を置く場合 */
    dp[d][0] = (1LL<<d) * (N-bit_cnt);
    for (int i=d-1; i>=0; i--) {
        bit_cnt = 0;
        rep(j, N) {
            if ((A[j] & 1LL<<i) > 0) bit_cnt++;
        }
        if ((1LL<<i & K) > 0) { //bitが立ってる
            dp[i][0] = dp[i+1][0] + (1LL<<i) * (N-bit_cnt);
            dp[i][1] = max(dp[i+1][1] + (1LL<<i) * max(bit_cnt, N-bit_cnt), dp[i+1][0] + (1LL<<i) * bit_cnt);
        } else {
            dp[i][0] = dp[i+1][0] + (1LL<<i) * bit_cnt;
            dp[i][1] = dp[i+1][1] + (1LL<<i) * max(bit_cnt, N-bit_cnt);
        }
    }
    
    // REP(i, 0, d) {
    //     printf("dp[%lld][0]=%lld, dp[%lld][1]=%lld\n", i, dp[i][0], i, dp[i][1]);
    // }

    cout << max(dp[0][0], dp[0][1]) + ans << endl;
    
    return 0;
}

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

int main() {
  int a, A, b, B;
  scanf("%d%d%d%d", &a, &A, &b, &B);

  int x = b-a; int y = B-A;

  printf("%d %d %d %d\n", b-y, B+x, a-y, A+x);
}

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

int main() {
  long long n;
  long long ans=0;
  cin >> n;

  for (long long i = 1; i <= n; i++) {
    long long k = n/i;
    ans += k*(k+1)*i/2;
  }
  cout << ans << endl;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    int a, b;
    char op;
    cin >> a >> op >> b;

    cout << (op == '+' ? a + b : a - b) << '\n';
    return 0;
}


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

typedef long long   ll;
typedef long double ld;
using namespace std;

int main() {
    ll n,k;
    cin >> n >> k;
    ll tk=k;
    ll ans;
    if(k%2!=0){
        ll ca=n/k;
        ans=pow(ca,3);
    }
    else{
        ll cb=n/k;
        ll cc=n/(k/2)-cb;
        ans=pow(cb,3)+pow(cc,3);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<climits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
int x,t;
int main(){
  scan(x);scan(t);
  prin(max(0,x-t));
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

const int MAX_N=100010;

int par[MAX_N];
int ranks[MAX_N];
ll usize[MAX_N];
int size_UF;

void init(int n){
    size_UF=n;
    for(int i=0; i<n; i++){
        par[i]=i;
        ranks[i]=0;
        usize[i]=1;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }
    else{
        return par[x]=find(par[x]);
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

void unite(int x, int y){
    x=find(x);
    y=find(y);
    if(x == y) return;
    size_UF--;

    int tmp=usize[x];
    usize[x]+=usize[y];
    usize[y]+=tmp;

    if(ranks[x] < ranks[y]){
        par[x]=y;
    }
    else{
        par[y]=x;
    }
    
    if(ranks[x] == ranks[y]){
        ranks[x]++;
    }

}

int main(){
    ll n, m; cin>>n>>m;
    init(n);
    vector<int> a(m), b(m);
    for(int i=0; i<m; i++){
        cin>>a[i]>>b[i];
        a[i]--, b[i]--;
    }

    ll sum=n*(n-1)/2;
    vector<ll> ans(m);
    for(int i=m-1; i>=0; i--){
        ans[i]=sum;
        //cout << usize[find(a[i])] << " " << usize[find(b[i])] << endl;
        if(same(a[i], b[i]));
        else sum-=(usize[find(a[i])]*usize[find(b[i])]);
        unite(a[i], b[i]);
    }

    for(int i=0; i<m; i++){
        if(ans[i]<=0) cout << 0 << endl;
        else cout << ans[i] << endl;
    }
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
    #define rep(i,n) for (ll i = 0; i < n; ++i)
    using namespace std;
     
    typedef uint64_t ll;
     
    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
    const int INF = 1001001001;   
    int dp[105][105]; 
     
    int main() {
      cin.tie(0);
      ios::sync_with_stdio(false);
     
      int h, w;
      cin >> h >> w;
     
      vector<string> s(h);
      rep(i, h) cin >> s[i];
      rep(i, h) rep(j, w) dp[i][j] = INF;
      if (s[0][0] == '#') dp[0][0] = 1;
      else dp[0][0] = 0;
      rep(i, h) rep(j, w) {
        if (j < w -1) {                  // right
          if (s[i][j] == s[i][j+1]) {
            chmin(dp[i][j+1], dp[i][j]);
          } else {
            chmin(dp[i][j+1], dp[i][j] + 1);
          }
        }
        if (i < h - 1) {                // down
          if (s[i][j] == s[i+1][j]) {
            chmin(dp[i+1][j], dp[i][j]);
          } else {
            chmin(dp[i+1][j], dp[i][j] + 1);
          }
        }
      }
     
      if (s[h-1][w-1] == '#') dp[h-1][w-1]++;
     
      cout << dp[h-1][w-1] / 2 << endl;
     
      return 0;
    }

Measured memory_bytes: 384
// 2011/03/18 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int H, W;
		cin >> H >> W;
		if(H==0&&W==0)
			break;

		char rct[502][502];
		for(int i=0; i<=H+1; i++)
			for(int j=0; j<=W+1; j++)
				rct[i][j] = '*';

		for(int i=1; i<=H; i++)
			for(int j=1; j<=W; j++)
				cin >> rct[i][j];

		short wh[502][502][2];

		for(int i=1; i<=H; i++)
			for(int w=0, j=1; j<=W; j++)
				if(rct[i][j]=='*')
					wh[i][j][0] = w = 0;
				else
					wh[i][j][0] = ++w;

		for(int j=1; j<=W; j++)
			for(int h=0, i=1; i<=H; i++)
				if(rct[i][j]=='*')
					wh[i][j][1] = h = 0;
				else
					wh[i][j][1] = ++h;

		int rct_max = -1;
		for(int i=H; i>=1; i--){
			for(int j=W; j>=1; j--){
				if(wh[i][j][0]*wh[i][j][1]<=rct_max)
					continue;
				if(wh[i][j][0]>rct_max)
					rct_max = wh[i][j][0];
				if(wh[i][j][1]>rct_max)
					rct_max = wh[i][j][1];
				if(rct[i-1][j]=='.'&&rct[i][j-1]=='.'&&rct[i-1][j-1]=='.')
					for(int w2 = wh[i][j][0], h2=1; h2<=wh[i][j][1]; h2++){
						if(wh[i-h2+1][j][0]<w2)
							w2 = wh[i-h2+1][j][0];
						if(w2*h2>rct_max)
							rct_max = w2*h2;
					}
			}
		}

		cout << rct_max << endl;
	}

	return 0;
}

Measured memory_bytes: 2096
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<(n);i++)
#define init(a,i) for(int k=0;k<(i);k++)(a)[k]=0
#define in(a,i) for(int k=0;k<(i);k++)cin>>(a)[k]
#define all(a)  (a).begin(),(a).end()
#define el(a) (a).end()-(a).begin()
#define mod 1000000007
#define inf 2147483647
ll extGCD(ll a,ll b,ll &x,ll &y) {
    if(b==0){
       x=1;
       y=0;
       return a;
    }
    ll d=extGCD(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

ll mod_inv(ll a){//aの逆元
	ll x,y;
	extGCD(a,mod,x,y);
	return x%mod;
}

ll conbination(ll n,ll k){
	ll a=1,b=1;
	rep(i,k){
		a=a*(n-i)%mod;
		b=b*(i+1)%mod;
	}
	return a*mod_inv(b)%mod;
}	
int main(){
	ll X,Y;
	cin>>X>>Y;
	if((X+Y)%3||X>2*Y||Y>2*X){
		cout<<0;
		return 0;
	}
	ll times=(X+Y)/3;
	X-=times;
	Y-=times;
	ll ans=conbination(times,X);
	if(ans<0)ans+=mod;
	cout<<ans;
	return 0;
}

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

int main() {
	cout.precision(10);
	cout << fixed;
	int n, k;
	cin >> n >> k;
	double prob = max(0.0, (n - k + 1.0) / n);
	for (int x = 1; x <= min(n, k - 1); ++x) {
		int pow2 = 1;
		while (x * pow2 < k) pow2 <<= 1;
		prob += 1.0 / (n * pow2);
	}
	cout << prob << endl;
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  string pos = "No";
  for (int i = 1; i < 10; i++){
    if (n % i == 0 && (n / i) < 10){
      pos = "Yes";
      break;
    }
  }
  cout << pos;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000010
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,k;
	string ar;
	cin>>n>>k>>ar;
	if(ar[k-1]=='A') ar[k-1]='a';
	if(ar[k-1]=='B') ar[k-1]='b';
	if(ar[k-1]=='C') ar[k-1]='c';
	cout<<ar;
	return 0;
}

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

int main() {
  int n;
  cin>>n;
  vector<int> a;
  for(int i=0; i<n; i++){
    int x; cin>>x;
    if(x%2==0) a.push_back(x);
  }
  for(int i=0; i<a.size(); i++){
    if(a[i]%3 != 0 && a[i]%5 != 0) {
      cout<<"DENIED";
      return 0;
    }
  }
  cout<<"APPROVED";
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
const int Maxn=200000+20,inf=0x3f3f3f3f;
int a[Maxn],n,ans;
stack <int> s;
int main()
{
//	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	s.push(0);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		if(a[i]==s.top()+1)s.push(a[i]);
	}
	ans=s.size()-1;
	if(!ans)puts("-1");
	else printf("%d\n",n-ans);
	
	return 0;
}

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

#define ll long long
#define endl "\n"
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);


void solve() {

    int n;
    cin >> n;

    cout << (1000-(n%1000))%1000 << endl;

   


}


int32_t main()
{

    IOS

    int T;
    T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }




}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = 1e9 + 2;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

int main(void){
    int n, T; cin >> n >> T; T /= 2;
    vi a(n); for(auto & e : a) cin >> e;

    map<int, int> cnt_bk;
    int X = 0;
    int vmin = inf;
    for(auto & e : a){
        cnt_bk[e]++;
        chmin(vmin, e);
        chmax(X, e - vmin);
    }

    int res = 0;
    map<int, int> cnt_fr;
    for(auto & e : a){
        if(cnt_bk[e] == 0) continue;

        if(cnt_fr[e - X] >= 1){
            if(cnt_fr[e - X] < cnt_bk[e]){
                res += cnt_fr[e - X];
                cnt_fr[e - X] = 0;
            }
            else {
                res += cnt_bk[e];
                cnt_bk[e] = 0;
            }
        }

        cnt_fr[e]++;
        cnt_bk[e]--;
    }

    cout << res << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    int n;cin>>n;
    cout<<n/3<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  long long n,cnt=0,tmp,ans=0,min=10000000;
  int a[100001];
  min=1000000;
  scanf("%lld",&n);
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
//    min=(min>abs(a[i]))?abs(a[i]):min;
    if(a[i]<0) {
      cnt++;
      a[i]=-1*a[i];
    }
 //   printf("%d\n",a[i]);
    if(min>a[i]){
      min=a[i];
    }
 //   printf("%lld\n",min);
    ans+=a[i];
  }
  if(cnt%2==0){
    printf("%lld",ans);
    return 0;
  }
  else {
//    printf("%lld\n",min);
    printf("%lld",ans-2*min);
  }
  return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
typedef long long ll;
char txt[4];
int gcd(int a, int b){
	return a%b?gcd(b,a%b):b;
}
int main(){
	int SW = 1;
	if(SW == 0){
		scanf("%s",txt);
		bool f = false;
		for(int i=0;i<3;i++) f|=txt[i]=='7';
		printf("%s",f?"Yes":"No");
	}
	else if(SW==1){
		ll N;scanf("%lld",&N);
		ll ret = N*(N+1)/2;
		ret -= 3*(N/3)*(N/3+1)/2;
		ret -= 5*(N/5)*(N/5+1)/2;
		ret += 15*(N/15)*(N/15+1)/2;
		printf("%lld",ret);
	}
	else{
		ll K;scanf("%lld",&K);
		ll sum=0;
		for(ll i=1;i<=K;i++){
			for(int j=1;j<=K;j++){
				for(int k=1;k<=K;k++){
					sum+=gcd(gcd(i,j),k);
				}
			}
		}
		printf("%lld",sum);
	}
}

Measured memory_bytes: 1736
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vector<int> h(N);
    rep(i, N) cin >> h[i];

    vector<int> dp(N, 2e9);
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    rep(i, 2, N) dp[i] = min(dp[i - 2] + abs(h[i - 2] - h[i]), dp[i - 1] + abs(h[i - 1] - h[i]));

    write(dp[N - 1]);
}

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

int dp[20001];

int f(int p, int x) {
  for (int i = 20000; i >= 0; --i) {
    if (dp[i]) {
      for (int j = 1; j <= x; ++j) {
        if ((i + (j * p)) <= 20000)
          dp[i + (j * p)] += dp[i];
      }
    }
  }
}

int main() {
  memset(dp, 0, sizeof(dp));
  dp[0] = 1;

  int A, B, C, X;
  cin >> A >> B >> C >> X;
  f(500, A);
  f(100, B);
  f(50, C);
  cout << dp[X] << endl;
  return 0;
}


Measured memory_bytes: 384
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    string T;
    cin >> T;

    int ans = 0;
    REP(i, T.size()) {
        if (T[i] == '?') cout << 'D';
        else cout << T[i];
    }
    cout << endl;
    
}


Measured memory_bytes: 3792
//	-*- mode: C++ -*-
//	Dice III
//
//		Write a program which reads the two dices constructed in the same way as Dice I, and determines whether these two dices are identical. You can roll a dice in the same way as Dice I, and if all integers observed from the six directions are the same as that of another dice, these dices can be considered as identical.
//
//	Input
//		In the first line, six integers assigned to faces of a dice are given in ascending order of their corresponding labels.
//		In the second line, six integers assigned to faces of another dice are given in ascending order of their corresponding labels.
//
//	Output
//		Print "Yes" if two dices are identical, otherwise "No" in a line.
//
//	Constraints
//		0≤ the integer assigned to a face ≤100
//	Sample Input 1
//		1 2 3 4 5 6
//		6 2 4 3 5 1
//	Sample Output 1
//		Yes
//
//	Sample Input 2
//		1 2 3 4 5 6
//		6 5 4 3 2 1
//	Sample Output 2
//		No

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <climits>

const unsigned int	faces	{6};

void	E(std::vector<unsigned int>& dice);
void	S(std::vector<unsigned int>& dice);
void	rotate(std::vector<unsigned int>&	dice);

bool	isSameDice(std::vector<unsigned int>&				diceA,
				   std::vector<unsigned int>&				diceB);

int main(int	argc,
		 char*	argv[])
{
	std::vector<unsigned int>	diceA	{};
	diceA.resize(faces, 0);

	for(unsigned int i = 0; i < faces; i++){
		std::cin >> diceA[i];
	}

	std::vector<unsigned int>	diceB	{};
	diceB.resize(faces, 0);

	for(unsigned int i = 0; i < faces; i++){
		std::cin >> diceB[i];
	}

	std::cout << (isSameDice(diceA, diceB) ? "Yes" : "No") << '\n';

    return 0;
}

void	E(std::vector<unsigned int>& dice)
{
	unsigned int	x	= dice[0];
	dice[0]	= dice[3];
	dice[3]	= dice[5];
	dice[5]	= dice[2];
	dice[2]	= x;
}

void	S(std::vector<unsigned int>& dice)
{
	unsigned int	x	= dice[0];
	dice[0]	= dice[4];
	dice[4]	= dice[5];
	dice[5]	= dice[1];
	dice[1]	= x;
}

void	rotate(std::vector<unsigned int>&	dice)
{
	unsigned int	x	= dice[1];
	dice[1]	= dice[2];
	dice[2]	= dice[4];
	dice[4]	= dice[3];
	dice[3]	= x;
}

bool	isSameDice(std::vector<unsigned int>&	diceA,
				   std::vector<unsigned int>&	diceB)
{
	bool	isMatch	{false};

	// 前方向に一回転させる
	for(unsigned int i = 0; i < 4; i++){
		S(diceB);

		// 一回転がす毎に一致判定
		isMatch	= std::equal(diceA.begin(), diceA.end(), diceB.begin());

		if(isMatch){	// 一致したら終了
			return	isMatch;
		}

		// 一致しなかったら、横方向に一回転させながら一致判定
		for(unsigned int j = 0; j < 4; j++){
			rotate(diceB);

			isMatch	= std::equal(diceA.begin(), diceA.end(), diceB.begin());

			if(isMatch){	// 一致したら終了
				return	isMatch;
			}
		}
	}

	// 前方向に一回転させても一致しない場合は右方向に一回転
	for(unsigned int i = 0; i < 4; i++){
		E(diceB);

		// 一回転がす毎に一致判定
		isMatch	= std::equal(diceA.begin(), diceA.end(), diceB.begin());

		if(isMatch){	// 一致したら終了
			return	isMatch;
		}

		// 一致しなかったら、横方向に一回転させながら一致判定
		for(unsigned int j = 0; j < 4; j++){
			rotate(diceB);

			isMatch	= std::equal(diceA.begin(), diceA.end(), diceB.begin());

			if(isMatch){	// 一致したら終了
				return	isMatch;
			}
		}
	}

	return	isMatch;
}



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

int main(){
    long long n;
    cin >> n;
    long long a[n],b[n],count=0;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    for(int i=0;i<n;i++) count += b[i]-a[i];
    long long res=0;
    for(int i=0;i<n;i++){
        if(a[i]<b[i]) res+=(b[i]-a[i]+1)/2;
    }
    if(res<=count) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <iomanip>
#include <math.h>
#include <algorithm>
#define hmm "\n"
#define test() int t; cin>>t; while(t--)
#define ll long long int
#define ull unsigned long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
void solve()
{
    ll n,m;
    cin>>n>>m;
    ll a[n],b[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
        b[i]=a[i]/2;
    }
    ll o=b[0];
    for(int i=1; i<n; i++){
        o=(o*b[i])/__gcd(o,b[i]);
    }
    for(int i=0; i<n; i++){
        if(o%a[i] != b[i]){
            cout<<"0\n";
            return;
        }
    }
    ll r= m/o;
    cout<<(r+1)/2<<hmm;
    
}
int main()
{
    fastIO
    //test()
    solve();
}


Measured memory_bytes: 5188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N, T;
    cin >> N >> T;
    vector<iint> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i].first >> A[i].second;
    }
    sort(ALL(A));

    vector<vector<int>> dp(N+1, vector<int>(T));
    int ans = 0;
    for (int i = 0; i < N+1; i++) {
        dp[i][0] = 0;
    }
    for (int i = 0; i < T; i++) {
        dp[0][i] = 0;
    }
    for (int n = 1; n < N+1; n++) {
        for (int t = 1; t < T; t++) {
            if(t - A[n-1].first >= 0){
                dp[n][t] = max(dp[n-1][t], dp[n-1][t-A[n-1].first] + A[n-1].second);
            }
            else{
                dp[n][t] = dp[n-1][t];
            }
        }
        for (int t = T; t < T+A[n-1].first; t++) {
            if(t - A[n-1].first >= 0){
                ans = max(ans, dp[n-1][t-A[n-1].first] + A[n-1].second);
            }
        }
    }

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

}

Measured memory_bytes: 38568
#include <iostream>
#include <vector>
#include <string>
#define INF 1000000007
using namespace std;
typedef long long ll;

int dp[26][100000] = {};

void init(string &s, int arr[26]) {
	for(int i = 0; i < s.size(); i++) {
		char c = s[i];
		arr[c-'a']++;
	}
}

int main() {
	string s,t;
	cin>>s>>t;

	int s_arr[26] = {};
	int t_arr[26] = {};
	init(t,t_arr);
	init(s,s_arr);
	for(int i = 0; i < 26; i++) {
		if(s_arr[i]==0&&t_arr[i]>0) {
			cout << -1 << endl;
			return 0;
		}
	}

	for(char c = 'a'; c <= 'z'; c++) {
		int start = -1;
		for(int i = 0; i < s.size(); i++) {
			if(s[i]==c) start = i;
		}
		if(start==-1) continue;
		int cnt = s.size();
		for(int i = 0; i < s.size()*2; i++) {
			int index = (start-i+s.size()*2)%s.size();
			dp[c-'a'][index] = cnt;
			if(s[index]==c) cnt=0;
			cnt++;
		}
	}

	int start = -1;
	for(int i = 0; i < s.size(); i++) {
		if(s[i]==t[0]) {
			start = i;
			break;
		}
	}
	ll ans = 0;
	ans += start+1;
	for(int i = 1; i < t.size(); i++) {
		char c = t[i];
		int num = dp[c-'a'][start];
		ans += num;
		start = (start+num)%s.size();
	}
	cout << ans << endl;
}


Measured memory_bytes: 10752
from collections import deque



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

D = [-1]*(N+1)
#S=[[0] * 3 for _ in range(2)] 2行3列の場合
S = [[]for i in range(N+1)]
deq=deque()

    


for i in range(M):
    A,B=map(int,input().split())
    
    S[A].append(B)
    S[B].append(A)
ans=0
for i in range(1,N+1):
    deq.append(i)
    count=0
    #D = [-1]*(N+1)
    while len(deq)!=0:
        v= deq.popleft()
        for nv in S[v]:
            if D[nv] !=-1:
                continue
            D[nv] =D[v]+1
            deq.append(nv)
            count+=1
    if count>ans:
        ans=count


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


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

const int INF = 1e9;
int c[3][3];

bool check() {
  if (c[0][0]-c[1][0] != c[0][1]-c[1][1]){
    return false;
  }
  if (c[0][0]-c[1][0] != c[0][2]-c[1][2]){
    return false;
  }
  if (c[1][0]-c[2][0] != c[1][1]-c[2][1]){
    return false;
  }
  if (c[1][0]-c[2][0] != c[1][2]-c[2][2]){
    return false;
  }
  return true;
}
int main() {
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>c[i][j];
    }
  }
  if (check()) {
    cout<<"Yes"<<endl;
  } else {
    cout<<"No"<<endl;
  }

}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

int main(){

  int N;
  int W[100];
  int i,j;
  int S1,S2;
  int min;

  S1=0;
  S2=0;
  
  scanf("%d", &N);

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

  min = 100 *N;
  
  for(i=0;i<N;i++){
    for(j=0;j<i;j++){
      S1 += W[j];
    }
    for(j=i;j<N;j++){
      S2 += W[j];
    }
    if(min > abs(S1 - S2)){
      min = abs(S1 -S2);
    }
    S1 = 0;
    S2 = 0;
  }

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

  return 0;
  
  
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K,a,b,s=1;
  cin >> N >> K;
  for (int i=0;i<N;i++){
    a = s * 2;
    b = s + K;
    if (a <= b){
      s = a;
    }else{
      s = b;
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 256
n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
L=[[0 for i in range(n)] for j in range(n)]
L2=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
  L[l[i][0]-1][l[i][1]-1]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    L2[i][j]=L2[i][j-1]+L[i-1][j-1]
for j in range(1,n+1):
  for i in range(1,n+1):
    L2[i][j]=L2[i-1][j]+L2[i][j]

p=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(L2[p[i][1]][p[i][1]]-L2[p[i][1]][p[i][0]-1]-L2[p[i][0]-1][p[i][1]]+L2[p[i][0]-1][p[i][0]-1])

Measured memory_bytes: 79356
#include <bits/stdc++.h>
using namespace std;
 
// #define int long long
 
/* short */
#define pb push_back
#define print(x) cout << x << '\n'
 
/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = 1; i <= (n); i++)
#define DEPS(i, a, n) for (int i = (a); i >= n; i--)
#define DEP(i, n) for (int i = (n); i >= 0; i--)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;

/* const */
const int INF = INT_MAX;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

/* func */
inline bool is_uruu(int y) {return (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));}

bool shinobu(string s)
{
  if (s == "/" || s == "*" || s == "+" || s == "-"){
    return (false);
  }

  return (true);
}

signed main()
{
  //ios::sync_with_stdio(false);
  string in;

  while (cin >> in){
    char c;
    stack<double> st;
    bool line = false;
    while (scanf("%c", &c), c == '\n' ? line = true : line = false, true){
      if (shinobu(in)){
        st.push(atof(in.c_str()));
        //cout << "tst: " << st.top() << endl;
      } else {
        double n1 = st.top(); st.pop();
        double n2 = st.top(); st.pop();
        if (in == "-"){
          st.push(n2 - n1);
        }
        if (in == "+"){
          st.push(n2 + n1);
        }
        if (in == "*"){
          st.push(n2 * n1);
        }
        if (in == "/"){
          st.push(n2 / n1);
        }
        //cout << "calc: " << n2 << in << n1 << "=" << st.top() << endl;
      }
      if (line) break;
      cin >> in;
    }
    printf("%f\n", st.top());
  }

  return (0);
}

Measured memory_bytes: 1276
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

int a, b, c, d, e, f, g;
ll sol = 0;

int main(){
	scanf("%d%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f, &g);
	if((d % 2 + e % 2 + a % 2) > 1 && d && e && a){
		d--; e--; a--;
		sol += 6LL;
	}
	sol += 2LL * b; b = 0;
	sol += 4LL * (e / 2LL);	
	sol += 4LL * (d / 2LL);
	d %= 2LL; e %= 2LL;
	sol += 4LL * (a / 2LL); a %= 2LL; 
	printf("%lld\n", sol / 2LL);
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;

int main(void){
  int n;
  while ((cin >> n) && n) {
    vector<bitset<100> > bit(n);
    REP(i, 0, n) {
      bitset<100> sol;
      int k;
      cin >> k;
      REP(j, 0, k) {
	int t;
	cin >> t;
	t--;
	sol[t] = true;
      }
      bit[i] = sol;
    }
    int k;
    cin >> k;
    bitset<100> leakage;
    REP(i, 0, k) {
      int t;
      cin >> t;
      t--;
      leakage[t] = true;
    }
    VI cand;
    REP(i, 0, n) {
      if ((bit[i] & leakage) == leakage) {
	cand.push_back(i);
      }
    }
    if (cand.size() != 1) {
      cout << -1 << endl;
    } else {
      cout << cand[0] + 1 << endl;
    }
      
  }
}

Measured memory_bytes: 3132
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

int main()
{
    int n, ans = 0;
    cin >> n;
    int v[n], c[n];
    rep(i,n) cin >> v[i];
    rep(i,n) cin >> c[i];
    rep(i,n)
    {
        int tmp = v[i]-c[i];
        if(tmp>0) ans += tmp;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(inti=a;i<=b;i++)

#define MOD 1000000009
typedef long long int ll;
typedef vector<int>vi;
typedef pair<int,int>pi;



int main()
{

int arr[3];

for(int index = 0 ; index<  3 ; index++)
    cin>>arr[index];

sort(arr,arr+3);

if(arr[0]!=arr[1])
    cout<<arr[0]<<endl;
else
    cout<<arr[2]<<endl;


 return 0;
}


Measured memory_bytes: 3648
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repR(i, n) for(int i = (n) - 1; i > -1; i--)
#define rep1(i, n) for(int i = 1; i < (int)(n + 1); i++)
#define rep1R(i, n) for(int i = (n); i > 0; i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main() {
  string S; cin >> S;
  if (S[0] != 'A') {
    cout << "WA" << endl;
    return 0;
  }
  bool found_c = false;
  int i_C;
  for (int i = 2; i < S.size() - 1; i++) {
    if (S[i] == 'C') {
      if (found_c) {
        cout << "WA" << endl;
        return 0;
      }
      found_c = true;
      i_C = i;
    }
  }
  if (!found_c) {
    cout << "WA" << endl;
    return 0;
  }
  rep(i, S.size()) {
    if (i == 0 || i == i_C) continue;
    if (S[i] < 'a' || S[i] > 'z') {
      cout << "WA" << endl;
      return 0;
    }
  }
  cout << "AC" << endl;
  return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll A[10];

int main()
{
    ll N;
    cin >> N;
    ll min = INF;
    REP(i, 5)
    {
        ll a;
        cin >> a;
        min = std::min(a, min);
    }

    cout << 4LL + (N + min - 1) / min << endl;
    return 0;
}

Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>

//#include <bits/stdc++.h>
using namespace std;
using LL = int;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourd; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, q, last, cnt, sum, ans, dp[10000][4], a[2000000], b[2000000];
string str, ss;
bool f[1100][1100];
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
struct Edge { LL to, cost; };
vector<Edge>vec[200000];
vector<LL>v;
map<Pll, LL>ma;
set<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
int main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i,n) {
		rep(j, 4) {
			dp[i][j] = INF;
		}
	}
	rep(j ,4) {
		dp[0][j] = j;
	}
	rep(i, n+1) {
		rep(j, 4) {
			rep(k, 4) {
				if (dp[i][j]!=INF) {
					if (j + k >= a[i])
						dp[i + 1][k] = min(dp[i][j] + k*2, dp[i + 1][k]);
				}
			}
		}
	}
	ans = INF;
	rep(j, 4)ans = min(ans,dp[n-1][j]+max(a[n-1]-j,0));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 7940
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define ll long long
# define ln cout<<'\n'
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
 
ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

int factorial(int n)
{
    int x = 1; // 0! = 1

    for (int i = 1; i <= n; ++i)
        x *= i;

    return x;
}

int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}


using namespace std;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    float x;
    cin >>x;
    float ans=1;
    for(int i=1;i<=x;i++){
        for(int j=2;j<=x;j++){
             float tmp  = pow(i,j);
            if (tmp <= x){
                ans = max(ans,tmp);
            }

        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
main = do
  str <- getLine
  let strs = foldr (\x acc -> (++) <$> x <*> acc) [""] [["A", ""], ["KIH"], ["A", ""], ["B"], ["A", ""], ["R"], ["A", ""]]
      can = str `elem` strs
  putStrLn $ if can then "YES" else "NO"


Measured memory_bytes: 380
#include  <bits/stdc++.h>
using namespace std;
static int fast_io = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
int main(){
  int n,k;
  cin>>n>>k;
  vector<bool> hasSnack(n);
  int ans=n;
  int amount,s; 
  for(int i = 0;i<k;i++){
    cin>>amount;
    for(int j = 0;j<amount;j++){
      cin>>s;
      if(!hasSnack[s]){
        hasSnack[s]=true;
        ans--;
      }  
    }
  }
  cout<<ans<<"\n";  
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
using ll = long long;
using ull = unsigned long long;
constexpr int MOD = 1000000007;

int mod(ll x){
    return x > 0 ? x % MOD : (x+MOD) % MOD;
}

int modm(ll x,ll m){
    return x * m % MOD;
}

int modpow(ll x, ll p) {
    int ret = 1;
    while(p > 0) {
        if (p & 1) ret = modm(ret,x);
        x = modm(x,x);
        p >>= 1;
    }
    return ret;
}

// x * modinv(d)
int modd(ll x,ll d) {
    return modm(x,modpow(d,MOD-2));
}

int main(void)
{
    IOS
    constexpr int N = 1e4;
    constexpr int M = 13;
    
    string s; cin >> s;
    int l = s.size();
    vector<vector<int>> dp(l+1,vector<int>(M,0));
    dp[0][0] = 1;

    REP(i,l) {
        REP(j,M) {
            REP(k,10) {
                if (s[i] - '0' == k || s[i] == '?') {
                    dp[i+1][(j*10 +k) % M] = mod(0LL + dp[i+1][(j*10 +k) % M] + dp[i][j]);
                }
            }
        }
    }

    cout << dp[l][5] << endl;

    return 0;
}

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

int dp[100005][5];

#undef int
int main()
{
#define int long long
   int n;
   cin >> n;

   int mat[n][3];
   for(int i=0;i<n;i++)
   {
      for(int j=0;j<3;j++)
      {
         cin >> mat[i][j];
      }
   }
   memset(dp,0,sizeof(dp));

   dp[0][0]=mat[0][0];
   dp[0][1]=mat[0][1];
   dp[0][2]=mat[0][2];

   for(int i=1;i<n;i++)
   {
      for(int j=0;j<3;j++)
      {
         if(j==0)
            dp[i][j]=mat[i][j]+max(dp[i-1][j+1],dp[i-1][j+2]);
         else if(j==1)
            dp[i][j]=mat[i][j]+max(dp[i-1][j-1],dp[i-1][j+1]);
         else
         {
            dp[i][j]=mat[i][j]+max(dp[i-1][j-1],dp[i-1][j-2]);
         }
      }
   }
   cout << max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]) << endl;
}

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

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int inv[N];

void add(int &x, int y) { 
    x += y;
    if (x >= MOD) x -= MOD;
}

int main() {
    inv[1] = 1;
    for (int n = 2; n < N; n++) {
        inv[n] = ll(MOD - MOD/n) * inv[MOD%n] % MOD;
        assert(ll(n)*inv[n]%MOD == 1);
    }
    for (int n = 2; n < N; n++) add(inv[n], inv[n-1]);

    int n, fact = 1, ans = 0; cin >> n;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        ll coef = (ll(inv[i+1]) + inv[n-i] + MOD - 1) % MOD;
        add(ans, coef * x % MOD);
        fact = (ll) fact * (i+1) % MOD;
    }
    cout << ll(ans)*fact%MOD << endl;
    return 0;
}


Measured memory_bytes: 640
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

MOD = 10**9 + 7

rui = []
rui[0]=a[0]
1.upto(n-1) do |i|
  rui[i] = rui[i-1] + a[i]
end

ans = 0
(n-1).times do |i|
  ans += a[n-i-1] * rui[n-i-2]
  ans %= MOD
end
p ans


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

int main(){

  ll n;
  cin >> n;
  vector<ll> a(n+1);
  vector<ll> b(n);
  for(ll i=0; i<n+1; i++) cin >> a[i];
  for(ll i=0; i<n; i++) cin >> b[i];
  
  vector<ll> z(n);
  copy(b.begin(), b.end(), z.begin());
  
  ll sum = 0;
  for(ll i=n-1; i>=0; i--){
    
    ll l1 = min(a[i+1], z[i]);
 	a[i+1] -= l1;
    z[i] -= l1;
    
    ll l2 = min(a[i], z[i]);
 	a[i] -= l2;
    z[i] -= l2;
    
    //cerr << i << " " << l1+l2 << endl;
    sum += (l1 + l2);
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl
#define ALL(a) (a).begin(),(a).end()
#define EACH(e,v) for(auto& e:v)
#define SORT(v) sort(ALL(v))
#define PERM(v) SORT(v);for(bool c##p=1;c##p;c##p=next_permutation(ALL(v)))
#define int long long
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }
template <class T> void chmax(T & a, T const & b) { if (b > a) a = b; }
template <typename T>
string to_string(const T &n){ostringstream stm;stm << n;return stm.str();}
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
using ll = long long;
const ll mod = 1000'000'007;

signed main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    
    int C=b/c-(a-1)/c;
    int D=b/d-(a-1)/d;
    dump(C);
    dump(D);
    int lc=c*d/__gcd(c,d);

    int L=b/lc-(a-1)/lc;
    dump(L);

    cout<<(b-a+1)-(C+D-L)<<endl;
 
}

Measured memory_bytes: 256