akhauriyash/Code-Regression huggingface dataset:
#define taskname "test"

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
int L;

struct graph
{
    struct Edge
    {
        int u, v, w;
    };

    int n, cur;
    vector<Edge> edges;

    void init()
    {
        n = 1; cur = 1;
        edges.clear();
    }

    void add_one()
    {
        edges.push_back({1, n, cur});
        ++cur;
    }

    void double_one()
    {
        cur *= 2;
        for(auto&e: edges)
            e.w *= 2;
        ++n;
        edges.push_back({n - 1, n, 0});
        edges.push_back({n - 1, n, 1});
    }

    void print()
    {
        cout << n << ' ' << edges.size() << '\n';
        for(auto&e: edges)
            cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
    }
} G;

void read_input()
{
    cin >> L;
}

void solve()
{
    vector<int> v;
    while(L > 1)
    {
        if(L & 1)
        {
            --L;
            v.push_back(0);
        }
        else
        {
            L /= 2;
            v.push_back(1);
        }
    }
    reverse(v.begin(), v.end());
    G.init();
    for(auto&to: v)
    {
        if(to) G.double_one();
        else G.add_one();
    }
    G.print();
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll money = 1000;

    rep(i, N - 1) {
        repd(j, i + 1, N) {
            if (A[i] < A[j]) {
                ll sell = money / A[i];
                money -= sell * A[i];
                money += sell * A[j];
                i = j - 1;
                break;
            }
            else break;
        }
    }

    cout << money << endl;
    return 0;
}

Measured memory_bytes: 3648
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N=Integer.parseInt(sc.next());
		int K=Integer.parseInt(sc.next());
		System.out.println((int)Math.ceil((double)(N-K)/(K-1))+1);
	}
}
	


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



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

int lo = S.size();
if(lo <= N) cout << S << endl;
else {
    S.erase(N);
    cout << S  << "..."<<endl;

}



}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
const long long md=998244353;
const long long INV2=(md+1)/2;
const int maxn=10010;
long long fac[maxn],inv[maxn];
long long powd(long long x,long long y){
	long long res=1;
	while(y){
		if(y&1) res=res*x%md;
		x=x*x%md;
		y>>=1;
	}
	return res;
}
long long dp[maxn];
int num1,num2;
int k,n;
void add1(){
	for(int i=k;i>=1;i--)
		dp[i]=(dp[i-1]+dp[i])%md;
}
void add2(){
	for(int i=k;i>=1;i--)
		dp[i]=(dp[i-1]*2+dp[i])%md;
}
void div1(){
	static long long f[maxn];
	for(int i=0;i<=k;i++)
		f[i]=0;
	for(int i=k;i>=1;i--){
		f[i-1]=dp[i];
		dp[i-1]=(dp[i-1]-dp[i]+md)%md;
	}
	for(int i=0;i<=k;i++)
		dp[i]=f[i];
}
void div2(){
	static long long f[maxn];
	for(int i=0;i<=k;i++)
		f[i]=0;
	for(int i=k;i>=1;i--){
		f[i-1]=dp[i]*INV2%md;
		dp[i-1]=(dp[i-1]-dp[i]*INV2%md+md)%md;
	}
	for(int i=0;i<=k;i++)
		dp[i]=f[i];
}
long long C(int x,int y){
	if(x<0||y<0||x-y<0) return 0;
	return fac[x]*inv[y]%md*inv[x-y]%md;
}
void solve(int x){
	int cnt1=0,cnt2;
	for(int i=1;i<=k;i++){
		if(i*2==x) continue;
		if(x-i>=1&&x-i<=k) cnt1++;
	}
	if(x%2==0) cnt2=k-cnt1-1;
	else cnt2=k-cnt1;
	cnt1/=2;
	while(num1>cnt1){
		num1--;
		div2();
	}
	while(num1<cnt1){
		num1++;
		add2();
	}
	while(num2>cnt2){
		num2--;
		div1();
	}
	while(num2<cnt2){
		num2++;
		add1();
	}
//	if(x==2*k) cerr<<dp[1]<<" "<<dp[2]<<endl;
	long long sum=0;
	for(int i=1;i<=k;i++)
		sum=(sum+C(n-1,i-1)*dp[i])%md;
	if(x%2==0){
		for(int i=1;i<=k;i++)
			sum=(sum+C(n-2,i-1)*dp[i])%md;
	}
	printf("%lld\n",sum);
}
int main(){
	fac[0]=1;
	for(int i=1;i<=maxn-1;i++)
		fac[i]=fac[i-1]*i%md;
	inv[maxn-1]=powd(fac[maxn-1],md-2);
	for(int i=maxn-1;i>=1;i--)
		inv[i-1]=inv[i]*i%md;
	scanf("%d%d",&k,&n);
	dp[0]=1;
	for(int i=2;i<=k*2;i++)
		solve(i);
	return 0;
}

