akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define INFTY 1<<20
typedef long long int ll;
const int MOD=1000000007;

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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){

int n;
ll k;
cin>>n>>k;
vector<pair<int,int>> p(n);
rep(i,n){
  int a,b;
  cin>>a>>b;
  p[i]=make_pair(a,b);
}
sort(p.begin(),p.end());
ll num=0;
rep(i,n){
  if(num+p[i].second<k){
    num += p[i].second;
  }
  else {
    cout<<p[i].first<<endl;
    break;
  }
}

  return 0;
}

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

using namespace std;

int main(int argc, char const *argv[])
{
    long long H;
    cin >> H;
    long long cnt = 0;
    long long tmp = H;
    while (tmp >= 2)
    {
        tmp /= 2;
        cnt += 1;
    }
    cout << (long long)pow(2.0, (double)(cnt + 1)) - 1 << endl;
    
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int a,b,c,k;
    scanf("%d %d %d %d",&a,&b,&c,&k);
    int tmp=0;
    if(a>=b){
        while(b<=a){
            b*=2;
            tmp++;
        }
    }
    if(b>=c){
        while(c<=b){
            c*=2;
            tmp++;
        }
    }
    
    if(tmp<=k)cout<<"Yes";
    else cout<<"No";
    return 0;
}

Measured memory_bytes: 3680
# coding: utf-8
# Your code here!


n=int(input())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))

ans = 0
rp = 0
for idx, a in enumerate(al):
    if idx == n:
        ans += min(rp, a)
    else:
        b = bl[idx]
        enemy = min(a,b+rp)
        ans += enemy
        rp = min(max(b - enemy + rp, 0), b)
print(ans)

Measured memory_bytes: 82148
import math

A, B = map(int, input().split())

a1 = (A+1)/0.08
a2 = A/0.08
b1 = (B+1)/0.1
b2 = B/0.1


if a2 >= b1 or b2 >= a1:
    print(-1)
else:
    print(math.ceil((max(a2, b2))))

Measured memory_bytes: 9192
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 200003;
template<typename T>
inline void read(T &x){
	int ch = getchar(); x = 0;
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template<typename T>
inline bool chkmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int n, a[N], mx, cnt[N];
bool val[N];
char s[N];
struct SegTree {
	int seg[N << 2];
	inline void build(int x, int L, int R){
		seg[x] = 1 - 1e9;
		if(L == R) return;
		int mid = L + R >> 1;
		build(x << 1, L, mid);
		build(x << 1 | 1, mid + 1, R);
	}
	inline void change(int x, int L, int R, int p, int v){
		if(L == R){seg[x] = v; return;}
		int mid = L + R >> 1;
		if(p <= mid) change(x << 1, L, mid, p, v);
		else change(x << 1 | 1, mid + 1, R, p, v);
		seg[x] = max(seg[x << 1], seg[x << 1 | 1]); 
	}
	inline int query(int x, int L, int R, int l, int r){
		if(l <= L && R <= r) return seg[x];
		int mid = L + R >> 1, ans = -1e9;
		if(l <= mid) ans = query(x << 1, L, mid, l, r);
		if(mid < r) chkmax(ans, query(x << 1 | 1, mid + 1, R, l, r));
		return ans;
	}
} Odd, Even;
inline bool check(int p, int v){
	if(v < 0) return false;
	if(v & 1) return Odd.query(1, 1, n, p, n) >= v;
	return Even.query(1, 1, n, p, n) >= v;
}
int main(){
	read(n);
	for(Rint i = 1;i <= n;++ i){
		read(a[i]); val[i] = chkmax(mx, a[i]);
	}
	Odd.build(1, 1, n);
	for(Rint i = n;i;-- i){
		int mx1 = Odd.query(1, 1, n, a[i], n), mx2 = Even.query(1, 1, n, a[i], n);
		if(val[i]) Odd.change(1, 1, n, a[i], mx1 + 2), Even.change(1, 1, n, a[i], mx2 + 2);
		else Odd.change(1, 1, n, a[i], mx2 + 1), Even.change(1, 1, n, a[i], mx1 + 1);
	}
	for(Rint i = n;i;-- i) cnt[i] = cnt[i + 1] + val[i];
	int cnt1 = 0, cnt2 = 0, mx1 = 0, mx2 = 0;
	for(Rint i = 1;i <= n;++ i){
		Odd.change(1, 1, n, a[i], 1 - 1e9); Even.change(1, 1, n, a[i], 0);
		if (check(mx2, cnt1 + cnt[i + 1] - cnt2 + (a[i] > mx1)) ||
			check(max(mx1, a[i]), cnt2 + cnt[i + 1] - cnt1 - (a[i] > mx1))){
			s[i] = '0'; cnt1 += chkmax(mx1, a[i]);
		} else {
			s[i] = '1'; cnt2 += chkmax(mx2, a[i]);
		}
	}
	if(cnt1 != cnt2) puts("-1");
	else puts(s + 1);
}

Measured memory_bytes: 8576
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int n;
	while(cin>>n,n){
		int a[11][11]={0};
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>a[i][j];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				a[i][n]+=a[i][j];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				a[n][i]+=a[j][i];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				a[n][n]+=a[i][j];
			}
		}
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++){
				printf("%5d",a[i][j]);
			}
			cout<<endl;
		}
	}
}

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    char ref=s[0];
    int ccount=0;
    int n=s.size();
    for(int i = 0; i < n; i++) {
        if(ref!=s[i]){
            ccount++;
            ref=s[i];
        }
    }
    cout << ccount << "\n";
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  int A[105000];
  int Acopy[105000];
  for (int i = 1; i <= N; i++){
    cin >> A[i];
    Acopy[A[i]] = i;
  }
  for (int i = 1; i <= N; i++) cout << Acopy[i] << ' '; 
}

Measured memory_bytes: 1664
N = int(input())
A = list(map(int,input().split()))
S = []
s = 0
for i in range(N):
    s += A[i]
    S.append(s)
ans = 0
S.sort()
x = S[0]
j = 1
if x == 0:
    ans += 1
for i in range(1,N):
    y = S[i]
    if y == 0:
        ans += 1
    if x == y:
        ans += j
        j += 1
    else:
        x = y
        j = 1
