akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1e9
#define MAX_V 1001
using namespace std;
typedef map<int,int> M;
M G[MAX_V],rG[MAX_V],g[MAX_V];
bool used[MAX_V];  

int dfs(int v,int t,int f){
  if(v == t)return f;
  used[v]=true;
  
  for(M::iterator it=G[v].begin();it!=G[v].end() ;it++){
    int to=it->first;
    int &cap=it->second;
    if(!used[to] && cap > 0){
      int d = dfs(to ,t , min(f,cap));
      if(d > 0){
	cap -= d;
	G[to][v]+=d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s, t, INF);
    if(f == 0)return flow;
    flow += f;
  }
}

int visited[MAX_V];
void visit(int pos){
  if(visited[pos])return;
  visited[pos]=1;
  for(M::iterator it=rG[pos].begin();it!=rG[pos].end() ;it++){
    int to=it->first,cap=it->second;
    if(cap)visit(to);
  }
}

int check2(int pos){
  if(used[pos]++) return 0;
  int res=0; 
  for(M::iterator it=G[pos].begin();it!=G[pos].end() ;it++){
    int to=it->first,cap=it->second;
    if(cap)res+=check2(to);
  }
  
  for(M::iterator it=g[pos].begin();it!=g[pos].end() ;it++){
    int to=it->first,cap=it->second;
    if(cap)res+=cap*visited[to];
  }
  return res;
}

int main(){
  while(1){
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    if(!n&&!m&&!s&&!t)break;
    s--,t--;
    for(int i=0;i<MAX_V;i++) rG[i].clear(),G[i].clear(),g[i].clear();
    
    for(int i=0,a,b;i<m;i++){
      cin>>a>>b;
      a--,b--;
      G[a][b]++;
      g[b][a]++;
    }

    int mx=max_flow(s,t);
    for(int i=0;i<n;i++)
      for(M::iterator it=G[i].begin();it!=G[i].end() ;it++){
	int to=it->first,cap=it->second;
	rG[to][i]=cap;
      }
    
    memset(visited,0,sizeof(visited));
    memset(used,0,sizeof(used));
    visit(t);
    int cnt=check2(s);
    cout<<mx+(cnt>0)<<" "<<cnt<<endl;
  }
  
}

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

typedef long long ll;
typedef long double ld;

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

    ll N;
    cin >> N;

    map<ll, int> a;

    for(ll i = 2; i * i <= N; i++) {
        if(N % i == 0){
            while(N % i == 0) {
                a[i]++;
                N /= i;
            }
        }
    }

    if(N != 1) a[N]++;

    int ans = 0;

    for(auto i = begin(a); i != a.end(); i++) {
        int count = 1;
        while(i->second >= count) {
            ans++;
            i->second -= count;
            count++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3656
#include<cstdio>
#include<algorithm>
inline void read(int&r)
{
	register char c;r=0;
	do c=getchar();while(c<'0'||c>'9');
	do r=r*10+c-'0',c=getchar();while(c>='0'&&c<='9');
}

int a[100000],b[100000],c[100001],d[100000];
int fa[100001];bool vis[100001];
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
#define id(x) std::lower_bound(c,c+m,x)-c

int main()
{
	int i,j,n,m;read(n);
	for(i=0;i<n;i++)read(a[i]),c[i]=a[i],c[n]^=a[i];
	for(i=0;i<n;i++)read(b[i]),d[i]=b[i];
	int x=c[n];
	std::sort(c,c+n+1);
	std::sort(d,d+n);
	for(i=j=0;j<n;i++,j++)while(c[i]!=d[j])if(i==j)i++;else return puts("-1"),0;
	for(i=j=0;i<n;i++)j+=a[i]!=b[i];
	if(!j)return puts("0"),0;
	m=std::unique(c,c+n+1)-c,j--;
	for(i=0;i<m;i++)fa[i]=i;
	for(i=0;i<n;i++)fa[find(id(a[i]))]=find(id(b[i]));
	for(i=0;i<n;i++)if(a[i]!=b[i]&&!vis[find(id(a[i]))])vis[fa[id(a[i])]]=true,j++;
	if(!vis[find(id(x))])vis[fa[id(x)]]=true,j++;

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

Measured memory_bytes: 3712
n = int(input())
a = list(map(int, input().split()))
alice = 0
bob = 0
a.sort()
for i in range(n):
    if i%2==0:
        alice += a[-1]
        a.pop()
    elif i%2==1:
        bob += a[-1]
        a.pop()
print(alice-bob)

Measured memory_bytes: 3060
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
import threading
import sys
import time


def get_int(): return int(stdin.readline().strip())


def get_tuple(): return map(int, stdin.readline().split())


def get_list(): return list(map(int, stdin.readline().split()))

st = input()
if st[-1]=='s':
    print(st+'es')
else:
    print(st+'s')

Measured memory_bytes: 70480
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder bd = new StringBuilder();
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<q; i++) {
            int com = sc.nextInt();
            if (com == 0) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                a[x-1] += y;
            }
            else if (com == 1) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                long sum = 0;
                for (int j=x; j<=y; j++) {
                    sum += a[j-1];
                }
                bd.append(sum + "\n");
            }
        }
        System.out.print(bd);
    }
}