Measured memory_bytes: 512
// by adiforluls
#pragma GCC optimize ("-O2")
#include<bits/stdc++.h>
using namespace std;
#define FASTNIBBA   ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define mii         map<int,int>
#define vi          vector<int>
#define vll         vector<long long>
#define lbnd        lower_bound
#define ubnd        upper_bound
#define all(a)      (a).begin(),(a).end()
#define clz(a)      __builtin_clz(a) // count leading zeroes
#define ctz(a)      __builtin_ctz(a) // count trailing zeroes
#define popc(a)     __builtin_popcount(a) // count set bits (for ints only diff for ll)
#define lul         1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define SIZE        1000005
#define F           first
#define S           second
#define debug(x)    cerr << #x << " = " << x << endl;
#define mod         998244353
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " = " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " = " << arg1<<" |";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
#define endl        '\n'
ll dp[100005][105];
void solve()
{
    int n,m; cin>>n>>m;
    int a[m];
    rep(i,0,m) cin>>a[i];
    sort(a,a+m);
    int diff[m-1];
    rep(i,1,m) diff[i-1]=a[i]-a[i-1];
    sort(diff,diff+m-1);
    ll ans=0;
    rep(i,0,max(0,m-n)) ans+=diff[i];
    cout<<ans;   
}
int main()
{
    FASTNIBBA;
   //  #ifndef ONLINE_JUDGE
     // freopen("input.txt", "r", stdin);
     // freopen("output.txt", "w", stdout);
   //  #endif
    int t; t=1;
    while(t--){
       solve();
    }
    return 0;
}

Measured memory_bytes: 1024
from collections import defaultdict
N = int(input())

d = defaultdict(int)
A = list(map(int, input().split()))
Q = int(input())

ans = sum(A)
for a in A:
    d[a] += 1

for i in range(Q):
    b, c = map(int,input().split())
    tmp = d[b] #変動する個数を数える
    d[b] = 0
    d[c] += tmp
    ans += (c-b)*tmp 
    print(ans)

Measured memory_bytes: 24116
#include <bits/stdc++.h>
#define pll pair<ll,ll>
const int mod = 1e9 + 7;
using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int n,H[100101],dp[101010],k;
int main(){
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1;i<=n;i++)cin>>H[i];
    for(int i = n-1;i>=1;i--){
        dp[i] = 1e9+7;
        for(int j = 1;j<=k&&j+i<=n;j++)
            dp[i] = min(dp[i],dp[i+j]+abs(H[i]-H[i+j]));
    }
    cout << dp[1] << endl;
    return 0;
}


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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    boolean flg = true;
    String s = in.readLine();
    for(int i=0; i<a+b+1; i++) {
      if(s.charAt(i)=='-' && i!=a)
        flg = false;
      if(s.charAt(i)!='-' && i==a)
        flg = false;
    }
    System.out.println(flg==true?"Yes":"No");
  }
}

Measured memory_bytes: 32844
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define lower(a,x) lower_bound(all(a), x) - a.begin();
#define COUNT(a,x)  upper_bound(all(a), x) - lower_bound(all(a), x);
#define MCOUNT(a,x,y) upper_bound(all(a), y) - lower_bound(all(a), x);
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end());
#define scan(x) scanf("%lld",&x);
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
typedef double D;
const ll inf = 5555555555555555555;
const ll mod = 1000000007;
const D pi = acos(-1);
const D eps = 1e-10;

ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok, flag;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111

ll digit_sum(ll x) {
  ll ret = 0;
  string y = to_string(x);
  rep(i, y.length()) ret += y[i] - '0';
  return ret;
}
string ss[18];
double mm[MAX*2];
int main(void) {
  ll k;
  vll a;
  cin >> k;

  FOR(i, 1, 16) ss[i] = ss[i - 1] + "9";
  FOR(i, 1, 10000) {
	string s1 = to_string(i);
	FOR(j, 1, 16) {
	  string s2 = s1 + ss[j];
	  if (s2.length() > 15)continue;
	  tmp = stoll(s2);
	  a.pb(tmp);
	}
  }
  FOR(i, 1, 10) a.pb(i);

  sort(all(a));
  UNIQUE(a);
  m = a.size();
  mm[m] = inf;
  rrep(i, m) mm[i] = min(mm[i + 1], (double)a[i] / digit_sum(a[i]));
  while (k) {
	if ((double)a[cnt] / digit_sum(a[cnt]) <= mm[cnt + 1]) {
	  cout << a[cnt] << endl;
	  k--;
	}
	cnt++;
  }

  return 0;
}

Measured memory_bytes: 2036
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
using namespace std;