print(ans)

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n,x;cin >> n >>x;
    vector<lint> l(n);
    REP(i, n) { cin >> l[i]; }
    lint ans=0;
    lint d = 0;
    FOR(i,1,n+1){
        d = d + l[i - 1];
        if(d>x){
            cout << i<< "\n";

            return 0;
        }
    }

    cout << n+1 <<"\n";

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
size_t N,A,B,C;
string S,t;
int main(){
    cin>>N>>A>>B>>S;
    for(size_t i{};i<S.size();++i){
        if(S[i]=='a'&&C<A+B){
            ++C;cout<<"Yes"<<endl;
            continue;
        }
        else if(S[i]=='b'){
            t+=S[i];
            if(C<A+B&&t.size()<=B){
                ++C;cout<<"Yes"<<endl;
            }
            else cout<<"No"<<endl;
            continue;
        }
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
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 INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#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)
int M,N;
string s,t;
string IO = "IO";
int dp[2050][2050][2];
int rec(int a,int b,int k){ // k 0 'I' 1 'O'
	if(dp[a][b][k]!=-1)return dp[a][b][k];
	if(a>=M){
		if(b>=N)return dp[a][b][k]=0;
		if(t[b]!=IO[k])return dp[a][b][k]=0;
		return dp[a][b][k]=1+rec(a,b+1,k^1);
	}else if(b>=N){
		if(s[a]!=IO[k])return dp[a][b][k]=0;
		return dp[a][b][k]=1+rec(a+1,b,k^1);
	}
	int ret = 0;
	if(s[a]==IO[k])ret=max(ret,1+rec(a+1,b,k^1));
	if(t[b]==IO[k])ret=max(ret,1+rec(a,b+1,k^1));
	return dp[a][b][k]=ret;
}
int main(){
	scanf("%d %d",&M,&N);
	cin >> s;
	cin >> t;
	int ans = 0;
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<=M;i++){
		for(int j=0;j<=N;j++){
			ans = max(ans,rec(i,j,0));
		}
	}
	if(ans>0&&ans%2==0)ans--;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 34388
x,k,d = map(int,input().split())

def judge():
    l = x if x > 0 else -x
    i = l//d
    r = l%d

    if (k - i)%2 == 0:
        print(r)
    else:
        print(d - r)
    '''
    if x > 0:
        for r in range(d):
            if (x - r)/d == (x - r)//d:
                i = (x - r)//d
                if (k - i)%2 == 0:
                    print(r)
                else:
                    print(d-r)
                exit()
    else:
        l = -x
        for r in range(d):
            if (l - r)/d == (l - r)//d:
                i = (l - r)//d
                if (k - i)%2 == 0:
                    print(r)
                else:
                    print(d-r)
                exit()
    '''

if x == 0:
    if k%2 == 0:
        print(0)
    else:
        print(d)
elif x < 0:
    if k*d + x > 0:
        judge()
    else:
        print(abs(k*d + x))
else:
    if x - k*d < 0:
        judge()
    else:
        print(abs(x - k*d))


Measured memory_bytes: 9056
#include<bits/stdc++.h>
#define clr(x) memset(x, 0, sizeof(x))
#define sz(x) (int)x.size()
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printii(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;

using namespace std;

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

const ll mx = 105;
const ll mod = 998244353;
const ll maxn = 1e17;


bool vis[101][101];

bool in(ll x, ll y, ll r, ll c){
  return x>=0 && y >= 0 && x < r && y<c;
}

void solve(){
 
 ll n, i, j, k;
 cin>>n>>k;

 ll p[n];
 for(i =0 ;i < n;i++){
   cin>>p[i];
 }
 sort(p, p+n);
 ll res = 0;

 for(i = 0;i < k;i++){
   res += p[i];
 }
 cout<<res<<"\n";


}   


int main(){

   ios_base::sync_with_stdio(false);
   cin.tie(0);

    ll t = 1;
    
   // cin>>t;

    while(t--){
        solve();
    }
   
}




Measured memory_bytes: 3656
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val patterns = Seq(1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049).sorted


    // hiまでにかかるコスト
    val dp = Array.fill[Int](n + 1)(Int.MaxValue)
    dp(0) = 0
    for (i <- 0 to n) {
      for (pat <- patterns) {
        if (i + pat <= n) {
          dp(i + pat) = math.min(dp(i + pat), dp(i) + 1)
        }
      }
    }
    println(dp(n))
  }
}


Measured memory_bytes: 30268
#include <cstdio>
#include <cmath>
#include <vector>

int main(int argc, char const *argv[]) {
  char s[11];
  int n[11];
  int l = 0;
  scanf("%s", s);
  for (int i = 0; s[i] != 0; i++) {
    n[i] = s[i] - '0';
    l++;
  }
  int bits = pow(2, l - 1);
  long r = 0;
  for (int i = 0; i < bits; i++) {
    std::vector<int> v;
    // printf("bits%d\n", i);
    for (int j = 0; j < l; j++) {
      bool b = (i >> j) & 1;
      v.push_back(n[j]);
      //printf("v%d\n", n[j]);
      if (j == l - 1 || (i >> j) & 1) {
        for (int u = 0; u < v.size(); u++) {
          //printf("%d %d\n", v[u], v[u] * (int)pow(10, v.size() - 1 - u));
          r += v[u] * pow(10, v.size() - 1 - u);
        }
        v.clear();
      }
    }
  }
  printf("%ld\n", r);
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int cntEven = 0;
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			if (tmp % 2 == 0)
				cntEven++;
		}

		int ans = (int) Math.pow(3, n) - (int) Math.pow(2, cntEven);

		System.out.println(ans);

		sc.close();
	}

}


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

int main(){
int N;
  cin>>N;
  
  vector<string>s(N);
  for(int i=0;i<N;i++){
    cin>>s.at(i);
  }
  
  int M;
  cin>>M;
  
  vector<string>t(M);
  
  for(int i=0;i<M;i++){
    cin>>t.at(i);
  }
  
  int max=-100;
  
  for(int i=0;i<N;i++){
    int sum=0;
    for(int j=0;j<N;j++){
      if(s.at(i)==s.at(j)){
        sum++;
      }
    }
    
      int sum1=0;
      
      for(int k=0;k<M;k++){
        if(s.at(i)==t.at(k)){
          sum1++;
        }
      }
      
      if(sum-sum1>max){
        max=sum-sum1;
      }
    }
  
  if(max>0){
    cout<<max<<endl;
  }
  else{
cout<<0<<endl;
  }
}

  


