akhauriyash/Code-Regression huggingface dataset:
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;

void main()
{
	int cnt;
	foreach (line; stdin.byLine) {
		auto s = line.chomp;
		auto t = s.dup.reverse;
		if (s == t) cnt++;
	}
	cnt.writeln;
}

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

#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9+7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

bool isRoute[3000] = {};
bool isS2G[3000] = {};
bool isG2S[3000] = {};
vector<vector<ll>> S2G(3000);
vector<vector<ll>> G2S(3000);
void dfs_s2g(ll pos){
    isS2G[pos] = true;
    rep(i, S2G[pos].size()){
        if(isS2G[S2G[pos][i]])continue;
        dfs_s2g(S2G[pos][i]);
    }
}
void dfs_g2s(ll pos){
    isG2S[pos] = true;
    rep(i, G2S[pos].size()){
        if(isG2S[G2S[pos][i]])continue;
        dfs_g2s(G2S[pos][i]);
    }
}

struct edge{ll from, to, cost;};
bool Bellman_ford(vector<edge> es, ll start, ll num_ver, ll num_edge, vector<ll> &min_dist){
    fill(ALL(min_dist), -1*LINF);

    min_dist[start] = 0;

    rep(i, num_ver)rep(j, num_edge){
        edge e = es[j];

        if(!isRoute[e.from] || !isRoute[e.to])continue;

        if(min_dist[e.to] < min_dist[e.from] + e.cost){
            min_dist[e.to] = min_dist[e.from] + e.cost;
            if(i == num_ver -1)return true;
        }
    }

    return false;
}

int main(){
    ll n, m, p;
    cin >> n >> m >> p;

    vector<edge> es(m);
    rep(i, m){
        ll a, b, c;
        cin >> a >> b >> c;

        a--, b--;
        es[i].from = a;
        es[i].to = b ;
        es[i].cost = c - p;

        S2G[a].push_back(b);
        G2S[b].push_back(a);
    }

    dfs_s2g(0);
    dfs_g2s(n-1);

    rep(i, n){
        isRoute[i] = isS2G[i]*isG2S[i];
    }

    vector<ll> ans(n);
    if(Bellman_ford(es, 0, n, m, ans))cout << -1 << endl;
    else cout << max((ll)0, ans[n-1]) << endl;
}


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

public class Main {
    public static int MAXN = 1600;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n=cin.nextInt();
        if(n<10){
        	out.println("Yes");
        }else if(n>=10&&n<100){
        	if((n%10)==(n/10)){
        		out.println("Yes");
        	}else{
        		out.println("No");
        	}
        }else{
        	if((n%10)==(n/100)){
        		out.println("Yes");
        	}else{
        		out.println("No");
        	}
        }
        out.flush();
        out.close();
        cin.close();
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'
const int N = 1e5;
const int inf = 1e9;
int A[N+7], dp[N+7];
int n;

int solve(int i) {
	if(i==n-1) return 0;
	if(dp[i]!=-1) return dp[i];
	int res1 = solve(i+1) + abs(A[i]-A[i+1]);
	int res2 = inf;
	if(i+2<=n-1) res2 = solve(i+2)+abs(A[i]-A[i+2]);
	return dp[i] = min(res1, res2);
}
int main(){
	ios_base::sync_with_stdio(0);
	int a,b,T,cas=0;
	cin>>n;
	for(int i=0;i<n;++i) cin>>A[i];
	fill(dp,dp+n,-1);
	int res=solve(0);
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 5760
#include <cstdio>
#include <iostream>
using namespace std;
int main(){
    int a[5];
    int s, l;
    
    for(int i = 0; i < 3; ++i){
        scanf("%d", &a[i]);
    }
    s=a[0]*a[1];
    l=a[0]*2 + a[1]*2;
    
    cout << s << " " << l <<endl;
    
    return 0;
    
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n ; ++i)
#define REP(i,a,b) for(int i=a; i<b; ++i)
typedef long long ll;
//プロトタイプ宣言
int gcd(int , int);


int main(){
  int a,b;
  cin >> a >> b;
  int ans = max((a+b),(a-b));
  ans = max(ans , (a*b));
  cout << ans << endl;
}









































//以下、ライブラリ
//ユークリッドの互除法

int gcd(int a, int b) {
  return b ? gcd(b, a%b) : a;
}



Measured memory_bytes: 256
found = []
for s in range(4):
    suit = []
    for i in range (14):
        suit.append(False)
    found.append(suit)
    
num_card = int(input())
for i in range(num_card):
    suit, rank = input().split()
    suit = 'SHCD'. index(suit)
    rank = int(rank)
    found[suit][rank] = True
    
for s in range(4):
    for r in range(1,14):
        if found[s][r] == False:
            suit = 'SHCD'[s]
            print(suit, r)


Measured memory_bytes: 5600
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
ch-=1
cw-=1
dh,dw=nii()
dh-=1
dw-=1
s=[list(input()) for i in range(h)]

dist=[[-1]*w for i in range(h)]

def BFS(que):
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]