int main()
{
	int A, B;
	cin >> A >> B;
	if (B % A == 0) {
		cout << A + B << endl;
	}
	else {
		cout << B - A << endl;
	}
	
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int n,m,i,j,k,a[N],l[N],r[N],ans;
int main(){
	scanf("%d%d",&n,&k);for (i=1;i<=n;i++) scanf("%d",&a[i]);j=n+1;for (i=1;i<=n;i++) if (a[i]>0){j=i;break;}
	for (i=j-1;i>=1;i--) l[j-i]=-a[i];for (i=j;i<=n;i++) r[i-j+1]=a[i];ans=2000000000;
	for (i=0;i<=k;i++){if (j-1<i||k-i>n-j+1) continue;ans=min(ans,l[i]+r[k-i]+min(l[i],r[k-i]));}printf("%d\n",ans);return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int Det(int S[6],int T[6])
{
	int i,j,k,d,C[6];
	int Dice[6][6]={{1,2,3,5,4,6},
					{2,6,3,1,4,5},
					{3,6,5,1,2,4},
					{4,6,2,1,5,3},
					{5,6,4,1,3,2},
					{6,5,3,2,4,1}};
	for(i=0;i<6;i++)
	{
		for(j=0;j<4;j++)
		{
			for(k=0;k<4;k++){C[k+1]=T[Dice[i][(j+k)%4+1]-1];}
			C[0]=T[Dice[i][0]-1];C[5]=T[Dice[i][5]-1];
			for(d=0,k=0;k<6;k++)
			{
				if(S[Dice[0][k]-1]==C[k])d+=1;
			}
			if(d==6)break;
		}
		if(d==6)break;
	}
	if(d==6){return 1;}
	else{return 0;}
}
int main(void)
{
	int n,i,j,k,c=0,D[101][6],s[6],t[6];
	scanf("%d",&n);
	for(i=0;i<6;i++){scanf("%d",&D[0][i]);}
	for(i=1;i<n;i++){for(j=0;j<6;j++){scanf("%d",&D[i][j]);}}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			for(k=0;k<6;k++){s[k]=D[i][k];}
			for(k=0;k<6;k++){t[k]=D[j][k];}
			c+=Det(s,t);
		}
	}
	if(c==0){printf("Yes\n");}
	else{printf("No\n");}
	return 0;
}

Measured memory_bytes: 584
import java.util.Scanner;

//Alien Messages
public class Main{

	int w, h, C, si, sj, SD, ED;
	int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
	int[] D = {5, 10, 3, 9, 12, 6};
	int[][] p = {{0,2},{1,3},{0,1},{0,3},{2,3},{1,2}};
	int[][] nx = {{0, 5, 4},{3, 1, 4},{2, 0, 3},{2, 5, 1}};
	int[][] map;
	
	boolean check(int pi, int pj){
		for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(map[i][j]==0){
			int c = 0;
			for(int k=0;k<4;k++){
				int ni = i+d[k][0], nj = j+d[k][1];
				if(0<=ni&&ni<h&&0<=nj&&nj<w&&map[ni][nj]==0)c++;
			}
			if(i==pi&&j==pj)c++;
			if(i==si+d[ED][0]&&j==sj+d[ED][1])c++;
			if(c<2)return false;
		}
		return true;
	}
	
	boolean f(int i, int j, int c, int pd){
		if(!check(i, j))return false;
		if(si+d[ED][0]==i&&sj+d[ED][1]==j&&c<C)return false;
		for(int k=0;k<3;k++){
			map[i][j] = D[nx[pd][k]];
			boolean ok = true;
			int ND = -1;
			for(int x=0;x<2;x++){
				int dir = p[nx[pd][k]][x];
				int ni = i+d[dir][0], nj = j+d[dir][1];
				if(!(0<=ni&&ni<h&&0<=nj&&nj<w&&map[ni][nj]!=-1)){
					ok = false; break;
				}
				if(map[ni][nj]==0){
					ND = dir;
				}
				else {
					int r = (dir+2)%4;
					if(((map[ni][nj]>>r)&1)==0){
						ok = false;
					}
				}
			}
			if(!ok)continue;
			if(ND==-1){
				if(c==C)return true;
			}
			else if(f(i+d[ND][0], j+d[ND][1], c+1, ND))return true;
		}
		map[i][j] = 0;
		return false;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			w = sc.nextInt(); h = sc.nextInt();
			if((w|h)==0)break;
			C = 0;
			map = new int[h][w];
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				map[i][j]=sc.nextInt()==0?0:-1;
				C+=map[i][j]==0?1:0;
			}
			boolean res = false, con = true;
			for(int i=0;i<h&&con;i++)for(int j=0;j<w&&con;j++)if(map[i][j]==0){
				con = false;
				for(int k=0;k<6;k++){
					boolean ok = true;
					for(int x=0;x<2;x++){
						int ni = i+d[p[k][x]][0], nj = j+d[p[k][x]][1];
						if(!(0<=ni&&ni<h&&0<=nj&&nj<w&&map[ni][nj]==0)){
							ok = false;
						}
					}
					if(!ok)continue;
					map[i][j] = D[k];
					si = i; sj = j; SD = p[k][0]; ED = p[k][1];
					if(f(i+d[p[k][0]][0], j+d[p[k][0]][1], 2, SD)){
						res = true; break;
					}
				}
			}
			System.out.println(res?"Yes":"No");
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
typedef long long ll;
const int N = 100010;

int p[N];

int main()
{
	int n;
	scanf("%d", &n);
	
	ll sum = 0;
	for(int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		sum += x;
		p[x]++;
	}
	
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int b, c;
		scanf("%d%d", &b, &c);
		sum -= (ll)b * p[b];
		sum += (ll)c * p[b];
		p[c] += p[b];
		p[b] = 0;
		printf("%lld\n", sum);
	}
	