Measured memory_bytes: 256
S = input()
S_list=list(S)
A,B,C,D = int(S_list[0]),int(S_list[1]),int(S_list[2]),int(S_list[3])
res = ""

for i in range(8):
	ans = str(A)
	val = A
	if i & 1 == 1:
		ans += '+'
		val += B
	else:
		ans += '-'
		val -= B
	ans += str(B)
	if i & 2 == 2:
		ans += '+'
		val += C
	else:
		ans += '-'
		val -= C
	ans += str(C)
	if i & 4 == 4:
		ans += '+'
		val += D
	else:
		ans += '-'
		val -= D
	ans += str(D)
	ans += "=7"
	if val == 7:
		res = ans
		break;

print(res)

Measured memory_bytes: 3064
#include<stdio.h>

#define MAX 100005
#define NTL -1

struct Node{int p, l, r;};
struct Node A[MAX];

int n,H,D[MAX];

int main(){
  int i,j,d,v,c,l;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    A[i].p = A[i].l = A[i].r = NTL;
  }

  for(i=0;i<n;i++){
    scanf("%d %d",&v,&d);
    for(j=0;j<d;j++){
      scanf("%d",&c);
      if(j == 0)A[v].l =c;
      else A[l].r =c;
      l =c;
      A[c].p=v;
    }
  }

  H=0;
  for(i=0;i<n;i++){
    D[i]=getDepth(i);
    if(D[i] >H)
      H=D[i];
  }

  for(i=0;i<n;i++)print(i);
  return 0;
}

int getDepth(int x){
  int d=0;

  for(;A[x].p!= NTL;d++)x = A[x].p;
  return d;
}

int print(int x){
  int i,c;

  printf("node %d: ",x);
  printf("parent = %d, ",A[x].p);
  printf("depth = %d, ",D[x]);

  if(A[x].p == NTL)printf("root, ");
  else if(A[x].l == NTL)printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for(i=0,c=A[x].l;c != NTL;i++,c = A[c].r){
    if(i)printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}




Measured memory_bytes: 3416
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    N = int(readline())
    A = list(map(int, readline().split()))
    C = [[0]*W for _ in range(H)]
    h=0
    w=0
    for i,a in enumerate(A):
        for _ in range(a):
            C[h][w] = i +1
            w += 1
            if w==W:
                h += 1
                w = 0
    for i,c in enumerate(C):
        if i%2==0:
            print(' '.join(map(str, c)))
        else:
            print(' '.join(map(str, reversed(c))))



if __name__ == '__main__':
    main()


Measured memory_bytes: 9412
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x);
#define rl(x) scanf("%lld",&x);
#define pi(x) printf("%d",x);
#define pl(x) printf("%lld",x);
#define lfd() printf("\n");
#define sp() printf(" ");
map<int,int> cnt;
int n;
int a;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		cnt[a]++;
	}
	int res=0;
	for(__typeof(cnt.begin()) it=cnt.begin();it!=cnt.end();it++){
		if(it->first<=it->second)
			res+=it->second-it->first;
		else
			res+=it->second;
	}
	cout<<res<<endl;
	return 0;
}



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