    for i in range(-2,3):
      for j in range(-2,3):
        ny=y+i
        nx=x+j
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
          que.append((ny,nx))
          dist[ny][nx]=dist[y][x]+1

dist[ch][cw]=0

que=deque()
que.append((ch,cw))

BFS(que)

print(-1)

Measured memory_bytes: 134888
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<long long int> nums(n);
    for(int i=0;i<n;i++)
        cin>>nums[i];
    vector<int> mini(n);
    long long int m=INT_MAX;
    for(int i=n-1;i>=0;i--)
    {
        m=min(m,nums[i]);
        mini[i]=m;
    }
    // for(int i=0;i<n;i++)
    //     cout<<mini[i]<<" ";
    // cout<<endl;
    for(int i=0;i<n;i++)
    {
        if(nums[i]-mini[i]>1)
        {
            cout<<"No" << endl;
            return 0;
        }
    }
    cout<<"Yes" << endl;
	return 0; 
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	int c[27];
	cin>>s;
	for(int i=0;i<26;i++){
		c[i]=0;
	}
	for(int i=0;i<s.size();i++){
		c[s[i]-'A']=c[s[i]-'A']+1;
	}
	for(int i=0;i<26;i++){
		if(c[i]!=2 and c[i]!=0){
			cout<<"No";
			return 0;
		} 
	}
	cout<<"Yes";
	return 0;
} 

Measured memory_bytes: 256
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))

N, M = inpl()
X = inpl()
Q = int(input())
L = inpl()

X += [N+1]
initcost = X[0] - 1
costs = [X[i+1] - X[i] - 1 for i in range(M) if X[i+1] - X[i] > 1]
C = [0]*(N+1)
C[0] = - 10**9

for i in range(1, N+1):
    cost = 0
    costs2 = []
    for c in costs:
        cost += c
        if c > 1:
            costs2.append(c-1)
    C[i] = - (initcost + cost)
    costs = costs2

for l in L:
    if l < - C[-1]:
        print(-1)
    else:
        print(bisect_left(C, -l))


Measured memory_bytes: 19824
#include <stdio.h>

int gcd(int i,int j,int k)
{
  int min;
  
  if(i<j)
    min=i;
  else
    min=j;
  if(k<min)
    min=k;
  for(int cnt=min;cnt>0;cnt--)
  {
    if (i%cnt==0 && j%cnt==0 && k%cnt==0)
      return (cnt);
  }
  return(0);
}

int main()
{
  int num;
  long ans=0;
  
  scanf("%d",&num);
  for(int i=1;i<=num;i++)
  {
    for(int j=1;j<=num;j++)
    {
      for(int k=1;k<=num;k++)
      {
        ans+=gcd(i,j,k);
      }
    }
  }
  printf("%lu",ans);
}

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