	return 0;
}

Measured memory_bytes: 4196
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  string S; cin >> S;
  int n=S.size();
  int ans = INF;
  // wbwbwb..
  int num = 0;
  rep(i, n) {
    if (S[i] == '1' && i&1) num++;
    if (S[i] == '0' && !(i&1)) num++;
  }
  chmin(ans,num);
  // bwbwbwb
  num = 0;
  rep(i,n) {
    if (S[i] == '0' && i&1) num++;
    if (S[i] == '1' && !(i&1)) num++;
  }
  chmin(ans, num);
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  string s;
  cin >> s;
  
  if(s[2]==s[3] && s[4]==s[5]) printf("Yes");
  else printf("No");
  
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int cmp(const int *a, const int *b){
  return *a - *b;
}
int main(){
  int n;
  scanf("%d",&n);
  int l[n];
  for(int i=0;i<n;i++)scanf("%d",&l[i]);
  qsort(l,n,4,cmp);
  int ans=0;
  for(int i=0;i<n-2;i++){
    for(int j=i+1;j<n-1;j++){
      int k=n-1;
      for(;l[i]+l[j]<=l[k];k--);
      ans+=k-j;
    }
  }
  printf("%d",ans);
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 2005;
const int MOD = 1e9 + 7;

int add(int a, int b) {
	return (a + b) % MOD;
}

int mul(int a, int b) {
	return (a * b) % MOD;
}

int binpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int divv(int a, int b) {
	return mul(a, binpow(b, MOD - 2));
}

int f[N];

void init() {
	f[0] = 1;
	for (int i = 1; i < N; i++) {
		f[i] = mul(f[i - 1], i);
	}
}

int C(int n, int k) {
	// cerr << n << ' ' << k << endl;
	return divv(f[n], mul(f[k], f[n - k]));
}

int sp(int n, int k) {
	//n over k
	return C(n + k - 1, k - 1);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	init();
	int n, k;
	cin >> n >> k;
	int red = n - k;
	vector<int> ans(k + 1);
	for (int i = 1; i <= k; i++) {
		if (i > red + 1) {
			ans[i] = 0;
		} else {
			int cnt1 = C(red + 1, i);
			int cnt2 = sp(k - i, i);
			// cerr << cnt1 << ' ' << cnt2 << endl;
			ans[i] = mul(cnt1, cnt2);
		}
		cout << ans[i] << '\n';
	}
}


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

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORB(i, m, n) for (int i = m; i >= n; i--)
#define ll long long
#define pb push_back
#define popb pop_back
#define debug(i) cout << #i << "= " << i << endl
using namespace std;
ll k;
ll dp[1000005];
void making(ll a, ll b)
{
    ll ans = 7;
    dp[0] = 7;
    for (ll i = 1; i <= b; i++)
    {
        ans *= a;
        ans %= k;
        dp[i] = ans;
    }
}
int main()
{

    cin >> k;
    int ans = -1;
    ll mod = 7;
    mod %= k;
    making(10, 1000001);

    for (ll i = 1; i < 1e6 + 1; i++)
    {
        if (mod % k == 0)
        {
            cout << i << endl;
            return 0;
        }

        mod += dp[i];
        mod %= k;
    }

    cout << ans << endl;
}


Measured memory_bytes: 11444
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
int main(void){
	vector<int>a;
	vector<int>b;
	int d;
	int k;
	int n, m;
	int s, t;
	int x, y, z;

	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &x);
		a.push_back(x);
	}
	scanf("%d", &m);
	for (int i = 0; i < m; i++){
		scanf("%d", &x);
		b.push_back(x);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	s = 0;
	t = 0;
	for (; s < n&&t < m;){
		if (a[s] == b[t]){
			s++;
			t++;
		}
		else s++;
	}
	if(t==m)printf("YES\n");
	else printf("NO\n");

	return 0;
}


Measured memory_bytes: 2548
#not accept