Measured memory_bytes: 101060
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int l,r,d;
	scanf("%d%d%d",&l,&r,&d);
	int sum = 0;
	for(int i = l;i <= r;i++){
		if(i % d == 0)
			sum++;
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 3708
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
#define pb push_back
 const ll mod = 1000000007;

 ll gdc(ll a, ll b) {
	 ll ta = a, tb = b;
	 if (a < b) {
		 ta = b;
		 tb = a;
	 }

	 ll r = ta % tb;
	 while (r != 0) {
		 ta = tb;
		 tb = r;
		 r = ta % tb;
	 }
	 return tb;
 }

ll a(ll n, ll c, ll d) {
	ll lcm = c * d / gdc(c, d);
	return n - n / c - n / d + n / lcm;
}

int main() {
	ll A, B, C, D;
	cin >> A >> B >> C >> D;

	cout << a(B, C, D) - a(A - 1, C, D) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;

#define rep(i,n)  for(int i = 0; i < (int)(n);    i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  ll N; std::cin >> N;
  std::vector<ll> A(N); rep(i,N) std::cin >> A[i];

  ll S = 0; rep(i,N) S += A[i];
  std::map<ll,ll> K;
  rep(i,N) K[ A[i] ]++;

  ll Q; std::cin >> Q;
  std::vector<ll> ans(Q);
  rep(i,Q) {
    ll B, C; std::cin >> B >> C;
    S -= B * K[ B ];
    S += C * K[ B ];
    ans[i] = S;
    K[C] += K[B];
    K[B] = 0;
  }
  for(auto&& a : ans) std::cout << a << std::endl;
  return 0;
}



Measured memory_bytes: 10848
/*
  桁DPによる解法
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
typedef long long ll;
using namespace std;

const int MAX_DIGIT = 50;
ll dp[100][2]; // dp[上からi桁目まで][smaller(kと一致しているかしていないか)]
/*
smaller = 0の時,Kとちょうど一致
smaller = 1の時,Kよりも小さい
*/
int main(){
  ll i,j,k,n,d,e;
  cin >> n >> k;
  std::vector<ll> a(n);
  for(i=0;i<n;i++)cin >> a[i];
  memset(dp,-1,sizeof(dp));
  dp[0][0] = 0;
  for(d=0;d<MAX_DIGIT;d++){
    ll mask = 1LL<<(MAX_DIGIT-d-1);
    ll cnt = 0;
    for(i=0;i<n;i++){
      if(a[i] & mask)cnt++;
    }
    ll cost0 = mask*cnt;
    ll cost1 = mask*(n-cnt);
    if(dp[d][0]!=-1){
      if(k & mask){
        dp[d+1][0]=dp[d][0]+cost1;
        dp[d+1][1]=dp[d][0]+cost0;
      }
      else dp[d+1][0]=dp[d][0]+cost0;
    }
    if(dp[d][1]!=-1){
      dp[d+1][1]=max(dp[d+1][1],dp[d][1]+max(cost0,cost1));
    }
  }
  cout << max(dp[MAX_DIGIT][0],dp[MAX_DIGIT][1]) << endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int a[500011][26];
int n;
int lowbit(int x){
	return x&-x;
}
int query(int x,int y){
	int res=0;
	for(int i=x;i;i-=lowbit(i)){
		res+=a[i][y];
	}
	return res;
}
void add(int x,int y,int v){
  for(int i=x;i<=n;i+=lowbit(i)){
	a[i][y]+=v;
}
}
int main(){
	int q;
	char s[500011];
	cin>>n;
	cin>>s+1>>q;
	for(int i=1;i<=n;i++){
		add(i,s[i]-'a',1);
	}
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			char b;
			int c;
			cin>>c>>b;
			add(c,s[c]-'a',-1);
			s[c]=b;
			add(c,s[c]-'a',1);
		}
		else{
			int l,r;
			cin>>l>>r;
			int ans=0;
			for(int i=0;i<26;i++)
			if(query(r,i)-query(l-1,i)) ans++;
			cout<<ans<<'\n';
		}
	}
}

