akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#include<functional>
//#include<bits/stdc++.h>
#define rep(i, x) for(ll i = 0; i < x; i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ld pi = 3.141592653589793238;
//printf("%.10f\n", n);

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll modpow(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y % 2) { res *= x; res %= mod; }
		x = x * x % mod; y /= 2;
	}
	return res;
}

signed main() {
	ll n, m; cin >> n;
    if(n % 1000 == 0) { cout <<"0\n"; }
	else { cout << 1000 - n % 1000 << endl; }
	return 0;
}

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

int main(){
	int n,m,l;
	long long a[105][105] = {0};
	long long b[105][105] = {0};
	long long c[105][105] = {0};
	cin >> n >> m >> l;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> a[i][j];			
		}
	}
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < l; ++j)
		{
			cin >> b[i][j];	
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int k = 0; k < l; ++k)
		{
			for (int j = 0; j < m; ++j)
			{
				c[i][k] += a[i][j] * b[j][k];		
			}
		}

	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < l-1; ++j)
		{
			cout << c[i][j] << " ";
		}
		cout << c[i][l-1] << endl;
	}
}

Measured memory_bytes: 1428
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

//ここから

void solve(){
  int n;
  cin>>n;
  vector<ll>t(n);
  ll sum=0;
  rep(i,n)cin>>t[i],sum+=t[i];
  int m;
  cin>>m;
  int p;
  ll x;
  ll pre=sum;
  rep(i,m){
    cin>>p>>x;
    p--;
    sum+=x-t[p];
    cout<<sum<<"\n";
    sum=pre;
  }
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    IOS;
    //ll t;cin>>t;while(t--)
    {
        ll a,b,c,d,i,j,k,l,m,n,sum=0,temp=0,f=0,cnt=0;
        cin>>n;
        string s;
        cin>>s;
        for(i=0;i<n;i++)
        {
            if(s[i]=='R')cnt++;
        }
        for(i=0;i<cnt;i++)
        {
            if(s[i]!='R')sum++;
        }
        cout<<sum<<endl;
    }
}


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

typedef long long ll;
const ll maxn=2e5+10,mod=1e9+7;
ll n,fa[maxn],dep[maxn],cnt[maxn],dp[maxn][2],ans,size[maxn],dfn[maxn],faa[20][maxn];
vector<ll> g[maxn],vv[maxn],gg[maxn];
int a[maxn<<1],tot,in[maxn],out[maxn];

inline ll qpow(ll a,ll n){
	ll res=1;
	while(n){
		if(n&1ll)
			res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}
int cloc;
void dfs(int pos){
	faa[0][pos]=fa[pos];
	for(int i=1;i<20;++i)
		faa[i][pos]=faa[i-1][faa[i-1][pos]];
	dfn[pos]=++cloc;
	in[pos]=cloc;
	for(int i=0;i<g[pos].size();++i)
		dfs(g[pos][i]);
	out[pos]=cloc;
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;~i;--i)
		if(dep[faa[i][x]]>=dep[y])
			x=faa[i][x];
	if(x==y)return x;
	for(int i=19;~i;--i)
		if(faa[i][x]!=faa[i][y])
			x=faa[i][x],y=faa[i][y];
	return fa[x];
}
bool cmp(int a,int b){
	return dfn[a]<dfn[b];
}