from sys import stdin
from collections import defaultdict

N, X = [int(x) for x in stdin.readline().rstrip().split()]
L = []
L = [int(x) for x in stdin.readline().rstrip().split()]

D = [0]
for i in range(1,N+1):
    D.append(D[i-1] + L[i-1])

max = 0
for i in range(1,N+1):
    if D[i] <= X:
      max = i
    else:
      break

print(max+1)

Measured memory_bytes: 3316
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

bool isPrime(int n) {//???????卒???属 
	if (n == 1) return false;
	int q = (int)sqrt(n);
	for (int i=2; i<=q; ++i) {
		if (n % i == 0) return false;
	}
	return true;
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		int num;
		int cnt = 0;
		while (n--) {
			scanf ("%d", &num);
			if (isPrime(num)) ++cnt;
		}
		printf ("%d\n", cnt);
	}
	return 0;
}

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

void nabeatsu(int n) {
  for (int i=1; i<=n; i++) {
    if (i%3 == 0) {
      cout << " " << i;
      continue;
    }
    if (i%10 == 3) {
      cout << " " << i;
      continue;
    }
    string x = to_string(i);
    x += "aaaa";
    for (int j=0; j<5; j++) {
      if (x.at(j) == '3') { 
        cout << " " << i;
        break;
      }
    }
  }
  cout << endl;
  return;
}

int main() {
  int n;
  cin >> n;
  nabeatsu(n);
  
  return 0;
}