long long int N,G,w[200],p[200],dp[200][100001],ans;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        cin >> N >> G;
        for (int i=1; i<=N; i++) {
            cin >> w[i] >> p[i];
        }


        for (int i=1; i<=N; i++) {
            for (int j=1; j<=G; j++) {
                if (j>=w[i]) {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
                }
                else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
       cout << dp[N][G];
       /*for (int i=1 ; i<=N; i++) {
           for (int j=1; j<=G; j++) {
            cout << dp[i][j] << " ";
           }
           cout << '\n';
       }*/
}


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

int main(){
	bool cards[4][13];
	for(int i=0;i<4;i++){
		for(int j=0;j<13;j++){
			cards[i][j]=false;
		}
	}
	int n, num; char suit;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> suit >> num;
		switch(suit){
			case 'S': cards[0][num-1]=true; break;
			case 'H': cards[1][num-1]=true; break;
			case 'C': cards[2][num-1]=true; break;
			case 'D': cards[3][num-1]=true; break;
		}
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<13;j++){
			if(!cards[i][j]){
				switch(i){
					case 0: cout << "S " << j+1 <<endl; break;
					case 1: cout << "H " << j+1 <<endl; break;
					case 2: cout << "C " << j+1 <<endl; break;
					case 3: cout << "D " << j+1 <<endl; break;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1160
from collections import defaultdict
dic = defaultdict(int)
n = int(input())
ns = map(int, input().split())
for i in ns:
    dic[i] += 1
result = 0
for key, value in dic.items():
    if key < value:
        result += value - key
    elif key > value:
        result += value
print(result)

Measured memory_bytes: 23656
#include <cstdio>
#include <algorithm>
using namespace std;

void print_A(int A[],int n){
	for (int i = 0 ;i<n;i++) {
		if (i!=n-1 )printf("%d ",A[i]);
		else printf("%d",A[i]);
	}
	printf("\n");
	return ;
}

int bubblesort(int A[],int n){
	int count=0;
	for (int i =0 ;i<n;i++){
		for(int j=n-1;j>=i+1;j--){
			if(A[j-1]>A[j]) {swap(A[j-1], A[j]);count++;} 
		}
	}
	return count;
}

int main (){
	int n,A[110];
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	int a = bubblesort(A,n);
	print_A(A,n);
	printf("%d\n",a);
	return 0;
}


Measured memory_bytes: 2716
#include <stdio.h>
#include <string.h>

int main(){
    int n, i=1;
    char cchar[100], vchar[100], *cptr, *vptr;

    scanf("%d %[^\n] %[^\n]", &n, vchar, cchar);
    // printf("%s \n", vchar);
    // printf("%s \n", cchar);

    int c[n], v[n];
    int ans=0;

    cptr = strtok(cchar, " ");
    c[0] = atoi(cptr);

    while(cptr != NULL) {
        cptr = strtok(NULL, " ");

        if(cptr != NULL) {
            c[i] = atoi(cptr);
        }
        i += 1;
    }

    vptr = strtok(vchar, " ");
    v[0] = atoi(vptr);

    i = 1;
    while(vptr != NULL) {
        vptr = strtok(NULL, " ");

        if(vptr != NULL) {
            v[i] = atoi(vptr);
        }
        i += 1;
    }

    for(i=0; i<n; i++) {
        if(v[i] > c[i]) {
            ans += v[i] - c[i];
            // printf("%d %d %d %d\n", ans, v[i], c[i], i);
        }
    }

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

    return 0;
}

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

int main(){
    int N; cin >> N;
    string S; cin >> S;
    rep(i,S.size()){
        if(S[i]+N >'Z'){
            printf("%c",S[i]+N-26);
        }
        else{
            printf("%c",S[i]+N);
        }
    }
}

Measured memory_bytes: 256
n=int(input())
s=input()

higashi=[0]*(n+1)
nishi=[0]*(n+1)

for i in range(0,n):
    nishi[i+1]=nishi[i]
    higashi[n-1-i]=higashi[n-i]
    if s[i]=="W":
        nishi[i+1]+=1
    if s[n-1-i]=="E":
        higashi[n-1-i]+=1

ans=[0]*(n+1)    
for i in range(n+1):
    ans[i]=nishi[i]+higashi[i]

print(min(ans))

Measured memory_bytes: 47836
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;

int n,k,x,a[N],ans;

int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	cin >> n >> k;
	for (int i=1;i<=n;i++){
		cin >> x;
		k-=!a[x];
		a[x]++;
	}
	sort(a+1,a+n+1);
	int i=1;
	while (!a[i]){
		i++;
	}
	k=-k;
	for (;k>0;k--){
		ans+=a[i];
		i++;
	}
	cout << ans << "\n";
}

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

int main() {
	int *A, *a, N, *b, count = 0;
	
	A = new int[9];
	a = new int[9];

	for (int i = 0; i < 9; i++) {
		cin >> A[i];
		a[i] = 0;
	}

	cin >> N;

	b = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> b[i];
	}

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < N; j++) {
			if (A[i] == b[j]) {
				a[i] = 1;
				count += 1;
			}
				if (count >= 7) {
				cout << "Yes";
				goto end;
			}
		}
	}

	if (a[0] + a[1] + a[2] == 3 || a[3] + a[4] + a[5] == 3 || a[6] + a[7] + a[8] == 3 || a[0] + a[3] + a[6] == 3 || a[1] + a[4] + a[7] == 3 || a[2] + a[5] + a[8] == 3 || a[0] + a[3] + a[6] == 3 || a[1] + a[4] + a[7] == 3 || a[0] + a[4] + a[8] == 3 || a[0] + a[3] + a[6] == 3 || a[1] + a[4] + a[7] == 3 || a[2] + a[4] + a[6] == 3) cout << "Yes";
	else cout << "No";

	end:

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  100005

void solve()
{
    ll n,k;
    cin>>n>>k;
    ll a[n+1];
    rep(i,1,n+1)cin>>a[i];
    ll dp[k+1];
    memset(dp,0,sizeof(dp));
    rep(i,1,k+1)
    {
        rep(j,1,n+1)
        {
            if(a[j]<=i)
            {
                if(dp[i-a[j]]==0)
                {
                    dp[i]=1;
                    break;
                }
            }
        }
    }
    cout<<((dp[k]==1)?"First":"Second")<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4380
#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, n;
    int a[114] = {};
    cin >> x >> n;
    if (n == 0) {
        cout << x << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int p = lower_bound(a, a+n, x) - a;
    int c = 0;
    while (true) {
        if (!binary_search(a, a+n, x-c)) {
            cout << x-c << endl;
            return 0;
        }
        if (!binary_search(a, a+n, x+c)) {
            cout << x+c << endl;
            return 0;
        }
        c++;
    }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main() {
  string s;
  cin >> s;
  
  if (s == "Sunny") puts("Cloudy");
  else if (s == "Cloudy") puts("Rainy"); 
  else if (s == "Rainy") puts("Sunny");

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int N;
int score[5];
void output(int a[5][5]){
  REP(i, 5){
    REP(j, 5) printf("%d ", a[i][j]);
    printf("\n");
  }
}
int point(int a[5][5]){
  int bonus = 1;
  int res = 0;
  while(true){
    bool del[5][5] = {};
    bool update = false;
    REP(y, 5) for(int i = 2; i < 5; i++) {
      if(a[y][i-2] == a[y][i-1] && a[y][i-1] == a[y][i] && a[y][i] != 0){
        del[y][i-2] = del[y][i-1] = del[y][i] = true;
        update = true;
      }
    }
    REP(x, 5) for(int i = 2; i < 5; i++) {
      if(a[i-2][x] == a[i-1][x] && a[i-1][x] == a[i][x] && a[i][x] != 0){
        del[i-2][x] = del[i-1][x] = del[i][x] = true;
        update = true;
      }
    }
    if(!update) break;
    REP(y, 5)REP(x, 5) if(del[y][x]){
      res += score[a[y][x] - 1] * bonus;
      a[y][x] = 0;
    }
    //output(a);
    //printf("v\n");
    REP(x, 5){
      queue<int> que;
      for(int y = 4; y >= 0; y--)if(a[y][x] != 0){
        que.push(a[y][x]);
      }
      for(int y = 4; y >= 0; y--){
        if(que.empty()){
          a[y][x] = 0;
        }else{
          a[y][x] = que.front();
          que.pop();
        }
      }
    }
    //output(a);
    //printf("\n\n");
    bonus += 1;
  }
  return res;
}
int dfs(int a[5][5], int k, int x, int y){
  int res = 0;
  int tmp[5][5];
  REP(i, 5)REP(j, 5) tmp[i][j] = a[i][j];
  res = point(tmp);
  if(k == N) return res;
  REP(r, 4){
    int nx = x + dx[r];
    int ny = y + dy[r];
    if(valid(nx, ny, 5, 5)){
      swap(a[y][x], a[ny][nx]);
      res = max(res, dfs(a, k + 1, nx, ny));
      swap(a[y][x], a[ny][nx]);
    }
  }
  return res;
}
int main(){
  while(cin >> N && N != -1){
    int a[5][5];
    REP(i, 5)REP(j, 5) cin >> a[i][j];
    REP(i, 5) cin >> score[i];
    int ans = 0;
    REP(y, 5)REP(x, 5) ans = max(ans, dfs(a, 0, x, y));
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
	cin>>a[i];
	sort(a,a+n,cmp);
	long long s1=0,s2=0;
	for(int i=0;i<n;i+=2)
	s1+=a[i];
	for(int i=1;i<n;i+=2)
	s2+=a[i];
	cout<<s1-s2;
	return 0;
}

Measured memory_bytes: 256
import sys
H, W = [int(x) for x in input().split()]
s = ['.' * (W + 2)] + ['.' + input() + '.' for _ in range(H)] + ['.' * (W + 2)]

for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            if s[i - 1][j] == '.' and s[i + 1][j] == '.'\
                and s[i][j - 1] == '.' and s[i][j + 1] == '.':
                print("No")
                sys.exit()
print("Yes")

Measured memory_bytes: 3064
#include "iostream"
#include "string"
#include "vector"
#include "algorithm"
#include "functional"
#include "cmath"
#include "set"

#define NDEF -200
#define NA -100
#define N_MAX 10000

std::vector<unsigned int> required_match{2, 5, 5, 4, 5, 6, 3, 7, 6};

std::vector<int> max_digit(N_MAX + 1, NDEF);


// setting max_digit[0]
void init_max_digit() {
    max_digit[0] = 0L;
    return;
}

// get max_digit by DP
int get_max_digit(int num_match, std::set<unsigned int> required_match_part) {
    if(max_digit[num_match] != NDEF) {
        return max_digit[num_match];
    } else {
        int maybe_max = NA;
        for (unsigned int required_num:required_match_part) {
            int remain_match = num_match - required_num;
            int remain_digit = (remain_match >= 0) ?
                    get_max_digit(remain_match, required_match_part) : NA;
            if (remain_digit >= 0) {
                maybe_max = std::max(maybe_max, remain_digit + 1);
            }
        }
        max_digit[num_match] = maybe_max;
        return maybe_max;
    }
}

int main(){
    init_max_digit();

    // get values from input
    int n, m;
    std::vector<int> a;

    std::cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a_i;
        std::cin >> a_i;
        a.push_back(a_i);
    }

    // main procedure
    std::vector<int> digits_allowed = a; // sorted as desc
    std::sort(digits_allowed.begin(), digits_allowed.end(), std::greater<int>());

    std::set<unsigned int> required_match_part;
    for (int digit:digits_allowed) {
        required_match_part.insert(required_match[digit - 1]);
    }

    std::string ans;
    int remain_digit_num = get_max_digit(n, required_match_part);
    int remain_match_num = n;

    while (remain_match_num > 0) {
        int is_find = false;
        for (int digit:digits_allowed) {
            int match_num_tmp = remain_match_num - required_match[digit - 1];
            if (match_num_tmp < 0) {
                continue;
            }

            int digit_num_tmp = get_max_digit(match_num_tmp,
                    required_match_part);
            if (digit_num_tmp == remain_digit_num - 1){
                ans += std::to_string(digit);
                remain_match_num = match_num_tmp;
                remain_digit_num--;
                is_find = true;
                break;
            }
        }
        if (!is_find) {
            break;
        }
    }

    // output
    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 2432
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;
int gcd(int a, int b)
{
    if(b) return gcd(b,a%b);
    return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

int n,dp[1 << 18],lst[1 << 18];

int32_t main(){_
    //freopen("in","r",stdin);
	cin >> n;
	dp[0] = 1;
	for(int i = 1;i <= n;i++)
	{
		int x;
		cin >> x;
		dp[i] = dp[i - 1];
		if(lst[x] && lst[x] != i - 1) dp[i] += dp[lst[x]];
		dp[i] %= mod;
		lst[x] = i;
	}
	rc(dp[n]);
}

Measured memory_bytes: 3840
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repe(i, n) for(int i = 0; i <= (n); i++)
#define fo(i, a, b) for(int i = (a); i < (b); i++)
#define foe(i, a, b) for(int i = (a); i <= (b); i++)
#define NL << endl

using namespace std;
using ll = long long;
const int INTMAX = numeric_limits<int>::max();
const ll LLMAX = numeric_limits<long long>::max();
const int MOD = 1000000007;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector<char>> f(n, vector<char>(10, 0));
	vector<vector<int>> p(n, vector<int>(11, 0));

	rep(i, n) rep(j, 10) cin >> f[i][j];
	rep(i, n) rep(j, 11) cin >> p[i][j];

	vector<int> b(10);
	b[0] = 1;
	fo(i, 1, 10) {
		b[i] = b[i - 1] << 1;
	}
	int ans = numeric_limits<int>::min();

	fo(i, 1, (1 << 10)) {
		int v = 0;
		rep(j, n) {
			int cnt = 0;
			rep(c, 10) {
				if ((b[c] & i) && f[j][c] == '1') {
					cnt++;
				}
			}
			v += p[j][cnt];
		}
		ans = max(ans, v);
	}

	cout << ans NL;

	return 0;

}

Measured memory_bytes: 256
/*
 * author :Sadik Hassan
 *
*/
#include "bits/stdc++.h"
using namespace std;
#define ll            long long
#define nl            "\n"
#define pb            push_back
#define fi            first
#define se            second
#define PI            (acos(-1.0))
#define repp(i,a,n)   for(int i=a;i<n;i++)
#define rep(i,n)      for(int i=0;i<n;i++)
#define SZ(s)         s.size()
#define SRT(x,y)      sort(x,x+y)
#define REV(a,b)      reverse(a,a+b)
#define VSRT(x)       sort(x.begin(),x.end())
#define VREV(x)       reverse(x.begin(),x.end())
#define w(t)          int t;cin>>t;while(t--)
#define TSFL(s)       transform(s.begin(),s.end(),s.begin(),::toupper);
#define TSFH(s)       transform(s.begin(),s.end(),s.begin(),::tolower);
#define _SAD()        ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
typedef vector<int> vi;
typedef vector<ll> vii;
typedef set<int> si;
typedef set<ll> sii;
/*---------------------------------------------------------------------*/

const int N = 2e5+10;
const int INF = (int)1e9+5;

int main()
{
    _SAD()
    string s;
    cin>>s;
    if(s=="ABC")cout<<"ARC"<<nl;
    else cout<<"ABC"<<nl;
    return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main() {
	ll a, b;
	cin >> a >> b;
	if ((a + b) % 2 == 0) {
		cout << (a + b) / 2 << endl;
		return 0;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}
}

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

int gcd(int a,int b){
	if(a>b) swap(a,b);
	if(b%a==0){
		return a;
	}else{
		return gcd(a,b%a);
	}
}
int main() {
    int n,m,i,j,cur,ans;
    cin >> n;
	vector<int> a(n);
	for(i=0; i<n; i++){
		cin >> a[i];
	}
	
	sort(a.begin(),a.end());
	reverse(a.begin(),a.end());
	
	cur=a[0];
	for(i=1; i<n; i++){
		cur=gcd(cur,a[i]);
	}
	if(cur>1){
		cout << "not coprime" << endl; return 0;
	}
	
	vector<bool> p(1000001,false);
		
	for(i=0; i<n; i++){
		cur=a[i];
		for(j=2; j*j<=cur; j++){
			if(cur%j==0){
				if(p[j]==true){
					cout << "setwise coprime" << endl; return 0;
				}else{
					p[j]=true;
					while((cur%j)==0){
						cur/=j;
					}
				}
				
				
			}
		}
		if(cur>1){
			if(p[cur]==true){
				cout << "setwise coprime" << endl; return 0;
			}else{
				p[cur]=true;
			}
		}
	}
	cout << "pairwise coprime" << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main(int argc, char const *argv[]) {

  ll a, b, c; cin >> a >> b >> c;
  ll right = 4 * a * b, left;
  ld tmp = c - a - b;
  
  left = pow(tmp,2);
  
  /* cout << right << " " << left << endl; */
  if (right < left && tmp > 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
def set_ball(i):
    index = i
    ball_count = 0
    while(True):
        ball_count += ball_status[index]
        index += i + 1
        if(index  >= N):
            break
    return (ball_count % 2) != a_list[i]

N = int(input())
a_list = list(map(int, input().strip().split()))

ball_status = [0 for i in range(N)]
for i in range(N):
    flag = set_ball(N-1-i)
    if(flag):
        ball_status[N-1-i] = 1
throw_balls = sum(ball_status)
print(throw_balls)
if(throw_balls > 0):
    ans = ""
    for i in range(N):
        if(ball_status[i] == 1):
            ans += str(i+1)
            ans += " "
    print(ans[:-1])

Measured memory_bytes: 10040
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)

int main()
{
  int h, w;
  cin >> h >> w;
  char a[h][w];
  rep(i, h) rep(j, w) cin >> a[i][j];

  bool row[h], col[w];
  memset(row, false, sizeof(row));
  memset(col, false, sizeof(col));

  rep(i, h)rep(j, w)
  {
    if (a[i][j] == '#')
    {
      row[i] = true;
      col[j] = true;
    }
  }
  rep(i, h) {
    if(row[i]){
      rep(j, w)if (col[j])cout << a[i][j];
      cout << endl;
    }
  }
      return 0;
}


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

int main(){
    char a;
    cin>>a;
    if(islower(a))cout<<'a'<<endl;
    else cout<<'A'<<endl;
    return 0;
}

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

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

    if(u == s){
        a--;
    }
    else{
        b--;
    }

    cout << a << " " << b << endl;
}

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

using ll = long long;

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    cout << n * (n-1) / 2 + m * (m-1) / 2 << '\n';
    return 0;
}

Measured memory_bytes: 256
def main():
    mod=10**9+7
    n=int(input())
    a = list(map(int,input().split()))
    a.sort()
    if n%2==0:
        check=[]
        for i in range(n//2):
            check.append(i*2+1)
            check.append(i*2+1)
        if a!=check:
            print(0)
            return
        ans=1
        for _ in range(n//2):
            ans=(ans*2)%mod
        print(ans)
    else:
        check=[0]
        for i in range(n//2):
            check.append((i+1)*2)
            check.append((i+1)*2)
        if a!=check:
            print(0)
            return
        ans=1
        for _ in range(n//2):
            ans=(ans*2)%mod
        print(ans)

if __name__ == "__main__":
    main()

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

int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  ll t = min(a, k);
  a -= t;
  k -= t;
  t = min(b, k);
  b -= t;
  cout << a << " " << b << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

#define N 500000

int a;


int left(int);
int right(int);
void maxHeapify(int*,int);
void buildMaxHeap(int*);

main(){

  int i,A[N];

  scanf("%d",&a);
  for(i = 1; i <= a; i++){
    scanf("%d",&A[i]);
  }
  buildMaxHeap(A);

  for(i = 1; i <= a; i++){
    printf(" %d",A[i]);
  }
    printf("\n");
  
  return 0;
}



int left(int i){
  return 2 * i;
}


int right(int i){
  return 2 * i +1;
}
void maxHeapify(int* A,int i){
  int x,l,r,largest;

  l = left(i);
  r = right(i);

  if(l <= a && A[l] > A[i]) largest = l;
  else largest = i;

  if(r <= a && A[r] > A[largest]) largest = r;

  if(largest != i){
    x = A[i];
    A[i] = A[largest];
    A[largest] = x;
    maxHeapify(A,largest);
  }
}

void buildMaxHeap(int* A){
  int i;
  for(i = a / 2;i >= 1; i--){
    maxHeapify(A,i);
  }
}

Measured memory_bytes: 2552
local n = io.read("*n")
local t = {}
for i = 1, n do t[i] = io.read("*n") end
local sum = 0
for i = 1, n do sum = sum + t[i] end
local m = io.read("*n")
for i = 1, m do
  local a, b = io.read("*n", "*n")
  print(sum - t[a] + b)
end


Measured memory_bytes: 504
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define FASTIO ios::sync_with_stdio(0); cin.tie(0);
#define show(x) cout << #x << " = " << x << "\n"
#define mem( a , b ) memset( a , b , sizeof a )
#define popcnt(x) __builtin_popcount(x)
#define all(x) x.begin() , x.end()
#define mod(x,m) ((x%m + m )%m)
#define SZ(a) (int)a.size()
#define ll  long long
#define ld  long double
#define vii vector  <ll>
#define dqi deque   <ll>
#define sii set     <ll>
#define vpi vector  <pii>
#define mii map     <ll,ll>
#define pii pair    <ll,ll>
#define pi  pair    <int,int>
#define pb  push_back
#define F   first
#define S   second
#define L   length()
#define OO  (ll)1e18
#define lSOne(x)(x&-x)
#define EPS 1e-20
using namespace std;
using namespace __gnu_pbds;
void ONLINE__JUDGE();

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;

pii swapii( pii pr ){ return { pr.S , pr.F }; }
ll binEXP( ll x , ll pw , ll MOD = LLONG_MAX );
int dx[] = {  0 ,  0 , -1 , +1 , -1 , +1 , -1 , +1 };
int dy[] = { -1 , +1 ,  0 ,  0 , -1 , +1 , +1 , -1 };

const ll MOD = 1e9 + 7;
const ll MAX = 100 + 9;

ll x; vector<ld> vec;
int main(){
    FASTIO //ONLINE__JUDGE();

    cin >> x; vec.resize(x);
    for ( ld& i : vec ) cin >> i , i = 1.0/i;

    ld sum = 0;
    for ( ld i : vec ) sum += i;
    cout << fixed << setprecision(15) << 1.0/sum;
    return 0;
}

void ONLINE__JUDGE()
{
    #ifndef ONLINE_JUDGE
    freopen( "inp.c"         , "r" , stdin  );
    //freopen( "OutPut.txt"   , "w" , stdout );
    #endif // ONLINE_JUDGE
}

ll binEXP( ll x , ll pw , ll MOD )
{ ll res=1; while(pw>0){ pw%2 ? res *= x : 0; x *= x; x%=MOD; pw /= 2; res%= MOD; } return res%=MOD; }


Measured memory_bytes: 256
fn gcd(a: i64,  b: i64) -> i64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a % b)
    }
}

#[test]
fn gcd_test() {
    assert_eq!(gcd(3, 5), 1);
    assert_eq!(gcd(8, 12), 4);
    assert_eq!(gcd(12, 12), 12);
}


fn main() {
    let mut k = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line);
        let s = line.split_whitespace().map(|a| a.parse().unwrap()).collect::<Vec<i64>>();
        gcd(s[0], s[1])
    };
    let mut count = 1;
    for i in 2i64..2000000 {
        if k % i == 0 {
            count += 1
        }
        while k % i == 0 {
            k /= i
        }
    }
    if k > 1 {
        count += 1
    }
    println!("{}", count);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;


const int MAX = 1e5;
struct edge{
    int v; // 次の頂点.
    int w; // 距離.
};
int dist[MAX]; // 距離を保存

// グラフを幅優先探索する.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @return: 特に無し.
void bfs(vector<vector<edge> > &G, int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    dist[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(dist[e.v] > 0)              continue;
            if(dist[e.v] == 0 && e.v != s) dist[e.v] = dist[u] + e.w, q.push(e.v);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    int N; // 頂点数 (0-index).
    scanf("%d", &N);
    vector<vector<edge> > graph(N);
    for(int i = 0; i < N - 1; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w); // from, to, cost.
        edge e1, e2;
        // u -> v
        e1.v = v, e1.w = w;
        graph[u].push_back(e1);
        // v -> u
        e2.v = u, e2.w = w;
        graph[v].push_back(e2);
    }
    
    // 2. 頂点を一つ固定して, そこから各頂点への距離を保存.
    // -> 頂点 0 から 最も遠い頂点 u を 選択.
    memset(dist, 0, sizeof(dist));
    bfs(graph, 0);
    int u = 0;
    int d = 0;
    for(int i = 0; i < N; i++) if(d < dist[i]) u = i, d = dist[i];
    
    // 3. 頂点 u から 各頂点への距離を保存.
    // -> 頂点 u から 最も遠い距離 を 探索.
    memset(dist, 0, sizeof(dist));
    bfs(graph, u);
    d = 0;
    for(int i = 0; i < N; i++) if(d < dist[i]) d = dist[i];

    // 4. 出力 ～ 後処理.
    printf("%d\n", d);
    return 0;
    
}



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

#define fastio                  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define input_output            freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 

#define ll                      long long
#define read1(x)                 cin>>x
#define read2(x,y)               cin>>x>>y
#define print(x)				cout<<x<<endl
#define pii                     pair<int, int>
#define pli                     pair<ll, int>
#define pil                     pair<int, ll>
#define pll                     pair<ll, ll>
#define vi                      vector<int>
#define vll                     vector<ll>
#define vb                      vector<bool>
#define vd                      vector<double>
#define vs                      vector<string>
#define ff                      first
#define ss                      second
#define pb                      push_back
#define ppb                     pop_back
#define pf                      push_front
#define ppf                     pop_front
#define vpii                    vector<pii>
#define umap                    unordered_map
#define uset                    unordered_set
#define clr(a,b)                memset(a,b,sizeof a)
#define all(ds)                 ds.begin(), ds.end()
#define rev(ds)                 ds.rbegin(), ds.rend()
#define asc(A)                  sort(A.begin(), A.end())
#define dsc(A)                  sort(A.begin(), A.end(), greater<int>())
#define gcd(x,y)                __gcd(x,y)
#define clr(a,b)                memset(a,b,sizeof a)
#define fr(i, n)                for(int i=0; i<n;++i)
#define fr1(i, n)               for(int i=1; i<=n; ++i)
#define rfr(i, n)               for(int i=n-1; i>=0; --i)
#define printVector(v)          for(int i= 0;i<v.size();i++) {cout<<v[i]<<" ";} cout<<endl;
#define precise(x)              cout<<fixed<<setprecision(x)
#define inf                     10000000000000

 

ll lcm(ll a, ll b) {return (a*b)/__gcd(a, b); }
ll power(ll x, ll y, ll m) { if(!y) return 1; ll p=power(x, y>>1, m)%m; p=p*p%m; return (y&1)?(x*p)%m:p;}
ll modInverse(ll a, ll m){ return power(a, m-2, m); }
bool isPrime(ll num){bool flag=true;for(ll i =2;i<=num/2;i++){if(num%i==0) {flag=false; break;} }return flag;}
ll sumofdigits(ll n){ll c=0;while(n>0){c++;n/=10;}return c;}
bool sortinrev(const pair<int,int>&a,const pair<int,int>&b) {return a.first > b.first; }
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) {return a.second < b.second; }

//const double PI= 2*acos(0.0);
const long long MOD= 1000000007;



void solve(){
    string s;cin>>s;
    ll ans = 0;
    fr(i,s.size())ans += (s[i]-'0');
    if(ans%9)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;


}
int main()
{
#ifndef ONLINE_JUDGE  
    input_output  
#else   
    fastio
#endif

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

    return 0;
}

Measured memory_bytes: 3752
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<numeric>
#include<iomanip>
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define ll long long

using namespace std;

//最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}


int main() {
	ll mod = 1e9 + 7; //1e9=1*10^9
	int n, m;
	cin >> n >> m;

	//階段に穴があればfalse, そうでなければtrue
	vector<bool>stair(n + 1, true);
	rep(i, m) {
		int a;
		cin >> a;
		stair[a] = false;
	}

	//dpテーブル
	//dp[i]はi段目にたどり着く方法の数
	//dp[i](i>=2)はdp[i-1]+dp[i-2]である
	vector<ll>dp(n + 1);
	dp[0] = 1;
	rep(i, n) {
		for (int j = i + 1; j <= min(n, i + 2); j++) {
			if (stair[j] == true) {
				dp[j] += dp[i];
				dp[j] %= mod;
			}
		}
	}

	cout << dp[n] << endl;

	return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main() {
    int N;

    cin >> N;

    cout << N*N*N << endl;

    return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
ll inf = 1e9;

int main() {
  while (true) {
    ll n, m;
    cin >> n >> m;
    if (!n && !m)
      break;

    vector<ll> sumh(1510);
    for (int i = 1; i <= n; i++) {
      ll h;
      cin >> h;
      sumh[i] = sumh[i - 1] + h;
    }
    vector<ll> sumsh(1500010);
    for (int i = 0; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
        sumsh.at(sumh[j] - sumh[i])++;
      }
    }

    vector<ll> sumw(1510);
    for (int i = 1; i <= m; i++) {
      ll w;
      cin >> w;
      sumw[i] = sumw[i - 1] + w;
    }
    vector<ll> sumsw(1500010);
    for (int i = 0; i <= m; i++) {
      for (int j = i + 1; j <= m; j++) {
        sumsw.at(sumw[j] - sumw[i])++;
      }
    }

    ll ans = 0;
    for (int i = 1; i <= 1500000; i++) {
      ans += sumsh[i] * sumsw[i];
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 26340
#include <stdio.h>

int main(void)
{
  int i, m, n, h[100001], a[100001], b[100001], c[100001] = {0}, result = 0;
  
  scanf("%d %d", &n, &m);

  
  for( i = 0; i < n; i++ ){
      scanf("%d ", &h[i]);
  }
  
  for( i = 0; i < m; i++ ){
      scanf("%d %d", &a[i], &b[i]);
  }
  
  for( i = 0; i < m; i++ ){
    if( h[a[i]-1] > h[b[i]-1] ){
        c[b[i]-1] = 1;
    } else if( h[a[i]-1] < h[b[i]-1] ){
        c[a[i]-1] = 1;
    } else {
        c[a[i]-1] = 1;
        c[b[i]-1] = 1;
    }
  }
  
  for( i = 0; i < n; i++ ){
      if( c[i] == 0 ){
          result++;
      }
  }
  printf("%d\n", result);
  return 0;
}

Measured memory_bytes: 3292
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, starter, n) for (int i = (starter); i < (int)(n); i++)

int main(){
    long A,B,tmp;
    cin >> A >> B;
    long x = A * B;
    if(A<B){
    tmp = A;
    A = B;
    B = tmp;
    }
    long r;
    r = A % B;

    while(r!=0){
        A = B;
        B = r;
        r = A % B;
    }
    cout << x/B << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int A = 0;
  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    int m = r - l + 1;
    A += m;
  }
  cout << A << endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
a, b = [], []
for i in range(m):
    a_, b_ = map(int, input().split()) 
    if a_ == 1:
        a.append(b_)
    if b_ == n:
        b.append(a_)
if len(set(a) & set(b)) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 21836
N,T=map(int,input().split())
AB=sorted([list(map(int,input().split())) for i in range(N)])
dp=[[0]*(T+3001) for i in range(N+1)]
for i in range(1,N+1):
    a,b=AB[i-1]
    for j in range(T+3001):
        dp[i][j]=dp[i-1][j]
        if 0<=j-a<T:
            dp[i][j]=max(dp[i][j],dp[i-1][j-a]+b)
print(max(dp[-1]))

Measured memory_bytes: 183640
#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)

int main() {
	ll N, Y; cin >> N >> Y;

	repe(i, 0, N) {
		repe(j, 0, N) {
			if (N >= i + j && 10000 * i + 5000 * j + 1000 * (N - i - j) == Y) {
				cout << i << " " << j << " " << (N - i - j) << endl;;
				return 0;
			}
		}
	}

	cout << -1 << " " << -1 << " " << -1 << endl;;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<stdlib.h>

typedef long long int lli;
using namespace std;

void yespr(){cout<<"Yes\n"<<endl;}
void nopr(){cout<<"No\n"<<endl;}

int main(void){
    int n,m;
    int a[100000];

    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i];
        n-=a[i];
    }
    if(n<0){
        cout<<"-1"<<endl;
    }
    else{
        cout<<n<<endl;
    }
    return 0;
}

Measured memory_bytes: 3652
#define NDEBUG

#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <utility>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <tuple>
#include <set>
#include <map>

// [0, max)
#define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var))
// [min, max)
#define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var))
// [min, max)
#define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

// a < b < c
#define LTLT(a, b, c) (((a) < (b)) && ((b) < (c)))
// a <= b < c
#define LELT(a, b, c) (((a) <= (b)) && ((b) < (c)))
// a < b <= c
#define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c)))
// a <= b <= c
#define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c)))

#ifndef NDEBUG
#  define MASSERT(cond) m_assert(cond, __LINE__, #cond);
#else
#  define MASSERT(...)
#endif

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

using sc = signed char;
using si = signed int;
using sl = signed long long int;

using ld = long double;

void m_assert(const bool& cond, const sl& line, const char *condstr) {
  if (!cond) {
    cerr << "Assertion Failed: " << condstr << " at line " << line << endl;
    exit(1);
  }
}

static sl N, K;
static vector<sl> Ai;
static vector<sl> Si;

void solve(void) {
  sl res = 0;
  map<sl, sl> m;
  FOR0(j, N + 1) {
    if (j - K >= 0) {
      m[Si[j - K]]--;
    }
    res += m[Si[j]];
    m[Si[j]]++;
  }
  cout << res << endl;
}

int main(void) {
  cin >> N >> K;
  Ai.resize(N);
  Si.resize(N + 1);
  Si[0] = 0;
  FOR0(i, N) {
    cin >> Ai[i];
    Si[i + 1] = (Si[i] + Ai[i] - 1) % K;
  }
  solve();
  return 0;
}

Measured memory_bytes: 15872