int main(){
	cin>>n;
	++cnt[0];
	vv[0].push_back(0);
	for(int i=1;i<=n;++i){
		cin>>fa[i];
		g[fa[i]].push_back(i);
		dep[i]=dep[fa[i]]+1;
		++cnt[dep[i]];
		vv[dep[i]].push_back(i);
		size[i]=1;
	}
	size[0]=1;
	for(int i=n;i;--i)
		size[fa[i]]+=size[i];
	dfs(0);
	for(int d=0;d<=n;++d){
		if(vv[d].empty())break;
		tot=0;
		for(int i=0;i<vv[d].size();++i)
			a[tot++]=vv[d][i];
		sort(a,a+tot,cmp);
		for(int i=tot-1;i;--i)
			a[tot++]=lca(a[i],a[i-1]);
		a[tot++]=0;
		sort(a,a+tot,cmp);
		tot=unique(a,a+tot)-a;
		stack<int> stk;
		stk.push(0);
		for(int i=1;i<tot;++i){
			while(!stk.empty()&&!(in[stk.top()]<=in[a[i]]&&out[a[i]]<=out[stk.top()]))
				stk.pop();
			gg[stk.top()].push_back(a[i]);
			stk.push(a[i]);
		}
		for(int ii=tot-1,i;~ii;--ii){
			i=a[ii];
			dp[i][0]=dp[i][1]=0;
			if(dep[i]==d){
				dp[i][0]=1;
				dp[i][1]=1;
			}
			else{
				ll dp0=1,dp1=0,dp2=0;
				for(int j=0,v;j<gg[i].size();++j){
					v=gg[i][j];
					dp2=(dp2*(dp[v][0]+dp[v][1])%mod+dp1*dp[v][1]%mod)%mod;
					dp1=(dp1*dp[v][0]%mod+dp0*dp[v][1]%mod)%mod;
					dp0=dp0*dp[v][0]%mod;
				}
				dp[i][0]=(dp0+dp2)%mod;
				dp[i][1]=dp1;
			}
		}
		for(int i=0;i<tot;++i)
			gg[a[i]].clear();
		ans=(ans+dp[0][1]*qpow(2,n+1-cnt[d]))%mod;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 81024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,sum = 1;
    string s;
    cin>>n>>s;
    char bef = s[0];
    for(int i=0;i<s.size();i++){
        if(bef != s[i])sum++;
        bef = s[i];
    }
    cout<<sum<<endl;
}



Measured memory_bytes: 512
N=int(input())
s=input()
R=s.count("R")
G=s.count("G")
B=s.count("B")
ans=R*G*B

#全探索する
for i in range(N-2):
  a=s[i]
  for j in range(i+1,N-1):
    if a==s[j]:
      continue
    b=s[j]
    k=2*j-i
    if "R" not in a+b:
      try:
        if s[k]=="R":
          ans-=1
      except:
        pass
      
    if "G" not in a+b:
      try:
        if s[k]=="G":
          ans-=1
      except:
        pass
      
    if "B" not in a+b:
      try:
        if s[k]=="B":
          ans-=1
      except:
        pass

print(ans)


Measured memory_bytes: 68812
#include  <iostream>

using namespace std;

int main()
{
	int n;
	int a[50], b[50];
	for (int i = 0; i < 49; i++)  a[i] = i + 1;
	cin >> n;
	for (int i = 0; i < n; i++)  cin >> b[i];

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i])  cnt++;
	}
	
	if (cnt <= 2)  cout << "YES" << endl;
	else  cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b,c,sum=0;
  string s;
  cin>>a>>b;
  b+=a*3;
  cout<<b/2<<'\n';
  return 0;
}


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

using namespace std;

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

  int n, m, p, x;
  cin >> n;
  vector<int> T(n);
  int sum = 0;
  for (auto &t : T) {
    cin >> t;
    sum += t;
  }
  cin >> m;
  for (int i = 0; i < m; ++i) {
    cin >> p >> x;
    cout << sum - T[p-1] + x << endl;
  }

  return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		
		int n = 0;
		while( n*(a-1) +1 < b  ) {
			n++;
		}

		System.out.println(n);
		in.close();
	}
}

Measured memory_bytes: 21332
n, x, y = map(int, input().split())
d = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(i, n + 1):
        dist = min(j - i, abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(x - j))
        d[dist] += 1
print(*d[1:n], sep = '\n')

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int n,d;
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main(){
	n=read(),d=read();
	d=(d<<1)+1;
	printf("%d\n",(n+d-1)/d);
	return 0;
}


Measured memory_bytes: 256
// AGC005_A
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <tuple>  // std::tuple std::get
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define REPN(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0LL)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
#define zero_pad(num) setfill('0') << std::right << setw(num)
#define space_pad(num) setfill(' ') << std::right << setw(num)

typedef long long ll;