Measured memory_bytes: 3232
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
//Combination
long long extGCD(long long a,long long mod,long long &x,long long &y){
    if(mod==0){
        x=1;
        y=0;
        return a;
    }
    long long d=extGCD(mod,a%mod,y,x);
    y-=(a/mod)*x;
    return d;
}
long long invmod(long long a,long long mod){
    long long x,y;
    extGCD(a,mod,x,y);
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
ll fac[2000010],finv[2000010],inv[2000010];
void combinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    REP(i,2,2000010){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=invmod(i,mod);
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll comb(ll n,ll k){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
ll rui(ll a,ll b){
    ll res=1;
    ll x=a;
    while(b){
        if(b&1)res=res*x%inf;
        x=x*x%inf;
        b/=2;
    }
    return res;
}
signed main(){
    ll n,a,b,c,d;cin>>n>>a>>b>>c>>d;
    ll m=b-a+1;
    vector<vector<ll> > dp(m+1,vector<ll>(n+1));
    combinit();
    vector<ll>kai(1010);
    kai[0]=1;
    REP(i,1,1010){
        kai[i]=kai[i-1]*i%inf;
    }
    dp[0][0]=1;
    rep(i,m){
        ll x=a+i;
        rep(j,n+1){
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%inf;
            ll now=dp[i][j];
            REP(k,1,d+1){
                if(k*x+j>n)break;
                now=now*comb(n-j-(k-1)*x,x)%inf;
                if(k>=c)dp[i+1][j+k*x]=(dp[i+1][j+k*x]+now*rui(kai[k],inf-2)%inf)%inf;
            }
            //cout<<dp[i][j]<<' ';
        }
        //cout<<endl;
    }
    rep(i,n+1){
        //cout<<dp[m][i]<<' ';
    }
    //cout<<endl;
    ll ans=dp[m][n];
    if(ans<0)ans+=inf;
    cout<<ans<<endl;
}

Measured memory_bytes: 57712
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using tl = tuple<ll, ll, ll>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n; cin>>n;
    ll ans = 0;
    for (ll i = 2; i * i <= n; ++i) {
        ll cnt = 0;
        ll c = 0;
        while (n % i == 0) {
            c++;
            if (cnt < c) {
                cnt++;
                c -= cnt;
            }
            n /= i;
        }
        ans += cnt;
    }
    if (n > 1) ans++;
    cout<<ans<<endl;
}

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

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

typedef pair<int, int> pint;

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

#define MOD (1000 * 1000 * 1000 + 7)

int solve(vector<int> m, int N, int K, int MAX) {
    if (K == 1) return N;

    int ans = 0;

    while (true) {
        int cnt = 0;
        vector<pair<int, int>> a;
        int MIN;
        int NOW_MAX = 0;

        int use_count = 0;
        // cerr << "MAX = " << MAX << endl;
        RREPS(i, MAX) {
            int l = m[i];
            if (l == 0) continue;

            a.pb(mp(i, l));
            cnt += l;
            MIN = i;
            NOW_MAX = max(NOW_MAX, i);

            if (cnt >= K) {
                int CCC = 1;
              

                use_count = i;

                ans += use_count * CCC;

                int remain = cnt - K * CCC;
                int M = SZ(a);
                RREP(j, M) {
                    int n = a[j].second - remain;
                    m[a[j].first] -= n;
                    m[a[j].first - use_count] += n;

                    remain = 0;
                }

                break;
            }
        }

        MAX = max(MIN, NOW_MAX - use_count);

        if (N - (m[0]) < K) break;
    }

    return ans;
}

signed main() {
    int N;
    cin >> N;

    vector<int> A(N);
    REP(i, N) {
        cin >> A[i];
        A[i]--;
    }

    vector<int> cnt(N, 0);
    REP(i, N) {
        cnt[A[i]]++;
    }

    int MAX = 0;
    REP(i, N) {
        MAX = max(MAX, cnt[i]);
    }

    vector<int> m(MAX+1, 0);
    int kind = 0;
    REP(i, N) {
        m[cnt[i]]++;
        if (cnt[i] > 0) kind++;
    }

    REP(i, N) {
        int ans = 0;

        if (i <= kind) {
            ans = solve(m, N, i+1, MAX);
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 5488
#include <bits/stdc++.h>
#define rep(i,n); for(long long i = 0;i < (n);i++)
using namespace std;
typedef long long ll;
int main(){
  ll n; cin >> n;
  string s; cin >> s;
  if(n % 2 == 1)cout << "No" << endl;
  else{
    bool a = true;
    rep(i,n/2)if(s[i] != s[i+n/2])a = false;
     if(a)cout << "Yes" << endl;
     else cout << "No" << endl;
  }
}

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

ll w,h;
vector<vector<ll>> v;
void dfs(int x, int y){
  v[x][y] = 0;
  rep(i,8){
    int nx = x+dx[i],ny = y+dy[i];
    if(value(nx,ny,w,h) && v[nx][ny]){
      dfs(nx,ny);
    }
  }
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(cin >> w >> h && w && h){
    v = vector<vector<ll>>(w,vector<ll>(h,0));
    rep(i,h){
      rep(j,w){
        cin >> v[j][i];
      }
    }
    ll ans = 0;
    rep(i,h){
      rep(j,w){
        if(v[j][i]){
          ++ans;
          dfs(j,i);
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3268
N, x = [int(i) for i in input().split()]
import sys

if x == 1 or x == 2*N-1:
    if N != 1:
        print('No')
        sys.exit()
    else:
        print('Yes')
        print(1)
        sys.exit()

smaller = True
if x > N:
    smaller = False
    x = 2*N-x

ans = list(range(2*N-1,N+x-1,-1))+list(range(1,N+x))
if not smaller:
    ans =[2*N - ans[i] for i in range(2*N-1)]

print('Yes')
for i in range(2*N-1):
    print(ans[i])

Measured memory_bytes: 19924
#include <stdio.h>
#include<ctype.h>
int main()
{
    char a[15],b[15],c[15];
    scanf("%s %s %s", a,b,c);
    a[0] = toupper(a[0]);
    b[0] = toupper(b[0]);
    c[0] = toupper(c[0]);
    printf("%c%c%c", a[0],b[0],c[0]);
    
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,m;string S;
int main(){
	while(true){
		cin>>n;if(n==0)break;cin>>m>>S;int G=0,cnt=0;
		for(int i=0;i<m;i++){
			if(G%2==0 && S[i]=='I')G++;
			else if(G%2==1 && S[i]=='O')G++;
			else{G=0;if(S[i]=='I')G=1;}
			if(G>=n*2 && G%2==1)cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

Measured memory_bytes: 3888
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
const long MOD = 1000000007;
#define all(a) a.begin(), a.end()
#define eall(a) a.begin()+1, a.end()
#define show(ans)  cout << ans << endl;

int main(){
long N;
cin >> N;
vector<long> V(N+1);
vector<long> C(N+1);
erep(i, N) cin >> V[i];
erep(i, N) cin >> C[i];

erep(i, N) V[i] -= C[i];
long ans = 0;
erep(i, N){
    if(V[i] >= 0) ans += V[i];
}

show(ans);

return 0;
}

Measured memory_bytes: 256
/// Updated! https://www.youtube.com/watch?v=U07_n9xGIlM
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define dbug printf("I am here\n");
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int maxn = 2e5+100;

const ll inf = 1e18;
ll dp[maxn] , n;
vector < pair < ll , ll > > arr;

int ind(int lo , ll x){
    int ans = n;
    int hi = n-1;
    while(lo <= hi){
        int mid = (lo + hi)/2;
        if(arr[mid].first >= x){
            ans = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
    return ans;
}

int solve(int i){
    if(i == n)return 0;
    ll &ret = dp[i];
    if(ret != -1)return ret;
    int in = ind(i+1,arr[i].second);
    ret = max(solve(i+1),1+solve(in));
    return ret;
}

int main()
{
    cin >> n;
    for(int i = 1; i<=n; i++){
        ll x , li; cin >> x >> li;
        arr.push_back({x-li,x+li});
    }
    sort(arr.begin(),arr.end());
    memset(dp,-1,sizeof dp);
    cout << solve(0) << endl;
    return 0;
}
/*



*/



Measured memory_bytes: 6640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;

int main()
{
    int a, b, k;
    cin >> a >> b >> k;
    int count = 0;

    for (int i = max(a, b); i >= 1; i--)
    {
        if (a % i == 0 && b % i == 0)
            count++;
        if (count == k)
        {
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin(), v.end()
bool chmin(ll & a, ll  b) { if (b < a) { a = b; return 1; } return 0; }
bool chmax(ll & a, ll b) { if (b > a) { a = b; return 1; } return 0; }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N=500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
int main() {
    cin >> a>>b>>m;
    vl A,B;
    rep(i,a){
        cin>>x;
        A.push_back(x);
    }
    rep(i,b){
        cin>>x;
        B.push_back(x);
    }

    ans=INF;

    rep(i,m){
        cin>>a>>b>>c;
        ans=min(ans,A[a-1]+B[b-1]-c);
    }
    
    sort(all(A));
    sort(all(B));
    
    ans=min(ans,A[0]+B[0]);

    cout<<ans<<endl;
}

Measured memory_bytes: 2548
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const int INF=1e7;
const LL LINF=1e18;
using edge=struct{P p;int c;};

int cost[101][101];
vector<edge> vec;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >>M;
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            cost[i][j]=INF;
        }
    }
    for(int i=0;i<M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        cost[a][b]=c;
        cost[b][a]=c;
        vec.push_back({make_pair(a,b),c});
    }
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<vec.size();i++){
        edge e;
        e=vec[i];
        P s;
        s=e.p;
        if(cost[s.first][s.second]<e.c) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  string s;
  int a,b,i;
  cin >> s >> a >> b;

  bitset<16000> x(0),y(0);
  int dx=0,dy=0;
  for(i=0;i<s.size();i++){
    if(s[i]=='F') dx++;
    else break;
  }
  x[8000+dx]=true;
  y[8000]=true;

  while(i<s.size()){
    dx=0;dy=0;
    for(i++;i<s.size();i++){
      if(s[i]=='F') dy++;
      else break;
    }
    for(i++;i<s.size();i++){
      if(s[i]=='F') dx++;
      else break;
    }
    x=(x<<dx)|(x>>dx);
    y=(y<<dy)|(y>>dy);
  }

  if(x[8000+a]==1&&y[8000+b]==1) printf("Yes");
  else printf("No");
  return 0;
}


Measured memory_bytes: 256
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
X = int(input())
prices = [100,101,102,103,104,105]

#
# dp = [0 for i in range(2002)]
# for price in prices:
#     dp[price] = 1
# for i in range(len(dp)):
#     for price in prices:
#         if i > price and dp[i-price] == 1:
#             dp[i] = 1
#
# if X > 2000:
#     print("1")
# else:
#     print(dp[X])



dp = [0 for i in range(max(X + 1, 106))]
for price in prices:
    dp[price] = 1
for i in range(len(dp)):
    for price in prices:
        if i > price and dp[i - price] == 1:
            dp[i] = 1

print(dp[X])


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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1000000000000007ll;

const double eps = 1e-10;

const i64 MAXN = 5005;

i64 n;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> n;

    set<pair<i64, i64>> q;
    for (i64 i = 1; i < n; i++) {
        i64 j = n - i;
        if ( i == j) {
            continue;
        }
        q.insert({min(i, j), max(i ,j)});
    }

    cout << q.size() << endl;

    return 0;
}


Measured memory_bytes: 31488
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int n;
  cin >> n;
  VEC<int> p(n);
  REP(i, 0, n) {
    int a;
    cin >> a;
    if (a == i + 1)
      p[i] = 1;
    else
      p[i] = 0;
  }
  int cnt = 0;
  REP(i, 0, n - 1) {
    if(p[i] && p[i+1]){
      ++cnt;
      p[i] = p[i + 1] = 0;
    }else if(p[i]){
      ++cnt;
      p[i] = 0;
    }
    
  }
  if(p[n-1])
    ++cnt;
  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 640
#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)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define bit(k) (1LL<<(k))
typedef long long ll;

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);

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

/*------------------------------------/
for library*/

/*------------------------------------*/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll A,B,K;
    cin>>A>>B>>K;
    if(K >= A){
        K -= A;
        A = 0;
        B = max(0LL,B - K);
    }
    else{
        A -= K;
    }
    cout<<A<<" "<<B<<endl;
}

Measured memory_bytes: 256
import sys
# from math import sqrt, gcd, ceil, log
# from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	n = int(input()); s = inp()
	ans = 1
	for i in range(1, n):
		if s[i-1] != s[i]:
			ans += 1
	print(ans)


		

if __name__ == "__main__":
	solve()

Measured memory_bytes: 9528
//hi
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long int LL;
int a[303][303];
int b[303][303];
int c[303][303];
int n;
bool check(){
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(a[i][j]!=b[i][j]) return false;
	return true;
}
int main(void){
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
		for(j=0;j<n;j++){
			scanf("%d",&a[i][j]);
			c[i][j]=b[i][j]=a[i][j];
		}
	for(int k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++){
				if(i==k || k==j || i==j) continue;
				b[i][j]=min(b[i][j], b[i][k]+b[k][j]);
				c[i][j]=b[i][j];
			}
	if(!check()){
		printf("-1\n");
	}else{
		for(int k=0;k<n;k++)
			for(i=0;i<n;i++)
				for(j=0;j<n;j++){
					if(i==k || k==j || i==j) continue;
					if(c[i][j]==b[i][k]+b[k][j]) c[i][j]=0;
				}
		LL l=0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				l+=c[i][j];
		printf("%lld\n",l/2);
	}
    return 0;
}


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

int main(){
  string S, T;
  int lengS, lengT;
  cin >> S >> T;
  lengS = S.length();
  lengT = T.length();
  int diff = S.compare(0, lengS, T, 0, lengS);
  if(diff == 0 && lengT == lengS + 1){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

public class Main{

	public static void main(String[] args) throws IOException
	{
		int m,f,r,sum,i;
		char cRank[] = new char[256];

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

		for(i=0; i<255; i++)
		{
			String[] mfr = br.readLine().split(" ");
			m = Integer.parseInt(mfr[0]);
			f = Integer.parseInt(mfr[1]);
			r = Integer.parseInt(mfr[2]);

			sum = m+f;

			if(sum+r == -3)  break;

			else if(m*f < 0 || sum < 30) cRank[i] = 'F';

			else if(30 <= sum && sum < 50) cRank[i] = (50 <= r)? 'C' : 'D';

			else if(50 <= sum && sum < 65) cRank[i] = 'C';

			else if(65 <= sum && sum < 80) cRank[i] = 'B';

			else if(80 <= sum ) cRank[i] = 'A';

		}

		br.close();

		for(int n=0; n<i; n++) System.out.println(cRank[n]);
	}
}

Measured memory_bytes: 24212
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N=1e5+5;

int n, suma=0, sumb=0, ans=0, reqd=0;
int a[N], b[N];
vector<int> excess;

int32_t main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		suma+=a[i];
	}	
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		sumb+=b[i];
		if(a[i]<b[i])
		{
			reqd+=b[i]-a[i];
			ans++;
		}
		else if(a[i]>b[i])
		{
			excess.push_back(a[i]-b[i]);
		}
	}
	if(suma<sumb)
	{
		cout<<"-1";
		return 0;
	}
	sort(excess.rbegin(), excess.rend());
	for(auto &it:excess)
	{
		if(reqd<=0)
			break;
		ans++;
		reqd-=it;
	}
	cout<<ans;
	return 0;
}

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

const int N = 100100;

int p[N][3];
int dp[N][4];
int n;


int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d", &p[i][0], &p[i][1], &p[i][2]);
    
    dp[0][0] = p[0][0];
    dp[0][1] = p[0][1];
    dp[0][2] = p[0][2];

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int q = 0; q < 3; ++q) {
                if (q == j) {
                    continue;
                }
                dp[i][j] = max(dp[i][j], dp[i - 1][q]  + p[i][j]);
            }
        }
    }

    printf("%d\n", max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}));
}



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

const long long inf = (long long)1e16;

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

    int n;
    cin >> n;
    vector <long long> A(n);
    long long sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> A[i];
        sum += A[i];
    }
    long long ans = inf;
    long long cnt = 0;
    for(int i = 0; i < n - 1; i++) {
        cnt += A[i];
        ans = min(ans, abs((sum - cnt) - cnt));
    }
    cout << ans;

    return 0;
}

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

int main(){
    string s;
    cin >> s;
    
    int start, end;
    
    for (int i = 0; i < s.size(); i++) {
        if (s.at(i) == 'A') {
            start = i;
            break;
        }
    }
    
    for (int i = 0; i < s.size(); i++) {
        if (s.at(i) == 'Z') {
            end = i;
        }
    }
    
    cout << end - start + 1 << endl;
    
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;

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


void solve(){
	int n,k;
	cin >> n >> k;
	map<int,int> has;
	for(int i =0;i<k;i++){
		int d;
		cin >> d;
		forn(j,0,d){
			int a;
			cin >> a;
			has[a]++;
		}
	}
	int ans =0 ;
	for(int i =1;i<=n;i++){
		if(has[i]==0)
			ans++;
	}
	cout<< ans << endl;
}

int main(){
	fast;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	// int t;cin >> t;while(t--)
		solve();
}

Measured memory_bytes: 3668