Measured memory_bytes: 51584
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	int N,M,C;
	cin>>N>>M>>C;
	int B[M],A[N][M];
	int check;
	int checksum=0;
	for(int i=0;i<M;i++)cin>>B[i];
	for(int i=0;i<N;i++){
		check=0;
		for(int j=0;j<M;j++){
			cin>>A[i][j];
			check+=A[i][j]*B[j];
		}
		if(check+C>0){
			checksum+=1;
		}
	}
	cout<<checksum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
	int n;
	string s, S;
	cin >> n >> s;

	int ans = -1;
	vector<int> count(n+1);

	for(int i=0;i<=n;i++) {
		string ss = s;
		S = ss.substr(n-i);
		ss.erase(ss.end()-i, ss.end());

		//被り判定
		sort(ss.begin(), ss.end());
		sort(S.begin(), S.end());

		int jmax = ss.size()-1, kmax = S.size()-1;
		
		for(int j=0;j<jmax;j++) {
			if(ss[j] == ss[j+1]) {
				ss.erase(ss.begin()+j);
				j--;
				jmax--;
			}
		}

		for(int k=0;k<kmax;k++) {
			if(S[k] == S[k+1]) {
				S.erase(S.begin()+k);
				k--;
				kmax--;
			}
		}
		//被り判定終わり

		for(int j=0;j<ss.size();j++) {
			for(int k=0;k<S.size();k++) {
				if(ss.at(j) == S.at(k)) count[i]++;
			}
		}

		ans = max(ans, count[i]);
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
a,b = map(int,input().split())
sa = set()
sb = set()
i = 1
while i * i <= max(a,b):
    if a % i == 0:
        sa.add(i)
        sa.add(a//i)
    if b % i == 0:
        sb.add(i)
        sb.add(b//i)
    i += 1
s = sa & sb
s.remove(1)
for x in list(s):
    for y in list(s):
        if x == y:
            continue
        if y % x == 0:
            s.remove(y)
print(len(s) + 1)

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

using ll=long long;
using vll=vector<ll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vpii=vector<pii>;


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

    string s;
    cin >> s;
    int ocnt = 0;
    for (char c: s)
        ocnt += (c == 'o');
    if (ocnt + (15-s.size()) >= 8)
        cout << "YES\n";
    else
        cout << "NO\n";
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, p;
	cin >> n >> p;


	string s; cin >> s;
	
	if (p == 2 || p == 5) {
		ll res = 0;
		FOR(i,0,n) {
			if ((s[i]-'0') % p == 0) res += i+1;
		}
		cout << res << endl;
		return 0;
	}
	
	vl cnt(p);
	vl pw(n+1);
	pw[0] = 1;
	FOR(i,1,n+1) pw[i] = 10*pw[i-1] % p;
	
	ll cur = 0;
	cnt[cur]++;
	
	FOR(i,0,n) {
		cur = (cur + pw[n-i-1]*(s[i]-'0')) % p;
		cnt[cur]++;
	}
	
	ll res = 0;
	for (ll x: cnt) res += x*(x-1)/2;
	cout << res << endl;
}



Measured memory_bytes: 2196
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main(){
	string s;
	cin>>s;
	if(s.find('C')<s.rfind('F')&&s.find('C')!=-1&&s.find('F')!=-1)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0
    
    for i in range(n):
        if i % 2 == 0:
            if a[i] % 2 == 1:
                cnt += 1

    print(cnt)



if __name__ == '__main__':
    main()

Measured memory_bytes: 61728
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
#define N_MAX 2000001

ll inv[N_MAX],fac[N_MAX],finv[N_MAX];

void init(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<N_MAX;i++){
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        fac[i]=fac[i-1]*(ll) i%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

ll inv_(ll n){
    if(n == 1) return 1;
    else return MOD-inv_(MOD%n)*(MOD/n)%MOD;
}

ll comb(ll n, ll r){
  ll ans;
  if(n < r){
      ans = 0;
  }else{
      ans = (fac[n]*finv[r])%MOD;
      ans = (ans*finv[n-r])%MOD;
      ans = (ans+MOD)%MOD;
  }
  return ans;
}

int main(){
    init();
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    ll X, Y;
    cin >> X >> Y;
    if((X+Y)%3 != 0){
        cout << 0 << endl;
        return 0;
    }
    ll N = (X+Y)/3;
    ll n = X-N;
    if(n < 0) {
        cout << 0 << endl;
        return 0;
    }
    cout << comb(N, n) << endl;
}

Measured memory_bytes: 47104
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int sum = 0, mx = 0;
  for (int i = 0; i < n; ++i) {
    int p;
    cin >> p;
    sum += p;
    mx = max(mx, p);
  }
  cout << sum - mx / 2 << endl;
}


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

int main() {
	// your code goes here
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0;i<n;i++)
	cin>>arr[i];
	int dp[n]={0};
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	for(int j=2;j<n;j++)
	dp[j]=INT_MAX;;
//	dp[1]=abs(arr[2]-arr[0]);
	for(int i=2;i<n;i++){
	
	for(int j=i-1;j>=0 && i-j<=k;j--)
	dp[i]=min(dp[i],dp[j]+abs(arr[i]-arr[j]));
		
	}
	
	cout<<dp[n-1]<<" ";
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b,c,s[60],t[60],MOD=1e9+7,ans;
int main(void){
    cin>>n;
    cin>>a;
    for(int i=0;i<60;i++){
        if(((a>>i)&1)==1){
            s[i]++;
        }
    }
    for(int j=1;j<n;j++){
        cin>>a;
        for(ll i=0;i<60;i++){
            if(((a>>i)&1)==1){
                ans+=((j-s[i])*((1LL<<i)%MOD)%MOD);
                s[i]++;
            }
            else{
                ans+=(s[i]*((1LL<<i)%MOD)%MOD);
            }
            ans%=MOD;
        }
    }
    cout<<ans<<endl;
}


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

int main(){
    
    int n,maxh = 0; cin >> n;
    int i = 0, u = 0;
    while(i < n){
        int h; cin >> h;
        if(h >= maxh){
            u++;
            maxh = h;
        }
        i++;
    }
    cout << u;
    return 0;
}

Measured memory_bytes: 256
n,m,k=map(int,input().split())
mod=998244353
cntb=1
ans=0
for i in range(k+1):
    ans=ans+(((m*pow(m-1,n-1-i,mod))%mod)*cntb)%mod
    ans=ans%mod
    cntb=(cntb*(n-1-i)*pow(i+1,mod-2,mod))%mod
print(ans%mod)

Measured memory_bytes: 68248
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using piii = pair<int, pair<int, int>>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;

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

    int N, A, B;
    cin >> N >> A >> B;
    vector<ll> v(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i];
    sort(v.rbegin(), v.rend());

    vector<vector<ll>> bino(N + 1, vector<ll>(N + 1));
    bino[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) {
            bino[i][j] += bino[i - 1][j];
            if (j > 0)
                bino[i][j] += bino[i - 1][j - 1];
        }
    }

    int mcnt = 1;
    ll msum = 0, sum = 0, cnt = 0;
    for (int i = 0; i < N; ++i) {
        sum += v[i];
        if (i + 1 < A || i + 1 > B)
            continue;
        ll tmp1 = (i + 1) * msum, tmp2 = mcnt * sum;
        if (tmp1 <= tmp2) {
            auto itr1 = lower_bound(v.rbegin(), v.rend(), v[i]);
            auto itr2 = upper_bound(v.rbegin(), v.rend(), v[i]);
            int n = itr2 - itr1;
            int r = itr2 - v.rbegin() - (N - i - 1);
            if (tmp1 < tmp2)
                cnt = bino[n][r];
            else
                cnt += bino[n][r];
            mcnt = i + 1;
            msum = sum;
        }
    }

    printf("%.6lf\n", (double)msum / mcnt);
    printf("%lld\n", cnt);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define ssort(a) sort(a.begin(), a.end())
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n, a,b, c;
  cin >> n >> a >> b >> c;
  vector<string> s(n);
  vector<char> ans(n);
  rep(i, n){
    cin >> s[i];
  }
  rep(i, n){
    if(s[i].substr(0, 2)=="AB"){
      if(a==0 && b==0){
        cout << "No" << endl;
        return 0;
      } else if(a==0){
        a++;
        b--;
        ans[i]='A';
      } else if(b==0){
        a--;
        b++;
        ans[i]='B';
      } else if(i!=n-1 && s[i+1].substr(0, 2)!="AB" && a==1 && b==1){
        if(s[i+1].substr(0, 2)=="AC"){
          a++;
          b--;
          ans[i]='A';
        } else {
          a--;
          b++;
          ans[i]='B';
        }
      } else {
        if(a>=b){
          a--;b++;
          ans[i]='B';
        } else {
          a++;b--;
          ans[i]='A';
        }
      }
    } else if(s[i].substr(0, 2)=="BC"){
      if(b==0 && c==0){
        cout << "No" << endl;
        return 0;
      } else if(b==0){
        b++;
        c--;
        ans[i]='B';
      } else if(c==0){
        b--;
        c++;
        ans[i]='C';
      } else if(i!=n-1 && s[i+1].substr(0, 2)!="BC" && c==1 && b==1){
        if(s[i+1].substr(0, 2)=="AC"){
          c++;
          b--;
          ans[i]='C';
        } else {
          c--;
          b++;
          ans[i]='B';
        }
      } else {
        if(b>=c){
          b--;c++;
          ans[i]='C';
        } else {
          b++;c--;
          ans[i]='B';
        }
      }
    } else if(s[i].substr(0, 2)=="AC"){
      if(a==0 && c==0){
        cout << "No" << endl;
        return 0;
      } else if(a==0){
        a++;
        c--;
        ans[i]='A';
      } else if(c==0){
        a--;
        c++;
        ans[i]='C';
      } else if(i!=n-1 && s[i+1].substr(0, 2)!="AC" && c==1 && a==1){
        if(s[i+1].substr(0, 2)=="BC"){
          c++;
          a--;
          ans[i]='C';
        } else {
          c--;
          a++;
          ans[i]='A';
        }
      } else {
        if(a>=c){
          a--;c++;
          ans[i]='C';
        } else {
          a++;c--;
          ans[i]='A';
        }
      }
    }
  }
  cout << "Yes" << endl;
  rep(i, n){
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 6412
n,p=map(int,input().split())
def factorize(n):
    fct={}
    temp=n
    if temp<4:
        fct[temp]=1
    else:
        e=0
        while temp%2==0:
            temp=temp//2
            e+=1
        if e>0:
            fct[2]=e
    
    for b in range(3,int(n**0.5)+1,2):
        e=0
        while temp%b == 0:
            temp=temp//b
            e+=1
        if e>0:
            fct[b]=e
    if temp!=1:
        fct[temp]=1
    return fct
q=1
d=factorize(p)

for i in d:
    if d[i]<n:
        continue
    q=q*i**(d[i]//n)
print(q)


Measured memory_bytes: 38512
#include <cstdio>
#include <ctype.h>
#include <cmath>
#include <algorithm>

using namespace std;

char *p1, *p2, buf[1 << 20];

inline char gc()
{
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}

template<typename T>
void rd(T &num)
{
    char tt;
    bool flag = 0;
    while (!isdigit(tt = gc()) && tt != '-');
    if (tt == '-')
        num = 0, flag = 1;
    else
        num = tt - '0';
    while (isdigit(tt = gc()))
        num = num * 10 + tt - '0';
    if (flag)
        num = -num;
    return;
}

const int _N = 1e5 + 10;

int E, N, M;
int Nx[_N * 2], V[_N * 2], Fs[_N], Dfn[_N], Low[_N], ID[_N];

void ins(int a, int b)
{
    Nx[++E] = Fs[a], Fs[a] = E, V[E] = b;
    return;
}

bool dfs(int p, int clr, int *cnt)
{
    bool suc = 1;
    ID[p] = clr, ++cnt[clr];
    for (int i = Fs[p]; i; i = Nx[i]) {
        if (i & 1)
            ++cnt[3];
        int t = V[i], c = (clr + ((i & 1) ? 1 : 2)) % 3;
        if (ID[t] != -1) {
            if (ID[t] != c)
                suc = 0;
        } else {
            if (!dfs(t, c, cnt))
                suc = 0;
        }
    }
    return suc;
}

long long ss(int x)
{
    return 1ll * x * x;
}

int main()
{
    rd(N), rd(M);
    for (int a, b, i = 1; i <= M; ++i) {
        rd(a), rd(b);
        ins(a, b), ins(b, a);
    }
    for (int i = 1; i <= N; ++i)
        ID[i] = -1;
    long long ans = 0;
    for (int i = 1; i <= N; ++i) {
        if (ID[i] != -1)
            continue;
        int cnt[4];
        cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
        if (dfs(i, 0, cnt)) {
            if (cnt[0] && cnt[1] && cnt[2])
                ans += 1ll * cnt[0] * cnt[1] + 1ll * cnt[1] * cnt[2] + 1ll * cnt[2] * cnt[0];
            else
                ans += cnt[3];
        } else {
            ans += ss(cnt[0] + cnt[1] + cnt[2]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 8192
//题意：n个题目，分别需要Ti时间来解答；m个饮料，喝下会使得某题时间变成Pi；需要计算选择每个饮料后的总时间
//思路：数据范围n 1-100；可以先求出所有题的解题时间，然后在计算每种饮料时，减去该饮料所作用的题目的时间
//然后加上该饮料作用后的时间，  这样O(N) 
#include <iostream>
using namespace std;

const int N=110;

int t[N], p[N];
int sum;
int n,m;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		sum+=t[i];	
	}	
	
	cin>>m;
	while(m--){
		int i,v;
		cin>>i>>v;
		cout<<sum-t[i]+v<<endl;
	}
	return 0;
}


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

int main(){

  int n;

  while(cin >> n, n){
    int m,a,b,time = n;

    cin >> m;

    for(int i=0;i<m;i++){
      cin >> a >> b;

      n -= (b-a);
    }

    if(n <= 0) cout << "OK" << endl;
    else cout << n << endl;
  }
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
  string s;
  cin >> s;
  string s0 = s.substr(0,3);
  string s1 = s.substr(1,3);
  if( all_of(s0.begin(), s0.end(), [&](char c){return c == s0[0];}) ||
  all_of(s1.begin(), s1.end(), [&](char c){return c == s1[0];}) ){
    cout << "Yes" << endl;
  }else{
        cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;
static const ll LOGN=55;


ll a[1111][1111];

int main(void) {
  ll H, W, A, B;
  cin >> H >> W >> A >> B;
  ll i, j;
  
  for(i=0; i<H; i++) {
    for(j=0; j<W; j++) {
      if(i<B && j<A) a[i][j]=1;
      else if(i>=B && j>=A) a[i][j]=1;
      else a[i][j]=0;
    }
  }
  
  for(i=0; i<H; i++) {
    for(j=0; j<W; j++) {
      cout << a[i][j];
    }
    pt("");
  }
  
}






Measured memory_bytes: 9856
#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
typedef long long ll;
typedef pair<int,pair<int,int>> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010;
int dx[5]={0,1,0,-1,0};
int dy[5]={1,0,-1,0,0};
ll sum[100010];
map<ll,ll> mp;
int main(){
    ll n,m;cin>>n>>m;
    ll a[100010];
    for(int i=0;i<n;i++){
        cin>>a[i];a[i]%=m;
    }
    mp[0]++;
    ll ans=0;
    for(int i=0;i<n;i++){
        sum[i+1]+=sum[i];
        sum[i+1]+=a[i];
        sum[i+1]%=m;
        ans+=mp[sum[i+1]];
        mp[sum[i+1]]++;
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 5760
/*Read the problem carefully before starting to work on it*/
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

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

#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007

double PI=3.1415926535897932384626;

//template<typename T> T power(T x,T y,ll m=mod){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

#define fi first
#define se second

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b,k;
	cin>>a>>b>>k;
	ll c=min(a,k);
	a-=c;
	k-=c;
	ll d=min(b,k);
	b-=d;
	k-=d;
	cout<<a<<" "<<b;
    return 0;
}


//252908XL

Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef unsigned long long ull;

ull fact (int n) {
    if (n < 2) return 1;
    else return (ull)n * fact(n - 1);
}

int main (void) {
    int n;
    cin >> n;
    cout << fact(n) << endl;
    return 0;
}

Measured memory_bytes: 1156
def canb_month(num):
    if 0 < num and num <= 12:
        return True
    else:
        return False


s = input()
f_half = int(s[:2])
s_half = int(s[2:])

a = None
if canb_month(f_half) and canb_month(s_half):
    a = 'AMBIGUOUS'
else:
    if canb_month(f_half):
        a = 'MMYY'
    elif canb_month(s_half):
        a = 'YYMM'
    else:
        a = 'NA'
        
print(a)


Measured memory_bytes: 3060
def collapse(A):
    R = []
    a = max(A)
    n = a.bit_length()
    B = [set() for _ in range(n)]
    for a in A:
        B[a.bit_length()].add(a)
    for i in reversed(range(n)):
        if not B[i]:
            continue
        b = B[i].pop()
        R.append(b)
        for k in B[i]:
            k ^= b
            B[k.bit_length()].add(k)
    return R

def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            n = a.bit_length() - 1
            while a != 0:
                if B[n] == 0:
                    return 1
                a ^= B[n]
                n = a.bit_length() - 1
        else:
            n = a.bit_length() - 1
            while a != 0 and B[n] != 0:
                a ^= B[n]
                n = a.bit_length() - 1
            if a == 0:
                continue
            B[n] = a
    return 0
    
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(N, A, S))
main()


Measured memory_bytes: 9096
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <stack>
#include <unordered_map>
#include <utility>
#include <vector>

// Aliases
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;

using std::cout;
using std::cerr;
using std::cin;
using std::endl;
using std::string;
using std::vector;
using std::array;
template <class T>
constexpr T inf = std::numeric_limits<T>::max();
template <class T>
constexpr T neg_inf = -std::numeric_limits<T>::max();
template <class T>
constexpr T pi = static_cast<T>(3.141592653589793);

template <class T = i64>
vector<T> read_vector(const u64 n)
{
    vector<T> vec;
    vec.reserve(n);
    for (u64 i = 0; i < n; i++)
    {
        T v;
        cin >> v;
        vec.emplace_back(v);
    }

    return vec;
}

template <class T>
void print(const vector<T>& vec, const bool new_line = false)
{
    const u64 n = vec.size(); 
    if (new_line)
    {
        for (u64 i = 0; i < n; i++)
        {
            cout << vec[i];
            if (i != n - 1) { cout << '\n'; }
        }
    }
    else
    {
        for (u64 i = 0; i < n; i++)
        {
            cout << vec[i];
            if (i != n - 1) { cout << ' '; }
        }
    }

    cout << endl;
}

int main()
{
    u32 n;
    cin >> n;
    double ratio;
    if (n % 2 == 0)
    {
        ratio = (double)(n) / 2 / n;
    }
    else
    {
        ratio = (double)(n / 2 + 1) / n;
    }

    cout << ratio << endl;

    return 0;
}


Measured memory_bytes: 256
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);

void main()
{
    string s;
    scan(s);
    // writeln(s);
    foreach (i; 2 .. s.length)
    {
        // writeln(s[0 .. $ - i]);
        auto ss = s[0 .. $ - i];
        if (func(ss))
        {
            writeln(ss.length);
            return;
        }
    }
    // writeln(s[0 .. (s.length / 2)]);
    // writeln(s[(s.length / 2) .. s.length]);
}

auto func(string s)
{
    if (s[0 .. (s.length / 2)] == s[(s.length / 2) .. s.length])
    {
        return true;
    }
    else
    {
        return false;
    }
}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}


Measured memory_bytes: 3720
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}

int dx4[4]={1,-1,0,0};
int dy4[4]={0,0,1,-1};

int main(){
  int i,j,n,m;
  int d,v,rd[128]={0},r;
  while(scanf("%d%d",&n,&m),n!=0){
    for(i=0;i<n;i++){
      scanf("%d%d",&d,&v);
      rd[d]=max(rd[d],v);
    }
    r=0;
    for(i=1;i<=m;i++){
      r+=rd[i];
      rd[i]=0;
    }
    printf("%d\n",r);
  }
  return 0;
}



Measured memory_bytes: 2044
#include<iostream>
using namespace std;
int nb_digits(int x)
{
    int p=1, a=0;
    while(p <= x)
    {
        p*=10;
        a++;
    }
    return a;
}
int main()
{
  int n, nb=0;
  cin >> n;
  while(n > 0)
  {
      if(nb_digits(n)%2==1)
        nb++;
      n--;
  }
  cout << nb << '\n';
}

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

int main() {
  set<int> S;
  for (int i = 0; i < 3; i++) {
    int a;
    cin >> a;
    S.insert(a);
  }
  cout << ((S.size() == 2) ? "Yes" : "No") << "\n";
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
n = int(input())
p_n_str = input().split()
p_n_int = [int(p) for p  in p_n_str]
flag = 0

for k in range(0, n):

    if p_n_int[k] != k+1:
        
        for i in range(1, n):
            if k+1 == p_n_int[i]:
                flag += 1
                smp = p_n_int[k]
                p_n_int[k] = p_n_int[i]
                p_n_int[i] = smp
                break
        
if flag <= 1:        
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			String str = scan.next();
			int a = scan.nextInt();
			int b = scan.nextInt();
			System.out.println(str + " " + (a + b) + " " + (a*200 + b * 300));
		}
	}
}

Measured memory_bytes: 17184
#include <iostream>
using namespace std;
int main() {
  int a, b, k;
  cin >> k >> a >> b;
  for (int i = a; i <= b; ++i) {
    if (i % k == 0) {
      puts("OK");
      return 0;
    }
  }
  puts("NG");
  return 0;
}

Measured memory_bytes: 3636
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 06/27/20 20:37:13
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  string s,t; cin>>s>>t;
  int ans = 0;
  for (int i = 0; i < s.size(); i++)
    if (s[i] != t[i])
      ans++;
    
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3796
#include <iostream>

using namespace std;

int main(){
  string S;
  cin >> S;
  string ans = "Good";
  if(S[0] == S[1]) ans = "Bad";
  if(S[1] == S[2]) ans = "Bad";
  if(S[2] == S[3]) ans = "Bad";

  cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;
 
 int main(void){
     int N;
     cin >> N;
     string S[N];
     rep(i,N) cin >> S[i];
     int L[N];
     rep(i,N) L[i]=S[i].length();
     int alf[N][26]={};
     rep(i,N) rep(j,L[i]) alf[i][S[i][j]-'a']++;
     rep(i,26){
         int count=INF;
         rep(j,N){
             int count2=alf[j][i];
             count=min(count,count2);
         }
         char ans='a'+i;
         if(count!=INF) rep(j,count) cout << ans;
     }
     cout << endl;
 } 

Measured memory_bytes: 256
import numpy as np
h,w = map(int,input().split())
s = np.array([[1 if i == "." else 0 for i in input()] for j in range(h)])
l,r,u,d = np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w))
for i in range(h):
  u[i] = (u[i-1]+1)*s[i]
  d[-i-1] = (d[-i]+1)*s[-i-1]
for i in range(w):
  l[:,i] = (l[:,i-1]+1)*s[:,i]
  r[:,-i-1] = (r[:,-i]+1)*s[:,-i-1]
print(int(np.max(l+r+u+d))-3)

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

const int MAX_E = 500001;
const int MAX_V = 100001;
const int MAX_D = 1000000000;

struct edge { int from, to, cost=MAX_D; };

int main() {
	int V, E, s;
	cin >> V >> E >> s;
	//int table[MAX_V][MAX_V] = {0};
	edge table[MAX_E];

	for (int i = 0; i < E; i++)
		cin >> table[i].from >> table[i].to >> table[i].cost;
	
	//*****************
	int prev[MAX_V];
	int dist[MAX_V];
	bool s_[MAX_V];

	for (int i = 0; i < V; i++)
		dist[i] = MAX_D;
	dist[s] = 0;

	for (int i = 0; i < V; i++)
		prev[i] = -1;
	prev[s] = s;

	for (int i = 0; i < V; i++)
		s_[i] = false;
	s_[s] = true;

	for (int i = 0; i < E; ++i)
	{
		if (table[i].from == s)
		{
			dist[table[i].to] = table[i].cost;
			prev[table[i].to] = s;
		}


	}
	dist[s] = 0;
	s_[s] = true; //????§????

	int mindist = MAX_D;
	bool mark = false;
	for (int i = 1; i < V; i++)
	{
		if (!mark&&i != 1)
			continue;
		mark = false;
		int u = s;
		for (int j = 0; j < V; j++)
		{
			if (!s_[j] && dist[j] < mindist)
			{
				u = j;
				mindist = dist[j];
				mark = true;
			}
		}
		s_[u] = true;//?????°???s????§????????????????

		int mindist_ = MAX_D;
		for (int j = 0; j < E; j++)
		{
			if (!s_[table[j].to] && table[j].cost < mindist_)
			{
				if (dist[table[j].from] + table[j].cost < dist[table[j].to])
				{
					dist[table[j].to] = dist[table[j].from] + table[j].cost;
					prev[table[j].to] = table[j].from;
					mark = true;
				}
			}
		}
	}

	for (int i = 0; i < V; i++)
	{
		if(dist[i]<MAX_D)
			cout << dist[i] << endl;
		else
			cout << "INF" << endl;
	}

	return 0;
}

Measured memory_bytes: 9396
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=1e9+7;
//
//
struct poi{
  int X;int Y;int Z;
  bool operator<(const poi&R)const{
    return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
  }
};
//
//
int main(){
	int N,K;
	cin>>N>>K;
	int ans=0;
	N-=2;
	ans+=N/11*5;
	N%=11;
	if(N>=1){
		if(K==0||K==2||K==4||K==7||K==9){
			ans++;
		}
	}
	if(N>=2){
		if(K==1||K==4||K==6||K==8||K==10){
			ans++;
		}
	}
	if(N>=3){
		if(K==1||K==3||K==5||K==7||K==9){
			ans++;
		}
	}
	if(N>=4){
		if(K==0||K==2||K==4||K==6||K==9){
			ans++;
		}
	}
	if(N>=5){
		if(K==1||K==3||K==6||K==8||K==10){
			ans++;
		}
	}
	if(N>=6){
		if(K==0||K==3||K==5||K==7||K==9){
			ans++;
		}
	}
	if(N>=7){
		if(K==0||K==2||K==4||K==6||K==8){
			ans++;
		}
	}
	if(N>=8){
		if(K==1||K==3||K==5||K==8||K==10){
			ans++;
		}
	}
	if(N>=9){
		if(K==0||K==2||K==4||K==7||K==9){
			ans++;
		}
	}
	if(N>=10){
		if(K==2||K==4||K==6||K==8||K==10){
			ans++;
		}
	}
	if(N>=11){
		if(K==1||K==3||K==5||K==7||K==10){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
N = input()
mod = 10 ** 9 + 7
num_p = [1] * 1001
p = []
# find p
for i in range(2, N + 1):
  canDivide = True
  for j in range(2, i):
    if i % j == 0:
      canDivide = False
      break
  if canDivide:
    p.append(i)

# factorization
for i in range(2, N + 1):
  for j in p:
    c = 0
    while i % j == 0:
      c += 1
      i /= j
    num_p[j] = (num_p[j] + c) % mod

print reduce(lambda x, y: x * y, num_p) % mod

Measured memory_bytes: 2820
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=100000+10,inf=0x3f3f3f3f;
int n,m,e,val[MAXN],to[MAXN<<1],nex[MAXN<<1],beg[MAXN],cnt,vis[MAXN],use[MAXN],Mn[MAXN];
ll ans;
std::priority_queue< int,std::vector<int>,std::greater<int> > q;
template<typename T> inline void read(T &x)
{
	T data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
	x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
	if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
	to[++e]=y;
	nex[e]=beg[x];
	beg[x]=e;
}
inline void dfs1(int x)
{
	vis[x]=cnt;chkmin(Mn[cnt],val[x]);
	for(register int i=beg[x];i;i=nex[i])
		if(!vis[to[i]])dfs1(to[i]);
}
inline void dfs2(int x)
{
	vis[x]=cnt;
	if(val[x]==Mn[cnt]&&!use[cnt])use[cnt]=1,ans+=Mn[cnt];
	else q.push(val[x]);
	for(register int i=beg[x];i;i=nex[i])
		if(!vis[to[i]])dfs2(to[i]);
}
int main()
{
	read(n);read(m);
	for(register int i=1;i<=n;++i)read(val[i]);
	for(register int i=1;i<=m;++i)
	{
		int u,v;read(u);read(v);
		u++;v++;
		insert(u,v);insert(v,u);
	}
	if(m==n-1)
	{
		puts("0");
		return 0;
	}
	for(register int i=1;i<=n;++i)
		if(!vis[i])Mn[++cnt]=inf,dfs1(i);
	memset(vis,0,sizeof(vis));cnt=0;
	for(register int i=1;i<=n;++i)
		if(!vis[i])++cnt,dfs2(i);
	if(n<(cnt-1)*2)
	{
		puts("Impossible");
		return 0;
	}
	int rest=2*(cnt-1)-cnt;
	while(rest--)ans+=q.top(),q.pop();
	write(ans,'\n');
	return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

int main(){
    int N; 
    cin >> N;
    vector<int> W(N);

    for (int i = 0; i < N; i++)
    {
        cin >> W[i];
    }
    
    
    int ans = 0;
    int tmp =0;
    int s1 =0;
    int tmp_old = 10000;
    int all= 0;

    for (int i = 0; i < N; i++)
    {
        all += W[i]; 
    }
    
    for (int i = 0; i < N; i++)
    {
        s1 += W[i];
        tmp = abs(all-s1-s1);
        ans = min(tmp,tmp_old);
        if (tmp<=ans)
        {
            ans = tmp;
        }

        tmp_old = ans;
        
    }
    
    cout << ans << endl;


}

Measured memory_bytes: 256
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  while d<h:
    d+=1
    if i>>d-1&1: e+=[(u,d)]; c+=1; u=d
  e+=[(u,h)]
  while r<w:
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
    r+=1
  else: a=min(a,c)
print(a)

Measured memory_bytes: 3436
N = int(input())
mod = 10 ** 9 + 7
res = (10 ** N) % mod
res = res - ((9 ** N) % mod) # no 9
res = res - ((9 ** N) % mod) # no 0
res = res + ((8 ** N) % mod) # no 9 and no 0
print(res % mod)

Measured memory_bytes: 10868
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define LLINF 100000000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,M,P;
int A[5020],B[5010];
ll C[5010];
ll d[5010];
int main(){
	cin >> N >> M >> P;
	for(int i=0;i<M;i++){
		cin >> A[i] >> B[i] >> C[i];
		C[i] -= P;
	}
	for(int i=2;i<=N;i++){
		d[i] = -LLINF;
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			int a = A[j];
			int b = B[j];
			ll c = C[j];
			if(d[b]<d[a]+c){
				d[b] = d[a]+c;
			}
		}
	}
	ll prev = d[N];
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			int a = A[j];
			int b = B[j];
			ll c = C[j];
			if(d[b]<d[a]+c){
				// cout << a << ' ' << b << ' ' << c << endl;
				d[b] = d[a]+c;
			}
		}
	}
	if(d[N]!=prev)cout << -1 << endl;
	else cout << max(0ll,d[N]) << endl;
	return 0;
}


Measured memory_bytes: 384
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let a: usize = iterator.next().unwrap().parse().unwrap();

    if n % 500 <= a {
        "Yes".to_string()
    } else {
        "No".to_string()
    }
}


Measured memory_bytes: 2108
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<queue>
#include<deque>
#include<climits>
#include<numeric>
#include<cassert>
#include<functional>
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define fi(i,j,k) fill(i[0],i[0]+j*j,k)
#define INF 1<<27
#define F first
#define S second
static const double eps=1e-10;
typedef long long ll;
using namespace std;
typedef pair<int,int> P;
int h,w;
char cmap[110][110];
P pos[110];
int index,matrix[110][110];
int imap[110][110];
static const int dx[4] = {0,1,0,-1};
static const int dy[4] = {1,0,-1,0};
static const int dx8[8] = {0,1,1,1,0,-1,-1,-1};
static const int dy8[8] = {-1,-1,0,1,1,1,0,-1};
static const int dx16[16] = {0,1,2,2,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1};
static const int dy16[16] = {-2,-2,-2,-1,0,1,2,2,2,2,2,1,0,-1,-2,-2};

int D[110][110];
bool used[110][110];

void bfs(P s,P g){
  rep(i,h)rep(j,w){
    D[i][j] = INF;
    used[i][j] = false;
  }
  queue<P> que;
  que.push(s);
  D[s.S][s.F] = 0;
  used[s.S][s.F] = true;

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

    for(int i=0;i<4;i++){
      int nx = p.F+dx[i],ny = p.S+dy[i];
      if(0<= nx && nx < w && 0<= ny && ny < h && cmap[ny][nx] != '#' && D[ny][nx] > D[p.S][p.F] +imap[ny][nx]){
	D[ny][nx] = min(D[p.S][p.F] + imap[ny][nx],D[ny][nx]);

	que.push(P(nx,ny));
      }
    }
  }
}

int main(){
  while(cin >> w >> h){
    int sindex,lim = 1;
    index = 1;
  
    rep(i,h)rep(j,w)imap[i][j] = 1;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> cmap[i][j];
	matrix[i][j] = INF;
	if(cmap[i][j] == 'S'){
	  lim++;
	}
	else if(cmap[i][j] == 'M')lim++;
	else if(cmap[i][j] == 'G'){
	  pos[0] = P(j,i);
	}
      }
    }
 
    rep(i,h){
      rep(j,w){
      
	if(cmap[i][j] == 'S'){
	  pos[lim-1] = P(j,i);
	}
	else if(cmap[i][j] == 'M'){
	  assert(index != lim-1);
	  pos[index++] = P(j,i);
	}
	else if(cmap[i][j] == '#'){
	  for(int k=0;k<8;k++){
	  
	    int nx = j+dx8[k],ny = i+dy8[k];
	    if(0<=nx && nx<w && 0<=ny && ny <h && cmap[ny][nx] != '#'){
	      imap[ny][nx] = 3;
	    }
	  }
	  for(int k=0;k<16;k++){
	    int nx = j+dx16[k],ny = i+dy16[k];
	    if(0<=nx && nx<w && 0<=ny && ny <h && cmap[ny][nx] != '#'){
	      imap[ny][nx] = max(imap[ny][nx],2);
	    }
	  }
	}
      }
    }


    index = lim;

    for(int i=0;i<index;i++){
      rep(j,index){
    
	if(i == j){
	  matrix[i][j] = 0;
	  continue;
	}
	bfs(pos[i],pos[j]);
	matrix[i][j] = D[pos[j].S][pos[j].F];
      }
    }
    int per[110];
    rep(i,index-1)per[i] = i+1;

    int sum;
    int ans=INF;
    do{
      sum=0;
      sum+=matrix[0][per[0]];

      int posi=-1;     
      for(int i=1;i<index-1;i++){
	if(i == index-2)posi = per[i];
	sum+=matrix[per[i-1]][per[i]];
      }
    
      if(posi != -1 && posi != lim-1)sum += matrix[posi][lim-1];
    
      ans=min(ans,sum);
    }while(next_permutation(per,per+(index-1)));
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N; cin >>N;
  long long kotae=1;
  long long count=1;
  long long MOD=1000000007;
  while(count<=N){
    kotae=kotae*count%MOD;
    count++;
    if(count>N)break;
  }
  cout <<kotae<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    string ans = "Yes";
    if (abs(a - c) > d)
        if (abs(a - b) > d || abs(b - c)>d)
            ans = "No";
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
#define inf 100000000/*10^8*/



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


int main(){
    int n,x;cin>>n>>x;
    int a[n+1];a[0]=0;for(int i=1;i<=n;i++)cin>>a[i];
    ll ans=0;
    for(int i=0;i<=n-1;i++){
        int c=a[i]+a[i+1]-x;
        if(c>0){
            ans+=c;
            a[i+1]-=c;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640