const ll MOD7 = 1000000007;  // 1 000 000 007
const ll MOD9 = 1000000009;  // 1 000 000 009

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

    // input
    string X;
    cin >> X;
    
    // calculation
    if (X.length() == 2) {
        if (X == "ST") {
            cout << 0 << "\n";
        } else {
            cout << 2 << "\n";
        }
    } else {
        // 4 <= S <= 200,000, O(N^2) は無理だから，eraseしながらはできない．
        // 愚直解：部分点 200 点解法
        /*
        int idx = (int)X.find("ST");
        while (idx != -1) {
            X.replace(idx, 2, "");
            idx = (int)X.find("ST");
        }
        cout << X.length() << "\n";
        */
        // 満点解法
        stack<char> stk;
        char ch;
        REP(i, X.length()) {
            ch = X[i];
            if (stk.empty()) {
                stk.push(ch);
            } else {
                if (stk.top() == 'S' && ch == 'T') {
                    stk.pop();
                } else {
                    stk.push(ch);
                }
            }
        }
        
        cout << stk.size() << "\n";
    }
    return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N)
  {
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  vector<pair<int, int>> B;
  B.push_back(make_pair(A[0], 1));
  rep(i, N - 1)
  {
    if (B.back().first == A[i + 1])
      B.back().second++;
    else
      B.push_back(make_pair(A[i + 1], 1));
  }

  int ans = N;
  int head = 0;
  int tail = B.size() - 1;
  for (; head <= tail;)
  {
    if (B[head].second < 2)
    {
      head++;
      continue;
    }

    for (; tail > head; tail--)
    {
      if (B[tail].second < 2)
        continue;

      B[head].second--;
      B[tail].second--;
      ans -= 2;
      break;
    }

    if (head == tail)
    {
      ans -= (B[head].second / 2) * 2;
      B[head].second = 1;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1784
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define INF (1LL<<60)
typedef long long Int;

struct node { int x, t, p; };
bool operator<(const node& l, const node& r) {
    return l.t!=r.t ? l.t<r.t : l.x!=r.x ? l.x<r.x : l.p<r.p;
}

int N, V, XL, XR;
node X[4000];

inline bool connect(int i, int j) {
    return abs(X[j].x-X[i].x)<=(long long)V*abs(X[j].t-X[i].t);
}

int head[10000], from[10000];
Int h[10000];
vector<int> u, v, next;
vector<Int> c;

inline void add_edge(int _u, int _v, Int _c) {
    u.push_back(_u);
    v.push_back(_v);
    c.push_back(_c);
    next.push_back(head[_u]);
    head[_u] = u.size()-1;
}

int main() {
    scanf("%d%d%d%d", &N, &V, &XL, &XR);
    X[0].x = XL;
    X[1].x = XR;
    rep(i, N) scanf("%d%d%d", &X[i+2].x, &X[i+2].t, &X[i+2].p);
    N += 2;
    sort(X, X+N);
    memset(head, -1, sizeof(head));
    rep(i, 2) add_edge(0, 2+i*2, 0);
    rep(i, N) add_edge(2+i*2, 2+i*2+1, -X[i].p);
    rep(i, N) {
        const int f = 2+2*i+1;
        add_edge(f, 1, 0);
        for(int j=i+1; j<N; j++) if(connect(i, j)) add_edge(f, 2+j*2, 0);
    }
    rep(i, N) h[2+i*2] = INF;
    rep(i, 2) h[2+i*2] = 0, from[2+i*2] = i;
    rep(i, N) {
        const int f = 2+i*2+1;
        h[f] = h[f-1] - X[i].p;
        from[f] = i + 2;
        for(int x=head[f]; x!=-1; x=next[x]) if(h[v[x]]>h[f]) {
            h[v[x]] = h[f];
            from[v[x]] = x;
        }
    }
    Int a = -h[1];
    int cur = 1;
    while(cur!=0) {
        const int x = from[cur];
        add_edge(v[x], u[x], -c[x]);
        c[x] = INF;
        cur = u[x];
    }
    memset(from, 0, sizeof(from));
    priority_queue<pair<Int, int> > q;
    q.push(mp(0, 0));
    while(!q.empty()) {
        const pair<Int, int> vv(q.top());
        q.pop();
        const int cc = -vv.first;
        const int ix = vv.second;
        if(from[ix]) continue;
        from[ix] = 1;
        if(ix==1) {
            a -= h[1] + cc;
            break;
        }
        for(int x=head[ix]; x!=-1; x=next[x]) {
            const Int nc = cc + c[x] + h[ix] - h[v[x]];
            q.push(mp(-nc, v[x]));
        }
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 134000
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

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

string S;

/*==================================================*/

/*==================================================*/

int main() {
    cin>>S;
    string s1="", s2="";
    REP(i,0,S.size()){
        if(S[i] != 'x') s1 += S[i];
        if(S[S.size()-1-i] != 'x') s2 += S[S.size()-1-i];
    }
    if(s1 != s2){
        cout<<-1<<endl;
        return 0;
    }

    int l = -1, r = S.size();
    int ans = 0;

    //test
    int c = 0;
    while(1){
        //test
        //cout<<"l: "<<l<<", r: "<<r<<endl;
        //if(c == 10) break;
        c++;

        if(l == r || l+1 == r){
            break;
        }

        if(S[l + 1] == 'x' && S[r - 1] != 'x'){
            //cout<<"test1"<<endl;
            int t = 1;
            while(S[l + t] == 'x'){
                t++;
            }
            ans += (t - 1);
            l += t;
            r--;
        }else if(S[l + 1] != 'x' && S[r - 1] == 'x'){
            //cout<<"test2"<<endl;
            int t = 1;
            while(S[r - t] == 'x'){
                t++;
            }
            ans += (t - 1);
            r -= t;
            l++;
        }else{
            l++;
            r--;
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 768
import math
x = int(input())
ans = 0
mx = 0
for b in range(1, int(math.sqrt(x))+1) :
    if b == 1 :
        mx = 1
        continue
    p = 1
    while b ** p <= x :
        mx = max(b**p, mx)
        p += 1
print(mx)


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

typedef pair<long long, long long> P;
void solve(int n){
	vector<int> v;
	vector<P> w;
	for(int i=0; i<n; ++i){
		int a, b, h, m, s;
		scanf("%d:%d:%d", &h, &m, &s);
		a = 3600*h + 60*m + s;
		scanf("%d:%d:%d", &h, &m, &s);
		b = 3600*h + 60*m + s;
		w.push_back(P(a, b));
	}
	sort(w.begin(), w.end());
	for(int i=0; i<n; ++i){
		int a = w[i].first;
		int b = w[i].second;
		bool f = false;
		for(int j=0; j<v.size(); ++j)
			if(v[j] <= a){
				v[j] = b;
				f = true;
				break;
			}
		if(!f) v.push_back(b);
		sort(v.begin(), v.end());
	}
	cout << v.size() << "\n";
}

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	while(1){
		int n;
		cin >> n;
		if(n == 0) return 0;
		solve(n);
	}
}


Measured memory_bytes: 3408
def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist


n, k = [ int(v) for v in input().split() ]
num = [ int(v) for v in input().split() ]
num_2 = [ max(i,0) for i in num ] 


cum_num, cum_num_2 = [0] + cumsum(num), [0] + cumsum(num_2)

ans = 0
for i in range(n-k+1):
    ansl = cum_num_2[i]
    ansm = cum_num[k+i] - cum_num[i]
    ansr = cum_num_2[n] - cum_num_2[i+k]
    ans = max(ansl+max(ansm,0)+ansr, ans)
print(ans)

Measured memory_bytes: 79008
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
int pow5(int x)
{
	return x*x*x*x*x;
}
int main()
{
	int x;
	cin >> x;
 
	for (int a = 120; a >= 1 ; --a)
	{
		for (int b = a-1; b >= -120; --b)
		{
			if (x%(a-b)!=0)
			{
				continue;
			}
			if (pow5(a)-pow5(b) == x)
			{
				cout << a << " " << b;
				return 0;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 3632
import Foundation
//漸化式
//var fib = [Int](repeating: 0, count: 100)
//fib[0] = 1
//fib[1] = 1
//for i in 2 ..< 50 {
//    fib[i] = fib[i-1] + fib[i-2]
//    print(fib[i])
//}


let N = Int(readLine()!)!
let h_line = readLine()!.split(separator: " ").map({Int($0)!})

var dp = [Int](repeatElement(0, count: N))
var cost = 0
dp[0] = 0
dp[1] = abs(h_line[1] - h_line[0])
for i in 2 ..< h_line.count {
    dp[i] = min(abs(h_line[i] - h_line[i-1]) + dp[i-1], abs(h_line[i-2] - h_line[i]) + dp[i-2])
}
print(dp.last!)

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

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

using namespace std;

int main()
{
	int a[5] = {0,6000,4000,3000,2000};
	rep(i,4)
	{
		int t,n;
		cin >> t >> n;

		cout << a[t]*n << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
n,m,*t=map(int,open(0).read().split())
u=[-1]*(n+1)
def root(x):
  while u[x]>=0:x=u[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y:return
  if u[x]>u[y]:x,y=y,x
  u[x]+=u[y]
  u[y]=x
for x,y in zip(*[iter(t[n:])]*2):
  unite(x,y)
print(sum(root(i)==root(p)for i,p in enumerate(t[:n],1)))

Measured memory_bytes: 35324
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
int N, M, K, H, W, L, R;



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

	cin >> N;
	vector<long long int>v(N);
	for (auto &i : v)cin >> i;
	M = accumulate(v.begin(), v.end(), 0LL);
	int ans = 0;
	for (int i = 1; i < N; i++) {
		if (abs(v[i] * N - M) < abs(v[ans] * N - M))ans = i;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    for a in A:
        if a % 2 == 0:
            if a % 3 != 0 and a % 5 != 0:
                print("DENIED")
                break
    else:
        print("APPROVED")



if __name__ == '__main__':
    main()


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

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

    int a[5];
    int amari = 0;
    int ans_idx = 0;
    for (int i = 0; i < 5; i++)
    {
        cin >> a[i];
        if (10 - a[i] % 10 > amari && a[i] % 10 != 0)
        {
            amari = 10 - a[i] % 10;
            ans_idx = i;
        }
    }

    int ans = 0;
    for (int i = 0; i < 5; i++)
    {
        if (i == ans_idx)
        {
            continue;
        }
        ans += a[i];
        if (a[i] % 10 != 0)
        {
            ans += 10 - a[i] % 10;
        }
    }
    ans += a[ans_idx];

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>

int main(){
  int n;
  std::cin >> n;
  int* d = new int[n];
  int* h = new int[n]; 
  for(int i=0;i<n;i++){
    std::cin >> h[i];
    d[i] = INT_MAX;
  }
  
  d[0] = 0;
  d[1] = std::abs(h[1]-h[0]);
  for(int i=2;i<n;i++){
    d[i] = std::min(d[i], std::abs(h[i]-h[i-1])+d[i-1]);
    d[i] = std::min(d[i], std::abs(h[i]-h[i-2])+d[i-2]);
    
  }
  
  std::cout << d[n-1];
  
  delete h;
  delete d;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
// debug
#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl;
#define ddd(x, y, z) cerr << "(" #x "," #y "," #z "):(" << x << "," << y << "," << z << ")" << endl;
#define dump(v)              \
  cerr << #v ":[ ";          \
  for (auto macro_vi : v)    \
  {                          \
    cerr << macro_vi << " "; \
  }                          \
  cerr << "]" << endl;
#define ddump(v)                     \
  cerr << #v ":" << endl;            \
  for (auto macro_row : v)           \
  {                                  \
    cerr << "[";                     \
    for (auto macro__vi : macro_row) \
    {                                \
      cerr << macro__vi << " ";      \
    }                                \
    cerr << "]" << endl;             \
  }
#define damp(m)                                                   \
  for (auto macro_pair : m)                                       \
  {                                                               \
    cerr << macro_pair.first << ":" << macro_pair.second << endl; \
  }
#define dpair(p) cerr << #p ":" \
                      << "(" << p.first << "," << p.second << ")" << endl;
// iterate
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define itr(macro_v, i) macro_v.begin() + i
// etc
#define chmin(mi, val) mi = min(mi, val);
#define chmax(ma, val) ma = max(ma, val);
using ll = long long;

using namespace std;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x, y;
  cin >> x >> y;
  int score = 0;
  if (x == 3)
  {
    score += 100000;
  }
  else if (x == 2)
  {
    score += 200000;
  }
  else if (x == 1)
  {
    score += 300000;
  }
  if (y == 3)
  {
    score += 100000;
  }
  else if (y == 2)
  {
    score += 200000;
  }
  else if (y == 1)
  {
    score += 300000;
  }
  if (x == 1 and y == 1)
  {
    score += 400000;
  }
  cout << score << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 924844033

int N, K;
vector<int> G[4000];
int dp[2][2001][2];
int fact[2001];
int U[4000], R[4000];

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

void unite(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (R[x] < R[y]) swap(x, y);
  U[y] = x;
  R[x] += R[y];
  R[y] = 0;
}

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

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  fact[0] = 1;
  for (int i=1; i<=2000; i++) fact[i] = (1LL*fact[i-1]*i) % MOD;
  cin >> N >> K;
  rep(i, 2*N) U[i] = i, R[i] = 1;

  rep(i, N) {
    int a = i-K, b = i+K;
    if (a >= 0) unite(i, a+N);
    if (b < N)  unite(i, b+N);
  }

  dp[0][0][0] = 1;
  rep(_, 2*N) {
    int r = R[_];
    if (r == 0) continue;
    rep(i, r-1) {
      rep(j, N+1) {
        dp[1][j][0] += (dp[0][j][0] + dp[0][j][1]) % MOD;
        dp[1][j][0] %= MOD;
      }
      rep(j, N) {
        dp[1][j+1][1] += dp[0][j][0];
        dp[1][j+1][1] %= MOD;
      }
      rep(j, N+1) {
        rep(k, 2) {
          dp[0][j][k] = dp[1][j][k];
          dp[1][j][k] = 0;
        }
      }
    }
    rep(j, N+1) {
      dp[0][j][0] = (dp[0][j][0] + dp[0][j][1]) % MOD;
      dp[0][j][1] = 0;
    }
  }

  long long s = 0;
  rep(i, N+1) {
    int b = 1;
    if (i % 2 == 1) b = -1;
    s += (1LL*b*dp[0][i][0]*fact[N-i]) % MOD;
    s %= MOD;
    s += MOD;
    s %= MOD;
  }
  cout << s << "\n";
  return 0;
}


Measured memory_bytes: 384
const Main = input => {
    input = input.trim();
    input = input.split(" ").map(value => parseInt(value, 10));

    let result;
    for(let i = 0; i < input.length; i++) {
        if(input[i] !== i + 1) {
            result = i + 1;
            break;
        }
    }
    console.log(result);
}
 
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29632
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;

int main(){
    int N, A; cin >> N >> A;
    vector<int> X(N);
    rep(i,N) {
        cin >> X[i];
        X[i] -= A;
    }

    map<int, Int> M;
    rep(i,N){
        map<int,Int> tmp;
        for(auto p : M){
            tmp[p.first + X[i]] += p.second;
            tmp[p.first] += p.second;
        }
        tmp[X[i]]++;
        swap(tmp,M);
    }

    cout << M[0] << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <vector>
using namespace std;
#define INF 1000000007
#define ll long long
#define rep(i_, __start, __end) for(ll i_=(ll)__start; i_<(ll)__end; i_++)
#define print(_a) cout << _a << endl;
#define printarray(a, len) rep(ii,0,len) cout << a[ii] << " ";
#define printarray2(aa, len) rep(ij,0,len) printarray(aa[ij], aa[ij].size()); print("");


int main(){
    ll x;
    cin >> x;
    if(x == 3 || x == 5 || x == 7){
      print("YES");
    } 
    else print("NO");
   
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
#include <set>
#include <random>
using namespace std;

int main() {
  int N;
  cin >> N;
  for (int X = 0; X <= N; X++) {
	  if (X * 108 / 100 == N) {
		  cout << X << endl;
		  return 0;
		}
	}
  cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();

		if (N <= 1) {
			System.out.print(0);
			return;
		} else if (N == 2) {
			System.out.print(2);
			return;
		}

		BigInteger all = new BigInteger("10").pow(N);
		BigInteger dame1 = new BigInteger("8").pow(N);
		BigInteger dame2 = new BigInteger("9").pow(N).multiply(BigInteger.TWO);
		System.out.print(all.subtract(dame2).add(dame1).remainder(new BigInteger("1000000007")));
	}
}

Measured memory_bytes: 89752
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdlib>
#include <cmath>
#include<stdio.h>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define MAX 1000000000000000000LL
ll inf=100000000000007;
using namespace std;

int main(){
    long long  n,m;cin>>n>>m;
    ll key=n*2+m;
    ll ans=min(key/4,m/2);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
A = []
A.append([0, 0, 0])
for i in range(n):
    A.append([int(i) for i in input().split()])
ans = 'Yes'

for i in range(n):
    dist = abs(A[i][1] - A[i + 1][1]) + abs(A[i][2] - A[i + 1][2])
    if (A[i + 1][0] - A[i][0])  < dist:
        ans = 'No'
        break
    if ((A[i + 1][0] - A[i][0]) - dist) % 2 == 1:
        ans = 'No'
        break
    
print(ans)

Measured memory_bytes: 21156
#include<iostream>
#include<vector>
using namespace std;
class union_find{
private:
    vector<int>parent;
    vector<int>rank;
    int cnt;
public:
    union_find(int vertex_num)
    {
        parent.resize(vertex_num);
        rank.resize(vertex_num);
        for(int i = 0; i < vertex_num; ++i){
            parent[i] = i;
            rank[i] = 0;
        }
        cnt = vertex_num;
    }
    int get_root(int n)
    {
        if(parent[n] == n){
            return n;
        }else{
            return get_root(parent[n]);
        }
    }
    bool is_same(int a, int b)
    {
        return get_root(a) == get_root(b);
    }
    void unite(int a, int b)
    {
        int root_a=get_root(a),root_b=get_root(b);
        if(root_a == root_b)return;
        if(rank[root_a] < rank[root_b]){
            parent[root_a] = root_b;
            --cnt;
        }else if(rank[root_a] > rank[root_b]){
            parent[root_b] = root_a;
            --cnt;
        }else{
            parent[root_a] = get_root(root_b);
            ++rank[root_b];
            --cnt;
        }
    }
    bool is_all_connected()
    {
        return cnt == 1;
    }
};
int main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>>ab(m);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        ab[i] = make_pair(a, b);
    }

    int ans = 0;
    for(int i = 0; i < m; ++i){
        union_find uf(n);
        for(int j = 0; j < m; ++j){
            if(i == j)continue;
            uf.unite(ab[j].first, ab[j].second);
        }
        if(!uf.is_all_connected()){
            ++ans;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define true 0
#define false 1

int isPrime(int);
int main(){
  int n, i, number=0;
  int integer[10000];

  scanf("%d", &n);
  if(n < 1 || 10000 < n)
    exit(1);

  for(i = 0; i < n; i++){
    scanf("%d", &integer[i]);
    if(integer[i] < 2 || pow(10, 8) < integer[i])
      exit(2);
    if(isPrime(integer[i]) == true)
      number++;
  }

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

  return 0;
}

int isPrime(int x){
  int i=3;

  if(x == 2)
    return true;
  else if(x < 2 || x % 2 == 0)
    return false;

  while(i <= sqrt(x)){
    if(x % i == 0)
      return false;
    i += 2;
  }

  return true;
}

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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

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

const int MAX_N = 5e3 + 5;
const int MAX_M = 200 + 5;
const ll INF = 1LL << 60;
ll mat[MAX_M][MAX_N], dis[MAX_N], dis_pref[MAX_N], data[MAX_N];
vector<pair<ll, int>> stac[MAX_M];
int nxt[MAX_M][MAX_N];
int n, m;

inline ll dis_traveled(int l, int r) {
	r--;
	if(l > r) {
		return 0;
	}
	return dis_pref[r] - dis_pref[l - 1];
}

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

	fori(i, 1, n) {
		scanf("%lld", dis + i);
		dis_pref[i] = dis_pref[i - 1] + dis[i];
	}

	fori(i, 1, n + 1) {
		fori(j, 1, m + 1) {
			scanf("%lld", &mat[j][i]);
		}
	}

	fori(i, 1, m + 1) {
		stac[i].emplace_back(INF, n + 1);
	}

	ll ans = -INF;
	ford(i, n, 1) {
		fori(j, 1, m + 1) {
			while(stac[j].back().first <= mat[j][i]) {
				pair<ll, int> top = stac[j].back();
				stac[j].pop_back();
				data[top.second] -= top.first;
				data[stac[j].back().second] += top.first;
			}
			
			data[i] += mat[j][i];
			data[stac[j].back().second] -= mat[j][i];
			stac[j].emplace_back(mat[j][i], i);
		}
		
		ll gain = 0;
		fori(j, i, n + 1) {
			gain += data[j];
			ans = max(ans, gain - dis_traveled(i, j));
		}
	}

	// 1 2
	// 5 3
	// 2 3
	// 2 1

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

	return 0;
}


Measured memory_bytes: 10368
#include <stdio.h>

int main(void){
    int r0,w0,c,r,water,i;
    for(;scanf("%d %d %d %d",&r0,&w0,&c,&r),r;){
        for(i=0;;i++){
            water=(r0+i*r)/c;
            if(water >= w0)
                break;
        }
        printf("%d\n",i);
    }
    return 0;
}

Measured memory_bytes: 600
import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    # エラトステネスの篩で、
    # 2 から 10^5までの素数を列挙
    limit = 10 ** 5 + 1
    prime = [False if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 else True for n in range(limit)]
    prime[0] = prime[1] = False
    prime[2] = prime[3] = prime[5] = True
    for p in range(3, limit, 2):
        if math.sqrt(limit) < p:
            break
        for q in range(p ** 2, limit, p):
            prime[q] = False

    # 累積和
    # 2017に似た数字の数を求めておく
    cnt = [0]*limit
    for n in range(len(cnt)):
        if prime[n] and prime[(n+1)//2]:
            cnt[n] = 1
    for n in range(1, len(cnt)):
        cnt[n] += cnt[n-1]

    # 回答
    Q = ii()
    for q in range(Q):
        l, r = il()
        print(cnt[r]-cnt[l-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 10048
#include <bits/stdc++.h>
#define Speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

#define st              first
#define nd              second
#define pb              push_back
#define pf              push_front
#define all(a)          (a).begin(), (a).end()
#define lwb             lower_bound
#define upb             upper_bound
#define vvll            vector<vector<ll> >
#define Mset(s, n)      memset(s, n, sizeof(s))
#define Sz(a)           int((a).size())
#define Max(a, b, c)    max(max((ll)(a), (ll)(b)), (ll)(c))
#define Min(a, b, c)    min(min((ll)(a), (ll)(b)), (ll)(c))
#define Unique(a)       sort(all(a)); (a).resize(unique(all(a)) - (a).begin())

typedef long double ld;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1e9 + 7;
const int oo = 2e9;
const ld PI = acos((ld) -1);
int Getbit(ll x, int k){return (x >> (k - 1)) & 1;}
ll Lcm(ll a, ll b) {return a / __gcd(a, b) * b;}
bool isPrime(ll n){for(ll i = 2; i * i <= n; i++){if(n % i == 0) return 0;} return (n > 1) ? 1 : 0;}
ll Powmod(ll n, ll k, ll p = MOD) {ll r = 1; for(; k; k /= 2, n = n * n % p){if(k & 1) r = r * n % p;} return r;}

const int N = 2e5 + 5;

ll n, m, k;
ll a[N], f[N];

void Solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    f[2] = abs(a[2] - a[1]);
    for(int i = 3; i <= n; i++){
        f[i] = min(f[i - 1] + abs(a[i - 1] - a[i]),
                    f[i - 2] + abs(a[i - 2] - a[i]));
    }
    cout << f[n];
}

int main(){
    Speed;
    int query = 1;
//    cin >> query;
    while(query--) Solve();
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

constexpr double EPS = 1.0e-12;

double dist(const pair<double, double>& p1, const pair<double, double>& p2) {
    auto dx = p1.first - p2.first;
    auto dy = p1.second - p2.second;
    return sqrt(dx * dx + dy * dy);
}

bool check(const vector<pair<double, double>>& p, const pair<double, double>& c,
           double r) {
    for (const auto& pp : p) {
        if (dist(pp, c) >= r + EPS) {
            return false;
        }
    }

    return true;
}

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

    vector<pair<double, double>> p(n);
    for (auto&& pp : p) {
        cin >> pp.first >> pp.second;
    }

    double ans = numeric_limits<double>::max();
    for (auto i : irange(0L, n)) {
        for (auto j : irange(i + 1, n)) {
            pair<double, double> c;
            c.first = (p[i].first + p[j].first) / 2.0;
            c.second = (p[i].second + p[j].second) / 2.0;
            double r = dist(p[i], p[j]) / 2.0;

            if (check(p, c, r)) {
                ans = min(ans, r);
            }

            for (auto k : irange(j + 1, n)) {
                if (p[i].first == p[j].first && p[j].first == p[k].first) {
                    continue;
                }

                if (p[i].second == p[j].second && p[j].second == p[k].second) {
                    continue;
                }

                auto abcd = p[i].first * p[i].first +
                            p[i].second * p[i].second -
                            p[j].first * p[j].first - p[j].second * p[j].second;
                auto abef = p[i].first * p[i].first +
                            p[i].second * p[i].second -
                            p[k].first * p[k].first - p[k].second * p[k].second;

                pair<double, double> c;
                c.second = ((p[k].first - p[i].first) * abcd -
                            (p[j].first - p[i].first) * abef) /
                           (2 * (p[k].first - p[i].first) *
                                    (p[i].second - p[j].second) -
                            2 * (p[j].first - p[i].first) *
                                    (p[i].second - p[k].second));

                c.first = (p[i].first != p[j].first
                                   ? ((2 * (p[i].second - p[j].second) *
                                               c.second -
                                       abcd) /
                                      (2 * (p[j].first - p[i].first)))
                                   : ((2 * (p[i].second - p[k].second) *
                                               c.second -
                                       abef) /
                                      (2 * (p[k].first - p[i].first))));

                double r = dist(p[i], c);

                if (check(p, c, r)) {
                    ans = min(ans, r);
                }
            }
        }
    }

    cout << setprecision(10) << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,R,G,B; 
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>R>>G>>B>>n;
	long long res=0;
	for(int r=0;r*R<=n;r++){
		for(int g=0;r*R+g*G<=n;g++){
			int b=n-r*R-g*G;
			if(b==0||b%B==0)
				res++;
		}
	}
	cout<<res<<endl;
	return 0;
}


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

using namespace std;

int main(){
    int a,b,c,cont=0;
    cin >> a >> b >> c;
    for(int i=a;i<=b;i++){
        if(c%i==0){
            cont++;
        }
    }
    cout << cont << endl;
    return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int (x); SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long (x); SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x,y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1000000007;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////

/*（๑•﹏•๑｀) */

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

    char target = S[K-1];
    REP(i,N){
        if (S[i] != target) S[i] = '*';
    }

    cout << S << endl;
}


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

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

int solve(int cur, const vector<vector<int>>& g, const vector<bool>& vec) {
	vector<bool> visited = vec;
	bool complete = [=]() -> bool {
		for (auto x : visited) {
			if (!x) {
				return false;
			}
		}
		return true;
	}();

	if (complete) {
		return 1;
	}

	int res = 0;
	for (auto next : g[cur]) {
		if (visited[next]) {
			continue;
		}

		visited[next] = true;
		res += solve(next, g, visited);
		visited[next] = false;
	}

	return res;
}

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

	int n, m;
	cin >> n >> m;

	vector<vector<int>> g(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;

		g[a].push_back(b);
		g[b].push_back(a);
	}

	vector<bool> visited(n);
	visited[0] = true;

	cout << solve(0, g, visited) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int MOD = 1000000007;
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
void initComb() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long comb(int n, int r) {
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

int main(){
  initComb();
  ll N, M, K;
  cin >> N >> M >> K;
  int sum = 0;
  rep(i, N)
    sum = (sum+i*(N-i)*M%MOD*M%MOD)%MOD; //2点間の縦方向の距離がiになる組合せの和(他の点は無視)
  rep(i, M)
    sum = (sum+i*(M-i)*N%MOD*N%MOD)%MOD; //2点間の横方向の距離がiになる組合せの和(他の点は無視)
  ll ans = sum*comb(N*M-2, K-2); //2点を固定する組合せは、他の点のパターン分存在する
  ans %= MOD;
  cout << ans << endl;
}

Measured memory_bytes: 12160
#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int main(void) {
    int N, M, X;
    int CA[12][13];
    int min = 2147483647; // 最小価格

    scanf("%d %d %d", &N, &M, &X);
    for(int i = 0; i < N; i++) {
        scanf("%d", &CA[i][0]);
        for(int j = 1; j <= M; j++) {
            scanf("%d", &CA[i][j]);
        }
    }

    for(int i = 1; i <= pow(2, N); i++) {
        int S = 0;          // 合計価格
        int A[12] = {0};    // 理解度
        int OK = true;
        
        for(int j = 0; j < N; j++) {
            if((i & (int)pow(2,j)) != 0) {
                S += CA[j][0];
                for(int k = 1; k <= M; k++) {
                    A[k-1] += CA[j][k];
                }
            }
        }

        for(int k = 0; k < M; k++) {
            if(A[k] < X) {
                OK = false;
            }
        }

        if(OK == false) {
            continue;
        }

        if(min > S) {
            min = S;
        }
    }

    if(min == 2147483647) {
        printf("-1\n");
    }
    else {
        printf("%d\n", min);
    }

    return 0;
}


Measured memory_bytes: 2476
using System;

class A{
  public static void Main(){
    int[] Ar = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
    int minus = Ar[0] * 60 + Ar[1];
    int plus = Ar[2] * 60 + Ar[3];
    Console.WriteLine(plus - minus - Ar[4]);
  }
}

Measured memory_bytes: 27544
#include <cstdio>
char str[100005];
void put(int a, int b){
	printf("%d %d\n", a, b);
}
void solve(){
	for(int i = 0; str[i]; i ++){
		if(str[i+1] && str[i] == str[i+1]) return put(i+1, i+2);
		if(str[i+2] && str[i] == str[i+2]) return put(i+1, i+3);	
	}
	return put(-1, -1);
}
int main(){
	scanf("%s", str);
	solve();
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

one = 0
two = 0
four = 0

for i in a:
    if i % 4 == 0:
        four += 1
    elif i % 2 == 0:
        two += 1
    else:
        one += 1

print("Yes" if four >= one or (four == one - 1 and two == 0) else "No")


Measured memory_bytes: 14224
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long 
const int maxn=200010;
int n;
ll a[maxn],ans;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    for (int i=2;i<=n;++i){
        if (a[i]<a[i-1]){
            ans+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    printf("%lld",ans);
}

Measured memory_bytes: 5368
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()





int main() {
    int n;
    cin >> n;
    map<string, int> cnt;
    vector<string> a(n);
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sort(all(a[i]));
        cnt[a[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        ans += cnt[a[i]] - 1;
        cnt[a[i]]--;
    } 
    cout << ans << endl;
    return 0;
}





Measured memory_bytes: 18176
#200419C
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)

count = 0
for i in range(N-1):
    L = len(A)
    #print(A)
    Ans = 0
    count += Ans
    for j in range(L-count):
        if A[count + j]==i+1:
            Ans += 1
        else:            
            break
    print(Ans)
    count += Ans

        
print("0")

Measured memory_bytes: 32380