int main(){
  string n;
  cin>>n;
  bool flag=false;
  if(n[0]==n[1]&&n[1]==n[2])flag=true;
  if(n[1]==n[2]&&n[2]==n[3])flag=true;

  if(flag){
    cout<<"Yes"<<"\n";
  }else{
    cout<<"No"<<"\n";
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9
#define f first
#define s second
using namespace std;
typedef pair <int,int> P;
typedef pair <double,P> PP;
int n,m,p,s,g,T[10];
vector <P> x[32];

double dijkstra(){
  priority_queue<PP,vector<PP>,greater<PP> >Q;
  double D[1<<8][31];
  for(int i=0;i<(1<<n);i++)for(int j=0;j<=m;j++) D[i][j]=INF;
  Q.push(PP(0,P(s,0)));
  while(!Q.empty()){
    PP t=Q.top();Q.pop();
    double dis=t.f;
    int pos=t.s.f,bit=t.s.s;
    if(pos==g) return dis;  
    if(D[bit][pos]<dis)continue;
    for(int i=0;i<x[pos].size();i++)
      for(int j=0;j<n;j++){
	int nbit=(bit|(1<<j)),npos=x[pos][i].f;
	double ndis=dis+(1.0*x[pos][i].s/T[j]);
	if(bit!=nbit&&D[nbit][npos]>ndis)Q.push(PP(ndis,P(npos,nbit))),D[nbit][npos]=ndis;
    }
  }
  return 0;
}

int main(){
  while(1){
    cin>>n>>m>>p>>s>>g;
    if(!n&&!m&&!p&&!s&&!g) break;
    for(int i=0;i<=m;i++) x[i].clear();
    for(int i=0;i<n;i++)cin>>T[i];
    for(int i=0,a,b,c;i<p;i++)cin>>a>>b>>c,x[a].push_back(P(b,c)),x[b].push_back(P(a,c));
    double ans=dijkstra();
    if(ans==0)cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2700
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N,D; cin >> N >> D;
    ll count=0;
    loop(i,0,N)
    {
        ll x,y; cin >> x >> y;
        if (x*x+y*y <= D*D) count++;
    }
    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
 
int N,M;
int x[110000];
signed main() {
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        int u=max(a,b),l=min(a,b);
        x[u]=max(x[u],l);
    }
    int ans=0,r=1;
    for(int i=1;i<=N;i++){
        cerr<<x[i]<<" "<<r<<endl;
        if(x[i]>=r){
            ans++;
            r=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

ll mod_prod(ll a, ll b, ll md) {
	ll res = (a * b - (ll)((long double)a / md * b) * md) % md;
	return res < 0 ? res + md : res;
}

ll mod_pow(ll x, ll k, ll m) {
	ll res = 1;
	while (k) {
		if (k & 1) res = mod_prod(res, x, m);
		k /= 2;
		x = mod_prod(x, x, m);
	}
	return res;
}

bool miller_rabin_test(ll n) {
	const static vector<ll> sprp = { 2, 3, 5, 7, 11 };
	if (n < 2) return false;
	ll d = n - 1, s = 0;
	while ((d & 1) == 0) d >>= 1, ++s;
	for (ll a : sprp) if (a <= n) {
		if (a == n) return true;
		if (mod_pow(a, d, n) != 1) {
			bool ok = true;
			for (ll r = 0; r < s; r++) {
				if (mod_pow(a, d << r, n) == n - 1) {
					ok = false;
					break;
				}
			}
			if (ok) return false;
		}
	}
	return true;
}

ll pollard_rho(ll n) {
	static mt19937 mt(random_device{}());
	if (n == 4) return 2;
	ll c = mt() % n;
	ll x = mt() % n, y = x, d = 1;
	while (d == 1) {
		x = (mod_prod(x, x, n) + c) % n;
		y = (mod_prod(y, y, n) + c) % n;
		y = (mod_prod(y, y, n) + c) % n;
		d = __gcd(abs(x - y), n);
	}
	return d;
}

template <typename T>
vector<pair<T, int>> factorize(T n) {
	if (n <= 1) return{};
	vector<T> st = { n }, ps;
	while (!st.empty()) {
		T t = st.back(); st.pop_back();
		if (t <= 1) continue;
		if (miller_rabin_test(t)) {
			ps.push_back(t);
			continue;
		}
		T x;
		while (x = pollard_rho(t), x == t);
		st.push_back(x);
		st.push_back(t / x);
	}
	sort(ps.begin(), ps.end());
	vector<pair<T, int>> res;
	for (auto p : ps) {
		if (res.empty() || res.back().first != p) res.emplace_back(p, 1);
		else res.back().second++;
	}
	return res;
}

const ll MAX = 1e10;
const ll INF = 1e11;

int main()
{
	int N;
	cin >> N;
	bool one = false;
	int res = 0;
	map<ll, int> cnt;
	vector<pair<ll, ll>> vps;
	for (int i = 0; i < N; i++) {
		ll s;
		cin >> s;
		ll val = 1, rev = 1;
		for (auto p : factorize(s)) {
			int c = p.second % 3;
			if (c == 0) continue;
			val *= c == 1 ? p.first : p.first * p.first;
			if (c == 2) {
				rev = min(rev * p.first, INF);
				continue;
			}
			if (INF / p.first / p.first < rev) rev = INF;
			else rev *= p.first * p.first;
		}
		if (rev > MAX) {
			res += 1;
			continue;
		}
		if (val == 1) {
			res += !one;
			one = true;
			continue;
		}
		if (val < rev) {
			vps.emplace_back(val, rev);
		}
		else {
			vps.emplace_back(rev, val);
		}
		cnt[val] += 1;
	}
	sort(vps.begin(), vps.end());
	vps.erase(unique(vps.begin(), vps.end()), vps.end());
	for (auto p : vps) {
		res += max(cnt[p.first], cnt[p.second]);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 12144
import java.util.Scanner;

class Main {
  public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in);    
    while(sc.hasNext()) {
      int n = sc.nextInt();
      String b = Integer.toBinaryString(n);
      int len = b.length();
      int i=1;
      boolean first=true;
      while(true) {
        len--;	
	if(b.substring(len, len+1).equals("1")) {
          if(first == false) {
	    System.out.print(" ");
          }
          System.out.print(i);
	  first=false;
        }
	i*=2;
	if(len == 0) {
          break;
	}
      }
      System.out.println("");
    }
  }
}

Measured memory_bytes: 26112
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static Scanner scanner = new Scanner(System.in);

	public static void main(String[] args) {

		ArrayList<Integer> hList = new ArrayList<Integer>();
		ArrayList<Integer> wList = new ArrayList<Integer>();
		int H = 0;
		int W = 0;

		while (true) {

			H = input();
			W = input();

			if (H == 0 && W == 0) {

				break;

			} else {

				hList.add(H);
				wList.add(W);

			}
		}

		for (int i = 0; i < hList.size(); i++) {

			for (int j = 1; j <= hList.get(i); j++) {

				for (int k = 1; k <=wList.get(i) ; k++) {

					if (j == 1 || j == hList.get(i)) {

						System.out.print("#");

					} else {

						if (k == 1 || k == wList.get(i)) {

							System.out.print("#");

						} else {

							System.out.print(".");

						}
					}
				}

				System.out.println("");

			}

			System.out.println("");

		}

		close();

	}

	public static int input() {

		return scanner.nextInt();

	}

	public static void close() {

		if (scanner != null) {

			scanner.close();

		}
	}
}

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

int main() {
	int t[3];
	int n;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>t[0]>>t[1]>>t[2];
		sort(t, t+3);
		if( ( (t[0]*t[0]) + (t[1]*t[1])) == (t[2]*t[2]) ){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1168
# 累積和(1次元)を用いた解法
from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    LR_acc = []
    for L in LR:
        LR_acc.append(list(accumulate(L)))
    
    for p, q in query:
        ans = 0
        for i in range(p,q+1):
            ans += LR_acc[i][q] - LR_acc[i][p-1]
        print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 123888
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int a[3];
    REP(i, 3)
    {
        cin >> a[i];
    }
    sort(a, a + 3);
    if (a[0] == a[1] && a[0] != a[2])
    {
        Yes(1);
    }
    else if (a[0] != a[2] && a[1] == a[2])
    {
        Yes(1);
    }
    else
    {
        Yes(0);
    }
}

Measured memory_bytes: 256
n, m = map(int, input().split())
sc = [list(map(int, input().split()))for i in range(m)]

ans = -1
for i in range(1000):
    if len(str(i)) != n:
        continue
    for s, c in sc:
        if str(i)[s-1] != str(c):
            break
    else:
        ans = i
        break
print(ans)


Measured memory_bytes: 3060
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    while True:
        n = int(input())
        w = list(map(int, input().split()))
        if n==0:
            break
        else:
            dp = [[0]*(n+1) for _ in range(n+2)]
            # 幅
            for i in range(2, n+1):
                for l in range(n-i+1):
                    r = l+i
                    if dp[l+1][r-1] == i-2:
                        if abs(w[l]-w[r-1])<=1:
                            dp[l][r] = i
                        else:
                            dp[l][r] = i-2
                    for j in range(l, r):
                        if dp[l][j] + dp[j][r] > dp[l][r]:
                            dp[l][r] = dp[l][j] + dp[j][r]

            print(dp[0][-1])        

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 7128
card = []
for i in ['S ','H ','C ','D ']:
    for j in range(13):
        num = i + str(j+1)
        card.append(num)

n = int(input())
for i in range(n):
    del_num = input()
    card.remove(del_num)

for i in card:
    print(i)


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

vector<int>pes,color,ces,sz;
vector<ll>points;

void dfs(int u, int z){
	color[u]=z;
	sz[color[u]]++;
	points[color[u]]+=ces[u];
	int v = pes[u];
	if(color[v]==-1)dfs(v,z);
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;ll k;
	cin>>n>>k;
	pes=ces=sz=vector<int>(n+1);
	color.resize(n+1,-1);
	points.resize(n+1);

	for(int i=1;i<=n;i++){
		cin>>pes[i];
	}
	for(int i=1;i<=n;i++){
		cin>>ces[i];
	}
	int z = 0;
	for(int i=1;i<=n;i++){
		if(color[i]==-1){
			dfs(i,++z);
		}
	}
	ll ans=-1e10;
	for(int i=1;i<=n;i++){
		ll tmp=0;
		int lim=min(sz[color[i]],(int)k);
		for(int u=pes[i],len=1;len<=lim;u=pes[u],len++){
			tmp+=ces[u];
			ans=max(ans,tmp);
			if(tmp<0)continue;
			ll foo=(k-len)/sz[color[i]];
			ans=max(ans,tmp+foo*points[color[i]]);
		}
	}
	cout<<ans;
	
	return 0;
}

Measured memory_bytes: 3764
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long 
using namespace std;
int n,m,cnt,tot,c[30][500010];
ll ans;
char ss[500010];
bool p[500010];
struct seg
{
	int v[800010];
	void bu(int i,int l,int r)
	{
		if(l==r){v[i]=1;return ;}
		bu(i*2,l,(l+r)/2);bu(i*2+1,(l+r)/2+1,r);
		v[i]=v[i*2]+v[i*2+1];
	}
	int qy(int i,int l,int r,int ql,int qr)
	{
		if(l>qr || ql>r)return 0;
		if(ql<=l && r<=qr)return v[i];
		return qy(i*2,l,(l+r)/2,ql,qr)+qy(i*2+1,(l+r)/2+1,r,ql,qr);
	}	
	void add(int i,int l,int r,int k)
	{
		if(l==r){v[i]--;return ;}
		if(k<=(l+r)/2)add(i*2,l,(l+r)/2,k);
		else add(i*2+1,(l+r)/2+1,r,k);
		v[i]=v[i*2]+v[i*2+1];
	}
}tr;
int dic(int k)
{
	return k-'a'+1;
}
int main()
{
	int i,s,a,b,j,k;
	scanf(" %s",ss);n=strlen(ss);
	for(i=1;i<=n;i++)k=dic(ss[i-1]),c[k][++c[k][0]]=i;
	for(i=1;i<=26;i++)cnt+=(c[i][0]&1);
	if(cnt>1)return puts("-1"),0;
	tr.bu(1,1,n);
	for(i=1;i<=n;i++)
	if(!p[i])
	{
		k=dic(ss[i-1]);
		s=c[k][c[k][0]--];
		if(i==s)ans+=tr.qy(1,1,n,i+1,n)/2;
		else ans+=tr.qy(1,1,n,s+1,n);
		tr.add(1,1,n,i);tr.add(1,1,n,s);p[i]=p[s]=1;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 55552
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long
#define faltu ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define binary(x) std::string binary = std::bitset<25>(x).to_string(); //to binary
#define inf 1000000007
#define mod 1000000007
#define pi pair<int,int>
#define lpi pair<int,int>
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define lvi vector<long long int>
#define pie 3.14159265358979323846
ll int MMM=inf;
int pw(ll int a, ll int b) {
    if (b == 0) return 1;
    ll int t = pw(a, b / 2);
    if (b % 2 == 0) return (t * t)%mod;
    else return ((t * t)%mod * a)%mod;
}
using namespace std;
vi pm;
void prm(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
              prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p]) pm.pb(p);
}
bool sortbysecdesc(const pair<ll int,ll int> &a,const pair<ll int,ll int> &b)
{
    return a.first>b.first;
}
bool cmp(int x,int y){return x>y;}
int gcd(int a,int b)
{
    if(a<b)
        swap(a,b);
    return (b==0)?a:gcd(b,a%b);
}
int main()
{
	faltu;
	int r;
	cin>>r;
	cout<<3*r*r<<endl;

}










Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int A,B,ans;
    cin >> A >> B;
    if (A<B){
        ans = 2*B-1;
    }
    if(A==B){
        ans = 2*A;
    }
    if(A>B){
        ans = 2*A-1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
S=np.where(S==".",1,0 )

left=np.zeros((H, W))
right=np.zeros((H, W))
top=np.zeros((H, W))
bottom=np.zeros((H, W))

for i in range(W):
  if i==0:
    left[:,i]=S[:,i]
    right[:,-i-1]=S[:,-i-1]
  else:
    left[:,i]=(left[:,i-1]+1)*S[:,i]
    right[:,-i-1]=(right[:,-i]+1)*S[:,-i-1]
    
for i in range(H):
  if i==0:
    top[i,:]=S[i,:]
    bottom[-1-i,:]=S[-i-1,:]
  else:
    top[i,:]=(top[i-1,:]+1)*S[i,:]
    bottom[-1-i,:]=(bottom[-i,:]+1)*S[-i-1,:]
    
ans=left+top+right+bottom-3
    

print(int(ans.max()))

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

using namespace std;

const int mod = 1e9+7;

int main(void){
    int n, m;
    cin >> n >> m;
    
    vector<bool> is_safe(n+1,true);
    
    for (int i = 0; i < m; i++){
        int a;
        cin >> a;
        
        is_safe[a] = false;
    }
    
    vector<int> dp(n+1,0);
    
    dp[0] = 1;
    if (is_safe[1]) dp[1] = 1;
    
    for (int i = 2; i <= n; i++){
        if (is_safe[i-1]) dp[i] += dp[i-1];
        if (is_safe[i-2]) dp[i] += dp[i-2];
        
        dp[i] %= mod;
    }
    
    cout << dp[n] << endl;
}


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

const int maxn = 2e5 + 10;
vector<int> adj[maxn];
int n, m, vis[maxn];
bool dfs(int u, int dep) {
	if( dep == 0 && u == n) return 1; 
	if(dep > 0)
	for(int v : adj[u]) if(!vis[v]) {
		vis[v] = 1; 
		if(dfs(v, dep-1)) return 1;
		vis[v] = 0;
	} return 0;  
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	ll k; cin>>k;
	ll arr[50];
	for(int i = 0; i < 50; i++) 
		arr[i] = 49; 
	if(k > 50) {
		ll x= k/50; 
		for(int i = 0; i < 50; i++) 
			arr[i] += x;
		k %= 50; 
	} 
	if(k != 0) {
		for(int i = 0; i < k; i++) {
			arr[i] += 50; 
			for(int j = 0; j < 50; j++) if(j != i) 
				arr[j]--; 
		}
	} 
	cout<<50<<endl;
	for(int i = 0; i < 50; i++) 
		cout<<arr[i]<<" ";
	cout<<endl;

}

Measured memory_bytes: 4992
/**
 *    author        : Saurav Paul 
 *    created       : August 06, 2020 10:20 PM
 *    Problem Name  : A - Frog 1
 *    Problem Limit : 2000 ms , 1024 MB
 *    Problem Url   : https://atcoder.jp/contests/dp/tasks/dp_a
 *    @genarated by : ai-virtual-assistant
**/

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    const int INF = 1e9+90 ;

    vector<int> v(n), dp(n, INF) ;
    for(auto &x : v) cin >> x;

    dp[0] = 0 ;
    for(int i = 1 ; i < n ; i++){
        for(auto j : {i-1,i-2}){
            if(j >= 0)
                dp[i] = min(dp[i], dp[j] + abs(v[i] - v[j])) ;
        }
    }

    cout << dp[n-1] << endl ;

    return 0 ;
}


Measured memory_bytes: 3812
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if k>=b-a and k>=c-a and k>=d-a and k>=e-a and k>=c-b and k>=d-b and k>=e-b and k>=d-c and k>=e-c and k>=e-d:
  print("Yay!")
else:
  print(":(")

Measured memory_bytes: 3064
package main

import(
	"fmt"
)

func main() {
	var N int
	var ans int
	var active int
	var h []int

	fmt.Scan(&N)
	for i:=0; i<N; i++ {
		var tmp int
		fmt.Scan(&tmp)
		h = append(h, tmp)
	}

	for i:=0; i<N; i++ {
		if h[i] > active {
			ans += h[i] - active
			active = h[i]
		} else {
			active = h[i]
		}
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
# Aはリスト、nはリストの最大値
def f2(n,A):
    s=[int(i) for i in range(0,n+1)]
    a={}
    for i in range(2,int(n**0.5)+1):
        if s[i]!=i:
            continue
        for j in range(i,n+1,i):
            s[j]=i

    for i in range(2,n+1):
        if s[i]==i:
            a[i]=1

    l=len(A)
    p=[[] for i in range(l)]
    for i in range(l):
        x=A[i]
        while x!=1:
            p[i].append(s[x])
            if a[s[x]]==0:
                return False
            x//=s[x]


        for j in p[i]:
            a[j]=0

    return True

from math import gcd
N=int(input())
A=[int(i) for i in input().split()]
a=max(A)
p=f2(a,A)


if p:
    print('pairwise coprime')
else:
    g=A[0]
    for i in range(1,len(A)):
        g=gcd(g,A[i])
        if g==1:
            break
    if g==1:
        print('setwise coprime')
    else:
        print('not coprime')


Measured memory_bytes: 224708
#include <bits/stdc++.h>
using namespace std;
#include "string"
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(false);cin.tie(nullptr)
const int N = 2e6 + 5;
int a,b,n;

int fl(int x){
	int tt = (a*x)/b - a*(x/b);
	//cout<<x<<" "<<tt<<endl;
	return tt;
}

int32_t main() { 
    boost;
    cin>>a>>b>>n;
    int x = (n/b)*b;
    int ans = fl(n);
    if(x>2)
    	 ans = fl(x-1);    
   	cout<<ans<<endl;
}


Measured memory_bytes: 3660
pre=-1
n=int(input())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))
cl=[0]+list(map(int,input().split()))
ans=0
prec=0
for  a,b in zip(al,bl):
    ans+=b
    if pre+1==a:ans+=cl[pre]
    pre=a
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,m,a[111][111],t;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++){
			double s=0;
			for(int k=1;k<=m;k++) s+=(double)((double)(a[i][k]-a[j][k])*(double)(a[i][k]-a[j][k]));
			if(int(sqrt(s))==sqrt(s)) t++;
		}
	cout<<t;
}


Measured memory_bytes: 256
while true do
 
	count = gets.to_i;
 
	if count == 0 then
		break;	
	end
 
	sum = 0.to_f;
	average = 0.to_f;
	aryStudentPoint = gets.split(' ').map(&:to_f);
 
	for sumIndex in 0..aryStudentPoint.length - 1 do
 
		sum = sum + aryStudentPoint[sumIndex];
 
	end
 
	average = sum / count;
	
	sum = 0.to_f;
 
	for index in 0..aryStudentPoint.length - 1 do
 
		sum = sum + (aryStudentPoint[index] - average) * (aryStudentPoint[index] - average)
 
	end
	
	puts "%.8f" % Math.sqrt(sum / count)
 
end

Measured memory_bytes: 8856
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static final int BIG_NUM  = 2000000000;
	public static final int MOD  = 1000000007;

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			int N = Integer.parseInt(br.readLine());

			String array[] = br.readLine().split("\\s+");

			System.out.printf("%d",Integer.parseInt(array[array.length-1]));
			for(int i = array.length-2; i >= 0; i--){
				System.out.printf(" %d", Integer.parseInt(array[i]));
			}
			System.out.printf("\n");


		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}




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

using std::min;

const int N=105,Node=N*N*3,Inf=1e9+10;

struct Edge{ int to,next,flow; }way[N*N<<4];

int n,m,s,t,node,nd[N][N][2],mp[N][N],num[Node],tot;

void Build(int u,int v,int flow) { way[++tot]=(Edge){v,num[u],flow}; num[u]=tot; }

void Add(int u,int v,int flow) {
	Build(u,v,flow);
	Build(v,u,0);
}

void Init() {
	scanf("%d%d",&n,&m);
	node=1;
	for (int i=0;i<n;++i)
		for (int j=0;j<m;++j) {
			char ch=getchar();
			while (ch!='.' && ch!='o' && ch!='S' && ch!='T') ch=getchar();
			if (ch=='S') nd[i][j][1]=node,s=node++;
			else if (ch=='T') nd[i][j][0]=node,t=node++;
			else nd[i][j][0]=node++,nd[i][j][1]=node++;
			if (ch=='.') mp[i][j]=0;else mp[i][j]=1;
		}
}

int dis[Node],vis[Node],que[Node];
bool Bfs(int s,int t) {
	for (int i=0;i<node;++i) dis[i]=Inf,vis[i]=0;
	int head=0,tail=0; dis[s]=0; que[++tail]=s; vis[s]=1;
	while (head!=tail) {
		int u=que[++head];
		for (int i=num[u];i;i=way[i].next) if (way[i].flow) {
			int v=way[i].to;
			if (!vis[v]) {
				dis[v]=dis[u]+1;
				vis[v]=1; 
				que[++tail]=v;
			}
		}
	}
	return dis[t]!=Inf;
}

int cur[Node];
int Dfs(int x,int a,int t) {
	if (!a || x==t) return a;
	int flow=0,f;
	for (int &i=cur[x];i;i=way[i].next) {
		int v=way[i].to;
		if (dis[v]==dis[x]+1 && (f=Dfs(v,min(a,way[i].flow),t))>0) {
			flow+=f; a-=f;
			way[i].flow-=f;
			way[i^1].flow+=f;
			if (!a) break;
		}
	}
	return flow;
}

int Maxflow(int s,int t) {
	int flow=0;
	while (Bfs(s,t)) {
		for (int i=0;i<node;++i) cur[i]=num[i];
		int f=Dfs(s,Inf,t);
		if (f==Inf) return -1;
		flow+=f;
	}
	return flow;
}

int row[N],col[N];
void Solve() {
	tot=1;
	for (int i=0;i<n;++i) {
		row[i]=node++;
		for (int j=0;j<m;++j) if (mp[i][j]) {
			if (nd[i][j][1]) Add(nd[i][j][1],row[i],Inf);
			if (nd[i][j][0]) Add(row[i],nd[i][j][0],Inf);
		}
	}
	for (int j=0;j<m;++j) {
		col[j]=node++;
		for (int i=0;i<n;++i) if (mp[i][j]) {
			if (nd[i][j][1]) Add(nd[i][j][1],col[j],Inf);
			if (nd[i][j][0]) Add(col[j],nd[i][j][0],Inf);
		}
	}
	for (int i=0;i<n;++i)
		for (int j=0;j<m;++j) if (mp[i][j] && nd[i][j][0] && nd[i][j][1])
			Add(nd[i][j][0],nd[i][j][1],1);
	printf("%d\n",Maxflow(s,t));
}

int main() {
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 1920
#include <algorithm>　　　 //STL 通用算法
#include <bitset>　　　　　//STL 位集容器
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>　　　　 //复数类
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>　　　　　 //STL 双端队列容器
#include <exception>　　　 //异常处理类
#include <fstream>
#include <functional>　　　//STL 定义运算函数（代替运算符）
#include <limits>
#include <list>　　　　　　//STL 线性列表容器
#include <map>　　　　　　 //STL 映射容器
#include <iomanip>
#include <ios>　　　　　　 //基本输入／输出支持
#include <iosfwd>　　　　　//输入／输出系统使用的前置声明
#include <iostream>
#include <istream>　　　　 //基本输入流
#include <ostream>　　　　 //基本输出流
#include <queue>　　　　　 //STL 队列容器
#include <set>　　　　　　 //STL 集合容器
#include <sstream>　　　　 //基于字符串的流
#include <stack>　　　　　 //STL 堆栈容器　　　　
#include <stdexcept>　　　 //标准异常类
#include <streambuf>　　　 //底层输入／输出支持
#include <string>　　　　　//字符串类
#include <utility>　　　　 //STL 通用模板类
#include <vector>　　　　　//STL 动态数组容器
#include <cwchar>
#include <cwctype>

#define int long long
using namespace std;
const int N=2050005;
int f[N],s[N],a[N];
int ans,n,x;
signed main(){
	cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        f[i]=f[i-1]+a[i];
        s[i]=s[i-1]^a[i];
    }
    int l=1;
    for(int r=1;r<=n;++r){
        while((f[r]-f[l-1])!=(s[r]^s[l-1]))
			l++;
        ans+=r-l+1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 9984
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=1e9+7;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
const int N=2005;
int e[N][N],f[N][N],g[N][N],h[N][N],cs[N][N],sb[N][N],n,m;
void init(){
	fp(i,0,max(n,m)){
		cs[i][0]=1;
		fp(j,1,i)cs[i][j]=add(cs[i-1][j],cs[i-1][j-1]);
		sb[i][0]=1;fp(j,1,n)sb[i][j]=add(sb[i][j-1],cs[i][j]);
	}
	fp(i,0,n)fp(j,1,m)e[i][j]=sb[j-1][i];
	e[0][0]=1;
	fp(i,1,n)fp(j,0,m)upd(e[i][j],e[i-1][j]);
	fp(i,0,n)fp(j,0,m)f[i][j]=e[i][j];
	fp(i,0,n)fp(k,0,i)upd(g[i][m],mul(cs[m-1][k],f[i-k][k]));
	g[0][0]=1;
	fp(k,0,n)upd(h[n][m],g[n-k][m]);
}
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d%d",&n,&m);
	init();
	printf("%d\n",h[n][m]);
	return 0;
}

Measured memory_bytes: 82176
def main():
  N = int(input())
  C = [0, 0, 0, 0]
  ANS = ["AC", "WA", "TLE", "RE"]
  for i in range(N):
    s = str(input())
    if s == "AC":
      C[0] += 1
    elif s == "WA":
      C[1] += 1
    elif s == "TLE":
      C[2] += 1
    elif s == "RE":
      C[3] += 1
  for i in range(4):
    print(ANS[i] + " x " + str(C[i]) )
    
if __name__ == "__main__":
  main()

Measured memory_bytes: 9216
import java.io.*;
import java.util.*;

public class Main
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;

    public void go() throws IOException
    {
        ntok();
        int n = ipar();
        int k = ipar();
        ntok();
        char[] s = spar().toCharArray();
        long happy = 0;
        for (int i = 0; i < n-1; i++)
        {
            if (s[i] == s[i+1])
            {
                happy++;
            }
        }
        out.println(Math.min(n-1, happy + 2*k));

        out.flush();
        in.close();
    }

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public int[] iapar(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public long[] lapar(int n)
    {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

    public static void main(String[] args) throws IOException
    {
        new Main().go();
    }
}


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

int n, dp[500001][3], frst[500001];
char s[500002];

inline void up(int &x, int y) { x = max(x, y); }

int main(){
	scanf("%d%s", &n, s + 1);
	s[0] = '0';
	frst[1] = 1;
	f(i, 2, n + 1)if (s[i] == '1'){
		if (s[i - 1] == '1')frst[i] = frst[i - 1];
		else frst[i] = i;
	}
	f(i, 0, n + 1)f(j, 0, 3)dp[i][j] = -1e9;
	dp[0][0] = 0;
	f(i, 1, n + 1){
		if (s[i] == '0'){
			up(dp[i][0], max(dp[i - 1][0], dp[i - 1][1]));
			up(dp[i][1], dp[i - 1][2]);
		}else {
			up(dp[i][1], dp[i - 1][1] + 1);
			f(j, 0, 3)up(dp[i][2], dp[i - 1][j]);
			if (i >= 2 && s[i - 2] == '1' && s[i - 1] == '0'){
				int t = frst[i - 2];
				if (t != i - 2){
					if (t != i - 3)f(j, 0, 3)up(dp[i][0], dp[t][j] + i - 2 - t);
					f(j, 0, 3)up(dp[i][0], dp[t - 1][j] + i - 1 - t);
				}
			}
		}
	}
	int an = 0;
	f(i, 0, 3)up(an, dp[n][i]);
	printf("%d\n", an);
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
 
typedef long long ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (n); ++i)
const double PI=3.14159265358979323846;

using namespace std;

int main() {

    string s;

    cin >> s;

    int i = s.length() / 2;
    if (s.length() % 2 != 0) i++;

    string ans = "";

    for (int j = 0; j < i; j++) {
        ans += s[j*2];
    }

    cout << ans << endl;
}

Measured memory_bytes: 512
import heapq

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
d_AB = {a:[] for a,b in AB}
for a,b in AB:
    d_AB[a].append(-b)
H = []
money = 0
for i in range(1,M+1):
    if i in d_AB.keys():
        for ab in d_AB[i]:
            heapq.heappush(H,ab)
        money += heapq.heappop(H)
    else:
        money += heapq.heappushpop(H,0)
print(-money)

Measured memory_bytes: 42908
const config = {
    input: '/dev/stdin',
    newline: '\n'
};

const line = require('fs').readFileSync(config.input, 'utf-8').split(config.newline);
const data = line[1].split(' ').map(x => [parseInt(x[1]), x]);

const bswap = arr => {
    if (arr.length === 1) return arr;
    const f = arr[0];
    const s = arr[1];
    const tl = arr.slice(2);
    if (f[0] > s[0]) {
        return [s, ...bswap([f, ...tl])];
    } else {
        return [f, ...bswap([s, ...tl])];
    }
};

const bsort = arr => {
    if (arr.length === 0) return [];
    const swapped = bswap(arr);
    const hd = swapped.slice(0, swapped.length-1);
    const tl = swapped[swapped.length-1];
    return [...bsort(hd), tl];
};

const ssort = arr => {
    if (arr.length === 0) return [];
    const min = arr.reduce((acc, x) => acc[0] > x[0] ? x : acc);
    const hd = arr[0];
    const filter = arr.slice(1).map(x => x[1] === min[1] ? hd : x);
    return [min, ...ssort(filter)];
};

const isStable = (bsort, arr) => arr.every((x, i) => bsort[i][1] === x[1]);

const bsorted = bsort(data);
const ssorted = ssort(data);

console.log(bsorted.map(x => x[1]).join(' '));
console.log('Stable');
console.log(ssorted.map(x => x[1]).join(' '));
console.log(isStable(bsorted, ssorted) ? 'Stable' : 'Not stable');



Measured memory_bytes: 18148
#include <bits/stdc++.h>
using namespace std;
int main(){
string S;
  cin>>S;
 int count =0; 

  for(int i=0;i<S.size();i++){
  if(S.at(i)=='+'){
    count+=1;


}
  if(S.at(i)=='-'){
  count-=1;
  }
  }
  cout<<count<<endl;
}


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

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n-1);i>=0;i--)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

struct UF {
    vi par, size;
    UF(int n): par(n), size(n, 1) { iota(all(par), 0); }
    int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }
    bool connected(int u, int v) { return find(u) == find(v); }
    bool join(int u, int v) {
        if (connected(u, v)) return false;
        u = find(u), v = find(v);

        if (size[u] < size[v]) par[u] = v, size[v] += size[u];
        else par[v] = u, size[u] += size[v];
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int n,m,k; cin >> n >> m >> k;
    UF c(n);
    vi f(n), res(n);
    vector<vi> b(n);
    forn(i, m){
        int x,y; cin >> x >> y, x--, y--;
        c.join(x, y), f[x]++, f[y]++;
    } 
    forn(i, k){
        int x,y; cin >> x >> y, x--, y--;
        b[x].pb(y), b[y].pb(x);
    } 
    
    forn(i, n) res[i] = c.size[c.find(i)] - 1 - f[i];

    vector<set<int>> v(n);
    forn(i, n) v[c.find(i)].insert(i);

    forn(i, n) for (int x : b[i])
        if(v[c.find(i)].count(x)) res[i]--; 

    forn(i, n) cout << res[i] << " \n"[i==n-1];
    return 0;
}


Measured memory_bytes: 16896