akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)1e9 + 7;


//---------------------------------------------------------------
template<int MOD> struct ModInt { int x;
    explicit operator bool() const { return !!x; }
    ModInt(int v = 0) : x(v % MOD) { if (x < 0) x += MOD; }
    ModInt(long long v) : x(v % MOD) { if (x < 0) x += MOD; }
    ModInt &operator+=(const ModInt &r) { if ((x += r.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(const ModInt &r) { if ((x += MOD - r.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(const ModInt &r) { x = 1LL * x * r.x % MOD; return *this; }
    ModInt &operator/=(const ModInt &r) { return *this *= r.inverse(); }
    ModInt operator-() const { return x ? ModInt(MOD - x) : ModInt(x); }
    ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
    ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
    ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
    ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
        return ModInt(u); } // x.pow(MOD-2)
    ModInt pow(long long k) const { ModInt r(1), a(x);
        while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
    bool operator==(const ModInt r) const { return x == r.x; }
    bool operator!=(const ModInt r) const { return x != r.x; }
    bool operator< (const ModInt r) const { return x <  r.x; }
    friend ostream& operator<<(ostream &os, const ModInt<MOD>& a) { return os << a.x; }
    friend istream& operator>>(istream &is, ModInt<MOD>& a) { return is >> a.x; }
};
template<typename T, int SZ> struct Comb { vector<T> _fac, _ifac, _inv;
    Comb() : _fac(SZ + 1), _ifac(SZ + 1), _inv(SZ + 1) {
        _fac[0] = _ifac[SZ] = _inv[0] = 1;
        for (int i = 1; i <= SZ; i++) _fac[i] = _fac[i - 1] * i;
        _ifac[SZ] /= _fac[SZ];
        for (int i = SZ - 1; i >= 0; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        for (int i = 1; i <= SZ; i++) _inv[i] = _ifac[i] * _fac[i - 1]; }
    T inv(int n) { return n < 0 ? T(0) : _inv[n]; }
    T fac(int n) { return n < 0 ? T(0) : _fac[n]; }
    T ifac(int n) { return n < 0 ? T(0) : _ifac[n]; }
    T P(int a, int b) { return (b < 0 || a < b) ? T(0) : _fac[a] * _ifac[a - b]; }
    T C(int a, int b) { return b < 0 ? T(0) : P(a, b) * _ifac[b]; }
    T H(int n, int k) { if (n < 0 || k < 0) return T(0);
        return k == 0 ? T(0) : C(n + k - 1, k); }
};
typedef ModInt<MOD> mint;
//---------------------------------------------------------------


int main() {
    Comb<mint, 250000> com;
    int H, W, K; cin >> H >> W >> K;

    mint sum = 0;
    for (int _: {0, 1}) {
        for (int d = 1; d < H; d++) {
            sum += mint(d) * mint(H - d) * mint(W).pow(2);
        }
        swap(H, W);
    }
    sum *= com.C(H * W - 2, K - 2);
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3200
// D - Powerful Discount Tickets
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,n) for(int i=0;i<(n);i++)

int main(){
	int N,M; cin>>N>>M;

	priority_queue<int> A;
	rp(i, N){
		int a; cin>>a;
		A.push(a);
	}

	rp(i,M){
		int a = A.top(); A.pop();
		A.push(a/2);
	}

	ll ans = 0;
	rp(i,N){ ans += A.top(); A.pop(); }
	cout<< ans <<endl;
}

Measured memory_bytes: 892
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INTINF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = INTINF;
	int tmp;
	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	REP(i, n) cin >> h[i];
	sort(h.begin(), h.end());
	REP(i, n-k+1) ans = min(ans, h[i+k-1] - h[i]);
	cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<sstream>
using namespace std;
int s2d(string buf){
  istringstream iss(buf);
  double x;iss >> x;
  return x;
}
int main(){
  string buf;
  while(cin>>buf){
    int i;
    for(i=0;i<buf.size();i++) if(buf[i]==',') buf[i]=' ';
    stringstream ss(buf);
    double d[12];
    for(i=0;i<12;i++){
      ss >> buf;
      d[i]=s2d(buf);
      //cout << i << ":" << d[i] << endl;
    }
    double p=0;
    for(i=0;i<10;i++) p+=d[i];
    p*=d[10]/(d[10]+d[11]);
    //cout << p << endl;
    int o=0,k=0;
    for(i=0;i<10;i++){
      if(p<=k+d[i]){
	o=i+1;
	break;
      }
      k+=d[i];
    }
    cout << o << endl;
  }
  return 0;
}

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

int main()
{
    int n;
    cin>>n;
    long long A[n+1],B[n];
    for(int i = 0; i <= n; i++){
        cin>>A[i];
    }
    for(int i = 0; i < n; i++)cin>>B[i];
    long long ans = 0;
    for(int i = n-1; i >= 0; i--){
        ans += min(A[i+1],B[i]);
        B[i] -= min(A[i+1],B[i]);
        ans += min(B[i], A[i]);
        A[i] -= min(B[i], A[i]);
    }
    cout<<ans;
    return 0;
}


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

int main(){
	char s[10];
	scanf("%s",s);
	bool flag=false;
	for(int i=1;s[i]!='\0';i++){
		if(s[i]=='C'&&s[i-1]=='A')
			flag=true;
	}
	if(flag)
		puts("Yes");
	else
		puts("No");
	return 0;
}

Measured memory_bytes: 256
import sys
from functools import reduce

(row, column) = sys.stdin.readline().rstrip('\r\n').split(' ')
row = int(row)
column = int(column)

a = []

for ii in range(row):
  a.append([int(x) for x in input().rstrip('\r\n').split(' ')])

for ii in range(len(a)):
  for aa in a[ii]:
    print(str(aa) + ' ', end='')
  print(reduce(lambda sum, x: sum + x, a[ii]))

total = 0
for ii in range(column):
  sum = 0
  for jj in range(row):
    sum += a[jj][ii]
    total += a[jj][ii]
  print(str(sum) + ' ', end='')
print(total)



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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    cout << ((1000 > n) ? "ABC" : "ABD") << endl;
    return 0;
}


Measured memory_bytes: 256
/**
 *
 * AtCoder Regular Contest 058 - Problem C: Iroha's Obsession
 *
 * Find the minimum positive m >= N where m not contains digits D1, D2, ..., DN.
 *
 * Brute force solution: precompute all values that not contains D1, D2, ..., DN an binary
 * search the answer.
 */
#include <iostream>

#include <set>
#include <vector>
#include <algorithm>

using namespace std;


// Ds = {D1, D2, ..., DN}
bool accept(int n, const set<int>& Ds)
{
    while (n)
    {
        auto d = n % 10;
        n /= 10;

        if (Ds.count(d))
            return false;
    }

    return true;
}

vector<int> filter_all(int MAX, const set<int>& Ds)
{
    vector<int> valid;

    for (int n = 0; n < MAX; ++n)
        if (accept(n, Ds))
            valid.push_back(n);

    return valid;
}

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

    int N, K;
    cin >> N >> K;

    set<int> Ds;

    for (int k = 0; k < K; ++k)
    {
        int n;
        cin >> n;

        Ds.insert(n);
    }

    auto valid = filter_all(100000, Ds);

    auto m = *lower_bound(valid.begin(), valid.end(), N); 

    cout << m << endl;

    return 0;
}


Measured memory_bytes: 892
#include<iostream>
using namespace std;
long long mod=1e9+7;
long long qpow(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return (ans+mod)%mod;
}
long long po[200005];
int main()
{
	long long n,a,b,ans,sum1=1,sum2=1;
	cin>>n>>a>>b;
	ans=qpow(2,n);
	for(int i=1;i<=200000;i++) po[i]=qpow(i,mod-2);
	for(int i=1;i<=a;i++)
	{
		sum1*=(n-i+1);
		sum1%=mod;
		sum1*=po[i];
		sum1%=mod;
	}
	for(int i=1;i<=b;i++)
	{
		sum2*=(n-i+1);
		sum2%=mod;
		sum2*=po[i];
		sum2%=mod;
	}
	cout<<((ans-sum1-1-sum2)%mod+mod)%mod<<endl;
	return 0;
}

Measured memory_bytes: 1920
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<math.h>
#include<functional>
#include<bitset>
#include<cassert>
using namespace std;
using lint = long long;
using ld = long double;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(lint i=n;i<(int)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	lint n;
	cin >> n;
	lint ans = 0;
	for(lint i = 1; i * i <= n; i++) {
		if(n - i >= 0 && (n - i) % i == 0) {
			lint m = (n - i) / i;
			if(i < m) ans += m;
		}
	}
	cout << ans << endl;
	return 0;
}
/* --------------------------------------- */


Measured memory_bytes: 256
import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)


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

int main() {
  int n, m;
  cin >> n >> m;
  
  vector<int> a(n), b(n), c(m), d(m);
  for (int i=0; i<n; i++){
    cin >> a.at(i) >> b.at(i);
  }
  for (int i=0; i<m; i++){
    cin >> c.at(i) >> d.at(i);
  }
  
  for (int i=0; i<n; i++){
    int md = pow(10, 9);
    int num;
    for (int j=0; j<m; j++){
      if(md > abs(a.at(i)-c.at(j))+abs(b.at(i)-d.at(j))){
        num = j;
        md =abs(a.at(i)-c.at(j))+abs(b.at(i)-d.at(j));
      }
    }
    cout << num + 1 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
int main(void){
    // Your code here!
    double N,T,A,ans;
    
    cin >> N >> T >>A;
    
    vector<double> vec(N);
    for(int i=0;i<N;i++) cin >> vec[i];
    
    for(int i =0;i<N;i++){
       vec[i] = T - 0.006*vec[i];
       
   }
   double min;
   if(A-vec[0]>0){
       min = A-vec[0];
   }else{
       min = -1*(A-vec[0]);
   }
   ans=0;
   for(int i=1;i<N;i++){
       if(A-vec[i]>0){
           if(min > A-vec[i]){
               min = A-vec[i];
               ans=i;
           }
       }else{
           if(min>-1*(A-vec[i])){
               min = -1*(A-vec[i]);
               ans = i;
           }
       }
   }
   cout << ans+1 << endl;
   
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>


using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    vector<ll> ans(n + 1,0);
    for (ll i = 1; i < n + 1; i++)
    {
        cin >> a[i];
    }
    ll cnt;
    for (ll i = n; i > 0; i--)
    {
        cnt = 0;
        for (ll j = i; j <= n; j += i)
        {
            cnt += ans[j];
        }
        if ((cnt + a[i]) % 2 == 1)
        {
            ans[i] = 1;
        }
    }
    vector<ll> b;
    for (ll i = 0; i < n; i++)
    {
        if(ans[i+1]==1)
        {
            b.push_back(i + 1);
        }
    }
    
    cout << b.size() << endl;
    for (ll i : b)
    {
        cout << i << " ";
    }
    cout << "\n";
    return 0;
}

Measured memory_bytes: 4980
import sys
import time
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    X = int(readline())
    top = X //100
    bottom = (X%100+4)//5
    if top>=bottom:
        print(1)
    else:
        print(0)

if __name__ == '__main__':
    main()

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

const int MAXN = 100000 + 10;

int n;
vector<int> G[MAXN];

int distx[MAXN];

vector<int> stk;

void dfs1(int x, int dest) {
    stk.push_back(x);
    cerr << x << "\n";
    if (x == dest) {
        int p = (stk.size() - 1) / 2;
        int w = stk[p];
        int v = stk[p+1];
        for (int i = 0; i < G[w].size(); i++) {
            if (G[w][i] == v) {
                swap(G[w][i], G[w].back());
                G[w].pop_back();
            }
        }
        for (int i = 0; i < G[v].size(); i++) {
            if (G[v][i] == w) {
                swap(G[v][i], G[v].back());
                G[v].pop_back();
            }
        }
        return;
    }
    for (auto y: G[x]) {
        if (distx[y] > n) {
            distx[y] = distx[x] + 1;
            dfs1(y, dest);
        }
    }
    stk.pop_back();
}

int vis[MAXN];
int cnt;
void dfs2(int x) {

    vis[x] = true;
    cnt++;
    for (auto y: G[x]) {
        if (!vis[y]) {
            dfs2(y);
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int x,y;
        cin >> x >> y;
        x--;y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 0; i < n; i++) distx[i] = n+100;
    distx[0] = 0;
    dfs1(0, n-1);

    cnt = 0;
    dfs2(0);
    int cntx = cnt;
    cnt = 0;
    dfs2(n-1);
    int cnty = cnt;

    if (cntx <= cnty) cout << "Snuke\n";
    else cout << "Fennec\n";

    return 0;
}


Measured memory_bytes: 12916
s=input()
kisuu=list("RUD")
guusuu=list("LUD")
ans=0
for i in s[::2]:
    if i not in kisuu:
        ans+=1
for i in s[1::2]:
    if i not in guusuu:
        ans+=1
if ans==0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <stdio.h>

int main(){

    int a=0,b=0;

    scanf("%d %d",&a,&b);

if (a<b)
    printf("a < b\n");
else if (a>b)
    printf("a > b\n");
else if (a==b)
    printf("a == b\n");
    else
        printf("none");

    return 0;

}

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

int main()
{
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
// #endif
    int n ;
    cin>>n;
    double arr[n];
    for(int i = 0 ;i<n ;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    double sum = 0.0;
    for(int i=0 ;i<n;i++)
    {
        if(i==n-1)
        {
            break;
        }
        sum=(arr[i]+arr[i+1])/2;
        arr[i+1]=sum;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int A,B;
int getX(int x){
  double a;
  a=x*100.0/(100+A);
  int b;
  b=ceil(a);
  if((int)(b*(100.0+A)/100) != x)return -1;
     double c=b*(100.0+B)/100;
     return (int)c;
}
int main(){
	int c;
	while(cin>>A>>B>>c,A){
		int ans=0;
		for(int i=1;i<c;i++){
			int data=getX(i)+getX(c-i);
			if(data>ans){
				ans=data;
			}
		}
		cout<<ans<<endl;
	}
}

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

int main()
{
    int N; cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];

    int ans = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    if (N % 2 == 0) {
        ans = B[N/2] + B[N/2-1] - (A[N/2] + A[N/2-1]) + 1;
    } else {
        ans = B[N/2] - A[N/2] + 1;
    }

    cout << ans << endl;
}


Measured memory_bytes: 4844
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

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

bool msprime[300010];

void init(){
	fill(msprime, msprime+300010, false);
	rep(i, 300010){
		if((i%7 == 1) || (i%7 == 6)) msprime[i] = true;
	}
	msprime[1] = false;
	rep(i, 300010){
		if(msprime[i]){
			for(int j = i*2; j < 300010; j+=i){
				msprime[j] = false;
			}
		}
	}
}

int main(){
	init();

	while(1){
		int n;
		cin >> n;
		if(n == 1) break;
		cout << n << ':';
		for(int i = 2; i <= n; i++){
			if(msprime[i] && (n%i == 0)) cout << ' ' << i;
		}
		cout << endl;
	}
}

Measured memory_bytes: 1452
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

from collections import deque

N = int(inp())
graph = [[] for _ in range(N+1)]
nextEdege  = []

for _ in range(N-1):
  a, b = map(int, inp().split())
  graph[a].append(b)  
  nextEdege.append(b)
  
q = deque([1]) # 頂点1から幅優先探索
color = [0]*(N+1)
while q:
  v = q.popleft()
  c = 1
  for u in graph[v]:
    if c == color[v]:
      c += 1
    color[u] = c
    c += 1
    q.append(u)
    
print(max(color))    
for b in nextEdege:
  print(color[b])
  

  

Measured memory_bytes: 18676
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#define MP make_pair
#define fi first
#define se second 
#define pb push_back
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int INF=2e9+7;
const int N=(1<<18)+5;
pair<int,int> dp[N][2];
int f[N];int ans[N];
int P[30];int n;

void update(int i,int j){
	pair<int,int> now0,now1;
	int tmp=i;
	if(dp[i][0].fi<dp[j][0].fi)	swap(i,j);
	now0=dp[i][0];
	if(dp[j][0].se!=dp[i][0].se){
		if(dp[j][0].fi<dp[i][1].fi)	now1=dp[i][1];
		else now1=dp[j][0];
	}
	else{
		if(dp[j][1].fi<dp[i][1].fi)	now1=dp[i][1];
		else now1=dp[j][1];
	}
	dp[tmp][0]=now0;
	dp[tmp][1]=now1;
}

void FMT(int n){
	register int i,j,k;
	for(i=1;i<n;i<<=1){
		for(j=0;j<n;j+=(i<<1)){
			for(k=0;k<i;k++){
				update(i+j+k,j+k);
			}
		}
	}
}

void solve(int K){
	int ret=0;int now=0;int i;
	for(i=20;i>=0;i--){
		if(1<<i&K){
			ret=max(ret,f[now+(1<<i)-1]);
			now+=(1<<i);
		}
	}
	ret=max(ret,f[now]);
	ans[K]=ret;
}

int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	register int i;int x;
	P[0]=1;rep(i,1,20)	P[i]=1<<i;
	scanf("%d",&n);
	rep(i,0,(1<<n)-1){
		scanf("%d",&x);
		dp[i][0]=MP(x,i);
		dp[i][1]=MP(-INF,-1);
	}
	FMT(1<<n);
	rep(i,0,(1<<n)-1)	f[i]=dp[i][0].fi+dp[i][1].fi;
	solve(4);
	rep(i,1,(1<<n)-1)	solve(i);
	rep(i,1,(1<<n)-1)	printf("%d\n",ans[i]);
	return 0;
}


























Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;
 
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main(void)
{
    int n;
    cin >> n;
    vector<vector<ll>> act(n, vector<ll>(3));
    REP(i,n){
        REP(j,3){
            cin >> act[i][j];
        }
    }

    vector<vector<ll>> dp(n,vector<ll>(3,0));

    dp[0] = act[0];

    FOR(i,1,n){
        REP(j,dp[i].size()){
            REP(k,dp[i].size()){
                if(j == k){
                    continue;
                }
                dp[i][j] = max(dp[i][j], dp[i-1][k] + act[i][j]);
            }
        }
    }

    cout << *max_element(all(dp[n-1])) << endl;

    return 0;
}

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

int main(){
  int n;
  cin >> n;
  
  int a[n];
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  
  int push = 1, count = 1;
  while (count <= n){
    if (a[push - 1] == 2){
      cout << count << endl;
      return 0;
    }
    push = a[push - 1];
    count++;
  }
  cout << -1 << endl;
}

Measured memory_bytes: 640
#include<stdio.h>

char clas[3]={'A','B','C'};

int has100(int m,int e,int j){
  if((m==100)||(e==100)||(j==100)){
    return 1;
  }
  else{
    return 0;
  }
}

int ave3(int m,int e,int j){
  return (m+e+j)/3;
}

void prclass(int x){
  printf("%c\n",clas[x]);
}

void dvdstdnt(int n){
  if(n!=0){
    int m,e,j;
    scanf("%d %d %d",&m,&e,&j);
    if(has100(m,e,j)==1){
      prclass(0);
    }
    else if((m+e)/2>=90){
      prclass(0);
    }
    else{
      int av3=ave3(m,e,j);
      if(av3>=80){
	prclass(0);
      }
      else if(av3>=70){
	prclass(1);
      }
      else if((av3>=50)&&((m>=80)||(e>=80))){
	prclass(1);
      }
      else{
	prclass(2);
      }
    }
    dvdstdnt(n-1);
  }
}

void doit(){
  int n;
  scanf("%d",&n);
  if(n!=0){
    dvdstdnt(n);
    doit();
  }
}

int main(){
  doit();
  return 0;
}

Measured memory_bytes: 616
a=int(input())
b=int(input())
c=int(input())
x=int(input())
ans=0
for i in range(a+1):
    for j in range(b+1):
        for q in range(c+1):
            if 500*i+100*j+50*q==x:
                ans+=1
print(ans)
    


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

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

	if (S == "Sunny")
		cout << "Cloudy" << endl;
	else if(S == "Cloudy")
		cout << "Rainy" << endl;
	else
		cout << "Sunny" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=1010000;
int d[N],n,fa[N],fb[N],id[N],ori[N],pr[N];
VI sa[N],sb[N];
namespace euler {
	int type,n,m,edgenum,top,u,v;
	int vet[N],next[N],head[N],s[N],ru[N],cu[N],q[N],flag[N];
	void add(int u,int v,int id)
	{
		d[u]++;
		vet[++edgenum]=v;
		next[edgenum]=head[u];
		head[u]=edgenum;
		s[edgenum]=id;
		ru[v]++;cu[u]++;
	}
	void dfs(int u)
	{
		for (int e=head[u];e;e=head[u])
		{
			while (e&&flag[abs(s[e])]) e=next[e];
			head[u]=e;
			if (e)
			{
				flag[abs(s[e])]=1;
				dfs(vet[e]);
				q[++top]=s[e];
			}
		}
	}
	VI solve() {
		rep(i,1,edgenum+1) {
			if (!flag[abs(s[i])]) dfs(vet[i]);
		}
		return VI(q+1,q+top+1);
	}
}
int main() {
	scanf("%d",&n);
	rep(i,1,n+1) {
		scanf("%d",fa+i);
		if (fa[i]==-1) fa[i]++;
		sa[fa[i]].pb(i);
	}
	rep(i,1,n+1) {
		scanf("%d",fb+i);
		if (fb[i]==-1) fb[i]++;
		sb[fb[i]].pb(i);
	}
	rep(i,1,n+1) if (SZ(sa[i])%2!=SZ(sb[i])%2) {
		puts("IMPOSSIBLE");
		return 0;
	}
	int nn=n;
	rep(i,0,n+1) if (SZ(sa[i])%2==1) {
		++nn; fa[nn]=fb[nn]=i;
		sa[i].pb(nn); sb[i].pb(nn);
		pr[i]=nn;
	}
	int m=0;
	rep(i,1,nn+1) {
		euler::add(fa[i],fb[i]+nn+1,++m);
		euler::add(fb[i]+nn+1,fa[i],-m);
	}
	rep(i,0,2*(nn+1)) assert(d[i]%2==0);
	VI c=euler::solve();
	rep(i,0,SZ(c)) {
		ori[abs(c[i])]=c[i]>0?1:-1;
	}
	puts("POSSIBLE");
	rep(i,1,n+1) if (pr[i]==0) printf("%d ",ori[i]); else printf("%d ",ori[i]+ori[pr[i]]);
	puts("");
}


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

long long f(vector<pair<long long, long long>> &x)
{
    priority_queue<long long, vector<long long>, greater<long long>> candidates;
    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
    for (pair<long long, long long> p : x)
    {
        q.push(p);
    }
    long long current = 1;
    while (!q.empty() && size_t(current) <= x.size())
    {
        long long index = q.top().first;
        if (index < current)
        {
            q.pop();
            continue;
        }
        if (index > current)
        {
            while (size_t(current) < candidates.size())
            {
                candidates.pop();
            }
            current = index;
        }
        else
        {
            long long diff = q.top().second;
            q.pop();
            candidates.push(diff);
        }
    }
    while (size_t(current) < candidates.size())
    {
        candidates.pop();
    }
    while (!q.empty())
    {
        candidates.push(q.top().second);
        q.pop();
    }

    long long ret = 0;
    while (!candidates.empty())
    {
        ret += candidates.top();
        candidates.pop();
    }
    return ret;
}

void solve()
{
    long long N;
    cin >> N;
    vector<long long> K(N);
    vector<long long> R(N);
    vector<long long> L(N);
    vector<pair<long long, long long>> right;
    vector<pair<long long, long long>> left;
    long long ans = 0;
    for (long long n = 0; n < N; n++)
    {
        cin >> K[n] >> R[n] >> L[n];
        if (R[n] > L[n])
        {
            right.push_back(make_pair(K[n], R[n] - L[n]));
        }
        else if (R[n] < L[n])
        {
            left.push_back(make_pair(N - K[n], L[n] - R[n]));
        }
        ans += min(R[n], L[n]);
    }

    ans += f(right);
    ans += f(left);
    cout << ans << endl;
}

int main()
{
    long long T;
    cin >> T;
    for (long long t = 0; t < T; t++)
    {
        solve();
    }
}


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

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

    int64_t ans = 1;
    vector<int64_t> d(n + 1, 1);
    for (auto i = 2; i <= n; i++) {
        for (auto j = i; j <= n; j += i) d[j]++;
    }
    for (auto i = 2; i <= n; i++) ans += d[i] * i;

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 81348
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rep2(i,n) for(int i=1; i<=(n); ++i)
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(),(x).end())
#define Sort2(x) sort((x).begin(),(x).end(), greater<int>())
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main()
{
    int h,w; cin >> h >> w;
    int hw = h*w;
    char maze[h][w];
    rep(i, h) rep(j, w) cin >> maze[i][j];
    int d[h][w];
    int INF = 1000000;
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    int ans = 0;

    rep(i,h) rep(j,w){
//        if(i!=0 || j!=0) continue;
        int sx=i, sy=j;
        if(maze[sx][sy]=='#') continue;
        rep(i,h) rep(j,w) d[i][j]=INF;
        int mx_d = 0;
        queue<P> que;
        que.push(P(sx,sy));
        d[sx][sy] = 0;

        while(que.size()){
            P p = que.front(); que.pop();
            rep(i,4){
                int nx = p.first + dy[i];
                int ny = p.second + dx[i];
                if(0<=nx && nx<h && 0<=ny && ny<w && maze[nx][ny]=='.' && d[nx][ny]==INF){
                    que.push(P(nx,ny));
                    d[nx][ny] = d[p.first][p.second] + 1;
                    mx_d = max(mx_d, d[nx][ny]);
                }
            }
        }
        ans = max(ans, mx_d);
//        cout << ans << endl;
        // rep(i,h){
        //     rep(j,w){
        //         if(d[i][j]==INF) cout << '#';
        //         else cout << d[i][j];
        //     }
        //     cout << endl;
        // }
    }
    cout << ans << endl;
}

/*
Ctrl+@ でコンソールを開け、以下で実行。
g++ d.cpp
./a.out

サンプルのダウンロードは oj d URL
テストは oj t
*/

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;
public class Hello
{
    public static void Main()
    {
        int M = NextInt();
        int K = NextInt();
        int m = (int)Math.Pow(2, M);
        if (K == 0)
        {
            for (int i = 0; i < m; i++)
                Console.Write(i + " " + i + " ");
            Console.WriteLine();
            return;
        }
        else if (K < m)
        {
            //Kを中心に構築
            //最後にKを置いても大丈夫かどうか
            int x = 0;
            for (int i = 0; i < m; i++)
                if(i != K)
                    x ^= i;
            if (x == K)
            {
                for (int i = 0; i < m; i++)
                    if (i != K)
                        Console.Write(i + " ");
                Console.Write(K + " ");
                for (int i = m - 1; i >= 0; i--)
                    if (i != K)
                        Console.Write(i + " ");
                Console.WriteLine(K);
                return;
            }
        }
        Console.WriteLine(-1);
    }
}

public class Input
{
    private static Queue<string> queue = new Queue<string>();
    private static void Confirm() { if (queue.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) queue.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(queue.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(queue.Dequeue()); }
    public static string NextString() { Confirm(); return queue.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(queue.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 16956
#include<stdio.h>

int main(){
	
	int N, R;
	scanf("%d %d", &N, &R);
	if (N < 10)
	{
		printf("%d\n", (R + (100*(10 - N))));
	}
	else if (N >= 10)
	{
		printf("%d\n", R);
	}
	
	return 0;
}

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

int main(){
	int n,k;
	cin>>n>>k;
	double q,m,ans;
	vector<double> a(300000);
	for(int i=0;i<n;i++){
		cin>>q;
		a[i]=(q+1)/2;
	}
	for(int i=0;i<k;i++){
		m+=a[i];
	}
	ans=m;
	for(int i=0;i<n-k;i++){
		m=m-a[i]+a[i+k];
		if(ans<m){
			ans=m;
		}
	}
	cout<<fixed<<setprecision(1);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 2560
import collections

n = int(input())
inp = list(map(int, input().split()))

odd = []
even = []

for i in range(n):
   if i % 2 == 0:
       odd.append(inp[i])
   else:
       even.append(inp[i])

# odd.sort()
# even.sort()

o_c = collections.Counter(odd)
o_e = collections.Counter(even)

o_most = o_c.most_common()
e_most = o_e.most_common()

if len(o_most) == len(e_most) == 1:
   if o_most[0][0] != e_most[0][0]:
       ans = 0
   else:
       ans = min(o_most[0][1], e_most[0][1])

else:
   if o_most[0][0] != e_most[0][0]:
       # odd
       if len(o_most) == 1:
           o_ans = 0
       else:
           o_ans = 0
           for i in range(len(o_most)-1):
               o_ans += o_most[i+1][1]

       # even
       if len(e_most) == 1:
           e_ans = 0
       else:
           e_ans = 0
           for i in range(len(e_most)-1):
               e_ans += e_most[i+1][1]
       # judge
       ans = o_ans + e_ans

   else:
       #最頻値が同じだった場合の処理が必要
       
       o_total=0
       for i in o_most:
       	o_total += i[1]
       
       e_total=0
       for i in e_most:
       	e_total+=i[1]
       
       aa=e_total-e_most[1][1]+o_total-o_most[0][1]
       bb=o_total-o_most[1][1]+e_total-e_most[0][1]
       ans = min(aa,bb)
       
       
       	



print(ans)


Measured memory_bytes: 23776
#include<bits/stdc++.h>
#include<vector>
#include<cmath>
#include<string>
#include<stack>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
const ll m = (1e+9) + 7;
int main() {
	int n, m;
	static ll ans;
	vector<pair<int, int>> p;
	cin >> n >> m;
	priority_queue<int> que;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		p.push_back(make_pair(a, b));
	}
	sort(p.begin(), p.end(),greater<pair<int,int>>());
	for (int day = 1; day <= m; ++day) {
		while (!p.empty() && p.back().first == day) {
			que.push(p.back().second);
			p.pop_back();
		}
		if (!que.empty()) {
			ans += que.top();
			que.pop();
		}
	}
	cout<<endl;
	cout << ans << endl;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n,cnt=0,ans=0,a,b,c,cmp,data,m,h,w,x,y,xcmp,ycmp,sum=0;

string s;

vector<int> z;

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

       cin >> a >> b >> c;
       if(Abs(a,b)>Abs(a,c)){
           Cout("B");
       }
       else{
           Cout("A");
       }
return 0;
}


Measured memory_bytes: 256
#include<stdio.h>



int main(){
	
	
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if(b-a==c-b){
		
		
		printf("YES\n");
		
		
	}else{
		
		printf("NO\n");
	}
	
	
	
	
	return 0;
}


Measured memory_bytes: 128
S = input()

s1 = int(S[:2])
s2 = int(S[2:])

#print(s1, s2)

if 1 <= s1 <= 12:
	if 1 <= s2 <= 12:
		print("AMBIGUOUS")
	else:
		print("MMYY")
	exit()

if 1 <= s2 <= 12:
	if 1 <= s1 <= 12:
		print("AMBIGUOUS")
	else:
		print("YYMM")
	exit()

print("NA")


Measured memory_bytes: 2940
#include<cstdio>
using namespace std;
const int d[19]={1,2,4,8,16,32,64,128,256,512,1024,
2048,4096,8192,16384,32768,65536,131072,262144};
int f[262145],g[262145],c[262145],t;
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=0;i<d[n];i++) scanf("%d",&c[i]),f[i]=i;
	g[0]=262144;
	for (int i=1;i<d[n];i++)
	{
		for (int j=0;j<n;j++)
		{
			if (!(i&(1<<j))) continue;
			if (c[f[i]]<c[f[i-(1<<j)]])
			{
				g[i]=f[i];
				f[i]=f[i-(1<<j)];
			}
			else if (f[i]!=f[i-(1<<j)] && c[g[i]]<c[f[i-(1<<j)]]) g[i]=f[i-(1<<j)];
			if (c[g[i]]<c[g[i-(1<<j)]]) g[i]=g[i-(1<<j)];
		}
		if (c[f[i]]+c[g[i]]>c[f[t]]+c[g[t]]) t=i;
		printf("%d\n",c[f[t]]+c[g[t]]);
	}
	return 0;
}

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

#include <math.h>
#include <stdlib.h>


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

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; }

const ll MOD = 1000000007;
const ll nMax = 10000;

long long fact[nMax];  // Array of Factorial
long long invFact[nMax]; // Array of Factorial of Inverse Elements
long long inv[nMax]; // Array of Inverse Elements

void calcFact(){
    fact[0] = 1; fact[1] = 1;
    invFact[0] = 1; invFact[1] = 1;
    inv[1] = 1;     //1に対する逆元は1
    
    for(int i = 2; i < nMax; i++){
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = (- inv[MOD % i] * (MOD/i) ) % MOD + MOD;
        invFact[i] = invFact[i-1] * inv[i] % MOD;
    }   
}
    
long long calcComb(long long _n, long long _k){
    if (_n < 0 || _k < 0) return 0;
    if (_n < _k) return 0;
    return fact[_n] * (invFact[_n-_k] * invFact[_k] % MOD) % MOD;
}


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll n, k; cin >> n >> k;
    ll r = n-k;

    calcFact();

    for(int i = 1; i <= k; i++){
        ll bp = calcComb(k-1, i-1);
        bp %= MOD;

        ll rp = 0;
        for (ll j = i-1; j < i+2; j++){
            if(r == 0 && j == 0) rp = 1;
            if(j == 0) continue;
            if(r >= j){
                rp += calcComb(r-1, j-1);
                if(j == i) rp += calcComb(r-1, j-1);
                rp %= MOD;
            }
        }
        ll ans = bp * rp;
        ans %= MOD;
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <time.h>

#include <string>

struct Node {
    int player;
    std::vector<int> children;
    int height;
    int rank;
};

const int MAX_N = 100050;
int N;
int a[MAX_N];

int win_num[MAX_N] = {};

Node tree[MAX_N * 2];
int node_of_player[MAX_N];

void dfs_set_rank(int node, int rank) {
    tree[node].rank = rank;

    for (auto c : tree[node].children) {
        dfs_set_rank(c, rank + 1);
    }
}

int main(int argc, char **argv) {
    std::cin >> N;

    a[1] = 0;
    for (int i = 2; i <= N; i++) {
        std::cin >> a[i];
    }

    for (int i = 2; i <= N; i++) {
        tree[a[i]].children.push_back(i);
    }

    dfs_set_rank(1, 0);

    std::vector<std::pair<int, int>> node_rank_vec;

    for (int i = 1; i <= N; i++) {
        node_rank_vec.push_back(std::pair<int, int>({i, tree[i].rank}));
    }

    std::sort(node_rank_vec.begin(), node_rank_vec.end(),
        [](const std::pair<int, int>& a, const std::pair<int, int>& b) { return a.second > b.second; }
    );

    for (auto p : node_rank_vec) {
        int node = p.first;
        int tmp = 0;
        std::vector<int> child_height;
        for (int c : tree[node].children) {
            child_height.push_back(tree[c].height);
        }
        std::sort(child_height.begin(), child_height.end());
        for (int h : child_height) {
            tmp = std::max(tmp, h) + 1;
        }
        tree[node].height = tmp;

        //std::cout << "check:" << node << " " << tmp << std::endl;
    }

    std::cout << tree[1].height << std::endl;

    return 0;
}


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

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

typedef long long ll;

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

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

    // input
    ll N;
    cin >> N;
    // vector<ll> vec(N);
    // REP(i, N) cin >> vec[i];
    
    // calculation
    if (N == 25) cout << "Christmas" << "\n";
    else if (N == 24) cout << "Christmas Eve" << "\n";
    else if (N == 23) cout << "Christmas Eve Eve" << "\n";
    else if (N == 22) cout << "Christmas Eve Eve Eve" << "\n";
    
    
    
    return 0;
}


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

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) &= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double PI = (double)acos(-1);
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  string s;
  cin >> s;

  int g = 0, p = 0, win = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'g') {
      if (p + 1 <= g) {
        win++;
        p++;
      } else {
        g++;
      }
    } else {
      if (p + 1 <= g) {
        p++;
      } else {
        win--;
        g++;
      }
    }
  }

  cout << win << endl;
  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<math.h>



struct Point{
  double x;
  double y;
};

void gohho(int d,struct Point p1,struct Point p2);
struct Point s,t,u;
double k;

int main(){
  struct Point p1,p2;
  int n;
  scanf("%d",&n);
  p1.x =0;
  p1.y = 0;
  p2.x = 100;
  p2.y = 0;

  printf("%.8f %.8f\n",p1.x,p1.y);
  gohho(n,p1,p2);
  printf("%.8f %.8f\n",p2.x,p2.y);
  return 0;
}



void gohho(int d,struct Point p1, struct Point p2){
  struct Point s,t,u;
  double k;

  if(d == 0)return;

  k = M_PI*60.0/180.0;

  s.x = (2.0 * p1.x + 1.0 * p2.x) /3.0;
  s.y = (2.0 * p1.y +1.0 * p2.y)/3.0;
  t.x = (1.0 * p1.x + 2.0 * p2.x)/3.0;
  t.y = (1.0 * p1.y +2.0 * p2.y)/3.0;
  u.x = (t.x - s.x) * cos(k) - (t.y - s.y) *sin(k) +s.x;
  u.y = (t.x - s.x) * sin(k) + (t.y - s.y) *cos(k) +s.y;

  gohho(d-1,p1,s);
  printf("%.8f %.8f\n",s.x,s.y);
  gohho(d-1,s,u);
  printf("%.8f %.8f\n",u.x, u.y);
  gohho(d - 1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  gohho(d-1,t,p2);
}



Measured memory_bytes: 2028
n=int(input())
a=[int(i) for i in input().split()]
a.sort()

ans = 0
cnt = 1

if n ==1:
    if a[0] == 1: 
        print(0)
        exit()
    else:
        print(1)
        exit()
 

for i in range(n-1):
    if a[i] == a[i+1]:cnt+=1
    else:
        if cnt < a[i]: ans += cnt
        elif cnt > a[i]: ans += cnt-a[i]
        cnt = 1
    if i+1 == n-1:
        if cnt < a[i]: ans += cnt
        elif cnt > a[i]: ans += cnt-a[i]
print(ans)

Measured memory_bytes: 63984
N, K = map(int, input().split())
mod = 10**9+7
counts = 0
for i in range(K, N+1+1):
    mins = 0.5*i*(i-1)
    maxs = N*i - 0.5*i*(i-1)
    counts += int((maxs - mins) + 1)
print(counts % mod)

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

int lex_smaller(char* s1, char* s2)
{
	int i;
	for (i = 0; s1[i] != 0 && s2[i] != 0; i++) {
		if (s1[i] < s2[i]) return 1;
		else if (s1[i] > s2[i]) return -1;
	}
	if (s1[i] == s2[i]) return 0;
	else if (s1[i] == 0) return 1;
	else return -1;
}

void push(char* s, char** heap, int* n)
{
	int i = *n;
	char *tmp;
	heap[(*n)++] = s;
	while (1) {
		if (i == 0) break;
		else if (lex_smaller(heap[i], heap[(i - 1) / 2]) == 1) {
			tmp = heap[(i - 1) / 2];
			heap[(i - 1) / 2] = heap[i];
			heap[i] = tmp;
			i = (i - 1) / 2;
		} else break;
	}
}

char* pop(char** heap, int* n)
{
	int i = 0, j;
	char *tmp, *output = heap[0];
	heap[0] = heap[--(*n)];
	while (1) {
		if (i * 2 + 1 >= *n) break;
		else if (i * 2 + 2 >= *n) j = i * 2 + 1;
		else if (lex_smaller(heap[i * 2 + 1], heap[i * 2 + 2]) == 1) j = i * 2 + 1;
		else j = i * 2 + 2;
		if (lex_smaller(heap[j], heap[i]) == 1) {
			tmp = heap[j];
			heap[j] = heap[i];
			heap[i] = tmp;
			i = j;
		} else break;
	}
	return output;
}

int main()
{
	int i, N, P[101];
	char S[101][11];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%s %d", S[i], &(P[i]));
	
	int j, n, city[101] = {};
	for (i = 1, n = 0; i <= N; i++) {
		for (j = 0; j < n; j++) {
			if (lex_smaller(S[i], S[city[j]]) == 0) break;
		}
		if (j == n) city[n++] = i;
	}
	
	int m = 0, flag[101] = {}, max, argmax;
	char *tmp, **heap = (char**)malloc(sizeof(char*) * n);
	for (j = 0; j < n; j++) push(S[city[j]], heap, &m);
	while (m > 0) {
		tmp = pop(heap, &m);
		while (1) {
			max = -1;
			for (i = 1; i <= N; i++) {
				if (flag[i] == 0 && P[i] > max && lex_smaller(tmp, S[i]) == 0) {
					max = P[i];
					argmax = i;
				}
			}
			if (max == -1) break;
			else {
				printf("%d\n", argmax);
				flag[argmax] = 1;
			}
		}
	}
	
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  string s;
  cin >> s;
  ll ans=0;
  for(ll i=0;i<4;i++) {
    if(s[i]=='+') ans++;
    if(s[i]=='-') ans--;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
typedef long long ll;
using namespace std;
int main(void){
    ll n,c;cin>>n>>c;
    vector<ll> x(n),v(n),a(n),b(n),d(n),e(n);
    rep(i,n) cin>>x[i]>>v[i];
    ll tmp=0;
    rep(i,n){
        if(i==0){
            tmp+=v[i];
            a[i]=max(tmp-x[i],(ll)0);
            d[i]=(a[i]==tmp-x[i])? x[i]:0;
        }
        else{
            tmp+=v[i];
            a[i]=max(a[i-1],tmp-x[i]);
            d[i]=(a[i]==tmp-x[i])? x[i]:d[i-1];
        }
    }
    reverse(x.begin(),x.end());
    reverse(v.begin(),v.end());
    tmp=0;
    rep(i,n){
        x[i]=c-x[i];
        if(i==0){
            tmp+=v[i];
            b[i]=max(tmp-x[i],(ll)0);
            e[i]=(b[i]==tmp-x[i])? x[i]:0;
        }
        else{
            tmp+=v[i];
            b[i]=max(b[i-1],tmp-x[i]);
            e[i]=(b[i]==tmp-x[i])? x[i]:e[i-1];
        }
    }
    
    reverse(b.begin(),b.end());
    reverse(e.begin(),e.end());
    //rep(i,n) cout<<d[i]<<" "<<e[i]<<endl;
    ll res=0;
    rep(i,n){
        //cout<<i<<endl;
        if(i==n-1){
            ll now=a[i];
            res=max(res,now);
        }
        else{
            ll left=a[i],right=b[i+1];
            //cout<<left<<" "<<right<<endl;
            ll now=right+left;
            now-=min(d[i],e[i+1]);
            res=max(res,now);
        }
        if(i==0){
            ll now=b[i];
            res=max(res,now);
        }
        else{
            ll left=a[i-1],right=b[i];
            //cout<<left<<" "<<right<<endl;
            ll now=right+left;
            now-=min(d[i-1],e[i]);
            res=max(res,now);
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 4992