akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstring>
using namespace std;
int main(){
bool f=true;
	char s[11];
	scanf("%s",s);
	if(s[0]!='A'){
		cout<<"WA";
		return 0;
	}
	int n=strlen(s);
	for(int i=0;i<n;i++)
		if(s[i]!='A'&&s[i]!='C')
			if(s[i]<'a'||s[i]>'z')
				f=false;
	int sum=0;
	for(int i=2;i<n-1;i++)	
		if(s[i]=='C')
			sum++;
	if(sum!=1)
		f=false;
	if(f==true)
		cout<<"AC";
	else
		cout<<"WA";		
			
}

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

int main() {
  int d, t, s;
  cin >> d >> t >> s;
  if (d <= t*s) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3548
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

int main ()
{
    int64_t x;
    cin >> x;
    int64_t money = 100;
    int64_t i;
    for (i = 0; money < x; i++) {
        money += money / 100;
    }
    cout << i;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
long long F[200009],C[200009];
long long a[200009];
vector<long long> v[200009];
priority_queue<long long > q;
priority_queue<long long> p[200009];
void dfs(long long x, long long t)
{
    F[x] = 1;
    C[x] = t;
    for (long long i =0 ; i < v[x].size(); i++)
        if(F[v[x][i]]==0) dfs(v[x][i],t);
}
main()
{
    long long N,m;
    cin >> N >> m;
    for (long long i =0; i < N; i++)
    {
        cin >> a[i];
    }
    for (long long i =0; i < m; i++)
    {
        long long a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    long long t =0;
    for (long long i =0; i < N; i++)
        if(F[i] ==0) {dfs(i,t); t++;}
    for (long long i =0; i < N; i++)
        p[C[i]].push(-a[i]);
        long long ans=0;
        if (m == N-1) {cout << 0 << endl; return 0;}
        m= 2*((N-1)-m);
    for (long long i =0; i < t; i++)
    {
        ans += p[i].top();
        p[i].pop();
        m --;
        while(p[i].size())
        {
            q.push(p[i].top());
            p[i].pop();
        }
    }
    if(q.size() < m) {cout <<"Impossible"<< endl; return 0;}
    while(m)
    {
        ans+=q.top();
        q.pop();
        m--;
    }
    cout << -ans << endl;

}


Measured memory_bytes: 21108
//verma_ankit484

#include<bits/stdc++.h>

typedef long long ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
const ll mod = (ll) 1e9+7;

using namespace std;

ll n, t;
vector<pair<ll, ll>> vc;

ll dp[3003][3003];

ll rec(ll idx, ll sum) {
  if (sum >= t) return 0;
  if (idx == n) {
    return 0;
  }
  ll &ans = dp[idx][sum];
  if (ans != -1) return ans;
  ans = vc[idx].second+rec(idx+1, sum+vc[idx].first);
  ans = max(ans, rec(idx+1, sum));
  return ans;
}

int main() {
  IOS
  #ifdef AV
  freopen("int.txt", "r", stdin);
  #endif
  cin >> n >> t;
  vc.resize(n);
  for (ll i = 0; i < n; i++) {
    cin >> vc[i].first >> vc[i].second;
  }
  sort(vc.begin(), vc.end());
  memset(dp, -1, sizeof(dp));
  cout << rec(0, 0) << endl;
  return 0;
}


Measured memory_bytes: 70912
# https://atcoder.jp/contests/abc152/tasks/abc152_e
# 見た瞬間にわかってしまった天才だ

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  # ここにバグがないか心配
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))

    if temp != 1:
        arr.append((temp, 1))

    if arr == []:
        arr.append((n, 1))

    return arr


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from fractions import gcd


def ret_inv(a, p):
    return pow(a, p - 2, p)


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a * b // g


N = read_a_int()
A = read_ints()

flat = defaultdict(lambda: 0)  # 素数がkey
for a in A:  # modで演算できるようにするか掛け算を実際には行わずに保持しておく必要がある。
    tmp = factorization(a)
    for k, v in tmp:
        flat[k] = max(flat[k], v)

flat_mod = 1
for k, v in flat.items():
    flat_mod *= pow(k, v, MOD)
    if flat_mod >= MOD:
        flat_mod %= MOD

ans = 0
for a in A:
    ans += flat_mod * ret_inv(a, MOD)
    if ans >= MOD:
        ans %= MOD
print(ans)


Measured memory_bytes: 71896
#include <stdio.h>
int stu[501][10001];
int main (void){
    int n,m,a,b,i,j;
    for(;;){
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)break;
        int sanka1[501]={0},sanka2[501]={0},ans=0;
        for(i=0;i<501;i++){
            for(j=0;j<10001;j++){
                stu[i][j]=0;
            }
        }
        for(i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            stu[a][b]=1;
        }
        for(i=0;i<=n;i++){
            if(stu[1][i]==1||stu[i][1]==1){
                sanka1[i]=1;
                sanka2[i]=1;
            }
        }
        for(i=0;i<=n;i++){
            for(j=0;j<=n;j++){
                if(sanka1[i]==1&&(stu[i][j]==1||stu[j][i]==1)){
                    sanka2[j]=1;
                }
            }
        }
        for(i=0;i<=n;i++){
            if(sanka2[i]==1){
                ans++;
            }
        }
        if(ans!=0)ans=ans-1;
        printf("%d\n",ans);
    }
return 0;
}

Measured memory_bytes: 20176
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

k = 0
l = 0
acc = None

def count_up(y1, x1, y2, x2):
    global acc, l
    if y1 > y2 or x1 > x2:
        return 0
    y2 += 1
    x2 += 1
    return  acc[y2][x2] - acc[y1][x2] - acc[y2][x1] + acc[y1][x1]

def main():
    global acc, k, l
    n, k = map(int, sys.stdin.readline().split())
    xycs = (map(lambda x: int(x) if x != 'B' and x != 'W' else x,
                 line.split()) for line in sys.stdin.readlines())

    l = k * 2
    yxs = (((y + k) % l, x % l) if c == 'W' else (y % l, x % l) for x, y, c in xycs)

    acc = [[0] * (l + 1) for _ in range(l + 1)]
    for y, x in yxs:
        acc[y + 1][x + 1] += 1
    for j in range(l):
        for i in range(l):
            acc[j + 1][i + 1] += acc[j + 1][i] + acc[j][i + 1] - acc[j][i]

    max_cnt = 0
    for j in range(k):
        for i in range(k):
            cnt = count_up(0, 0, j - 1, i - 1) + count_up(0, i + k, j - 1, l - 1) + count_up(j, i, j + k - 1, i + k - 1) + count_up(j + k, 0, l - 1, i - 1) + count_up(j + k, i + k, l - 1, l - 1)
            max_cnt = max(max_cnt, max(n - cnt, cnt))

    print(max_cnt)

if __name__ == '__main__':
    main()


Measured memory_bytes: 94812
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3005, mod = 1000000007;

int n, m, a[maxn];
ll f[maxn][maxn];

ll qpow(ll x, int y)
{
	ll ret = 1;
	while(y)
	{
		if(y&1)
			ret = ret * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ret;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			f[i][j] = (a[i] > a[j]);
	int u, v, inv2 = qpow(2, mod - 2);
	for(int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &u, &v);
		if(u > v)	swap(u, v);
		f[u][v] = f[v][u] = inv2 * (f[u][v] + f[v][u]) % mod;
		for(int j = 1; j <= n; ++j)
			if(j != u && j != v)
			{
				f[j][u] = f[j][v] = inv2 * (f[j][u] + f[j][v]) % mod;
				f[u][j] = f[v][j] = inv2 * (f[u][j] + f[v][j]) % mod;
			}
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			ans = (ans + f[i][j]) % mod;
	printf("%lld", ans * qpow(2, m) % mod);
	return 0;
}


Measured memory_bytes: 70656
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.container;
import std.datetime;

void main()
{
	immutable MAX = 1000000;

	bool p[MAX];
	p[] = 1;
	p[0..2] = 0;
	foreach (i; 2..sqrt(MAX*1.0).ceil.to!int) {
		if (p[i]) {
			foreach (j; iota(i*2, MAX, i))
				p[j] = 0;
		}
	}

	while (1) {
		auto x = readln.chomp.split.map!(to!int);
		if (x[0] == -1) break;
		int cnt;
		int[] plist;
		foreach (i; x[0]+1..MAX) {
			if (p[i]) {
				cnt++;
				plist ~= i;
				if (cnt == 100) break;
			}
		}
		int[] res;
		foreach (i, e; plist) {
			auto a = plist[i..$].dup;
			a[] += e;
			res ~= a;
		}
		res.sort[x[1]-1].writeln;
	}
}

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

dp = [[10 ** 18] * n for _ in range(n)]
dp[0] = [0] * n

s = [0]
for i in a:
    s.append(s[-1]+i)


for i in range(1, n):
    for j in range(n):
        if i + j < n:
            b = 10 ** 18
            for k in range(i):
                l = i - k - 1
                b = min(b, dp[k][j]+dp[l][j+k+1])
            dp[i][j] = b + s[i+j+1]-s[j]

print(dp[-1][0])


Measured memory_bytes: 42988
from collections import defaultdict as dd
import heapq
N = int(input())
a = list(map(int,input().split()))
res = 0
a = sorted(a, reverse=True)
dic=dd(list)
ls = [-a[0]]
heapq.heapify(ls)
for val in a[1:]:
    tmp = -heapq.heappop(ls)
    res += tmp
    heapq.heappush(ls,-val)
    heapq.heappush(ls,-val)
print(res)

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

bool isACGT(char &c){
  return c == 'A' || c == 'C' || c == 'G' || c == 'T';
}

int main(){
  string S;
  cin >> S;
  
  int count = 0;
  int countmax = 0;
  
  for(char &c:S){
    if(isACGT(c)){
      count++;
      if(count > countmax)
        countmax = count;
    }
    else
      count = 0;
  }
  
  cout << countmax << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
const long long MAX=1e18;
long long a[100010];
long long sum=0;
long long find(long long x)
{
    //cout<<x<<" ";
	long long num=0;	
    long long ans;
	for(long long i=1;;i++)
	{
		num+=i;
		if(x<num) 
		{
			ans=i;
			//cout<<ans<<" ";
			break;
		}
		
	}
	//cout<<ans-1<<" ";
	return ans-1;
}
void divide(long long x)
{
    for (long long i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            long long s = 0;
            while (x % i == 0) x /= i, s ++ ;
            a[++sum]=s;
        }
    if (x > 1) a[++sum]=1;

}
int main()
{
    long long n;
    cin>>n;
    long long ans=0;
    divide(n);
    //cout<<sum;
    for(long long i=1;i<=sum;i++)
    {
    	ans+=find(a[i]);
    	//cout<<ans<<" ";
	}
	//find(1);
	cout<<ans;
}


Measured memory_bytes: 3636
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using StructLayoutAttribute = System.Runtime.InteropServices.StructLayoutAttribute;
using FieldOffsetAttribute = System.Runtime.InteropServices.FieldOffsetAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        var nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(string.Join("\n", Enumerable.Range(0, nm[1]).Select(x => new Tuple<int[], int>(Console.ReadLine().Split().Select(int.Parse).ToArray(), x)).GroupBy(x => x.Item1[0]).SelectMany(x => x.OrderBy(y => y.Item1[1]).Select((y, z) => new Tuple<string, int>($"{y.Item1[0].ToString().PadLeft(6, '0')}{(z + 1).ToString().PadLeft(6, '0')}", y.Item2))).OrderBy(x => x.Item2).Select(x => x.Item1)));
    }
}


Measured memory_bytes: 52916
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_map>


int main (void) {
  long long N, M;
  std::cin >> N >> M;

  std::vector<std::pair<long long, long long>> drink(N);
  for(int i=0; i<N; i++) std::cin >> drink[i].first >> drink[i].second;

  std::sort(drink.begin(), drink.end(),
      [](std::pair<long long,long long> x, std::pair<long long,long long> y) { return x.first < y.first;});

  long long num_bought = 0;
  long long money = 0;
  for(int i=0; i<N; i++) {
    money += drink[i].first * std::min(drink[i].second, M-num_bought);
    num_bought += std::min(drink[i].second, M-num_bought);
    if ( M == num_bought ) break;
  }

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

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define debug(x) cerr << "\n" \
                      << #x << ": " << x << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define int long long
#define print(x) cout << (x) << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = (1LL << 30);
const ll MOD = 1000000007;
//=============================================================
//=============================================================

int N, M;
int H, W;
int ans = INF;
vector<int> h;
int K;
void solve(){
    sort(h.begin(),h.end());
    for (int i=0; i<= N-K; ++i){
        ans = min(ans, (h[i+K-1] - h[i]));
    }
    cout<<ans<<endl;

}

signed main()
{
    cin >> N >> K;
    rep(i,N){
        int uuuu;
        cin>>uuuu;
        h.push_back(uuuu);
    }
    solve();
    return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int main(){
	int r=read(),g=read(),b=read(),n=read(),cnt=0;
	FOR(i,0,n/r) FOR(j,0,(n-i*r)/g) if((n-i*r-j*g)%b==0) cnt++; 
	printf("%d\n",cnt);
}

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

int main()
{
    string a,b;
    cin>>a>>b;
    if(a.size()> b.size())cout<<"GREATER\n";
    else {
        if(a.size()<b.size())cout<<"LESS\n";
        else {
            if(a>b)cout<<"GREATER";
            else if(a<b)cout<<"LESS\n";
            else cout<<"EQUAL";
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,a,b,q;
  cin>>n>>a>>b>>q;
  vector<Int> x(a),y(b),h(b),z(q);
  vector<char> c(a);
  for(Int i=0;i<a;i++) cin>>x[i]>>c[i],x[i]--;
  for(Int i=0;i<b;i++) cin>>y[i]>>h[i],y[i]--,h[i]--;
  for(Int i=0;i<q;i++) cin>>z[i],z[i]--;

  y.emplace_back(n);

  auto pos=
    [&](Int k)->Int{
      Int j=b;
      while(1){
	while(j>=0&&k<y[j]) j--;
	if(j<0||h[j]<0||y[j+1]<=k) return k;
	Int l=y[j+1]-y[j];
	if(h[j]+l<=y[j]){
	  k=h[j]+(k-y[j]);
	  continue;
	}
	Int m=y[j]-h[j];
	k=h[j]+(k-y[j])%m;
      }
    };
  
  map<Int, char> dp;  
  for(Int i=0;i<a;i++) dp[pos(x[i])]=c[i];
  for(Int i=0;i<q;i++){
    Int k=pos(z[i]);
    cout<<(dp.count(k)?dp[k]:'?');
  }
  cout<<endl;  

  return 0;
}



Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
int main(){
 int N;
  cin >> N;
  int n = N;
  int O,Y,A,U,M,S,H,J,I;
  O = N / 100000000;
  N = N % 100000000;
  Y = N / 10000000;
  N = N % 10000000;
  A = N / 1000000;
  N = N % 1000000;
  U = N / 100000;
  N = N % 100000;
  M = N / 10000;
  N = N % 10000;
  S = N / 1000;
  N = N % 1000;
  H = N / 100;
  N = N % 100;
  J = N / 10; 
  N = N % 10;
  I = N;
  int Goukei = O+Y+A+U+M+S+H+J+I;
    if(n % Goukei == 0){
      cout <<"Yes"<< endl; 
    }
  else{
    cout <<"No"<< endl;
  }
}

Measured memory_bytes: 3580
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define int long long
signed main() {
	int n, m; cin >> m >> n;
	vector<int>v1, v2;
	for (int i = 0; i < n; i++) {
		int p; cin >> p;
		v1.push_back(p);
	}
	sort(v1.begin(), v1.end());
	for (int i = 1; i < n; i++)v2.push_back(v1[i] - v1[i - 1]);
	sort(v2.begin(), v2.end());
	int ans = 0;
	for (int i = 0; i < n - m; i++) ans += v2[i];
	cout << ans << endl;
}

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

int main(){
   int a,b,c,d;
   cin >> a >> b >> c>> d;
   if(abs(c-a)<=d || (abs(b-a) <= d && abs(c-b)<=d)){
      cout << "Yes";
   }else{
      cout << "No";
   }
   return 0;
}

Measured memory_bytes: 256
# 最初はa[0]がプラス、マイナスで場合分けしていたが、それだと最小にならない可能性があるため
# 偶数番目の和をプラス、奇数番目の和をプラスにする場合をやって最小になるほうを結果として出す

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

cnt = [0,0]

for i in [0,1]:
    tmp_sum = 0
    for index, value in enumerate(a):
        tmp_sum += value
        if (i + index) % 2 == 0:
            if tmp_sum <= 0:
                cnt[i] += abs(tmp_sum) + 1
                tmp_sum += abs(tmp_sum) + 1
        else:
            if tmp_sum >= 0:
                cnt[i] += tmp_sum + 1
                tmp_sum -= tmp_sum + 1


print(min(cnt))

Measured memory_bytes: 14332
#include <iostream>
#include <string>
#include <map>
using namespace std;

map<string,string> code1,code2;

int main() {
    code1["A"] = "00000"; code1["B"] = "00001";
    code1["C"] = "00010"; code1["D"] = "00011";
    code1["E"] = "00100"; code1["F"] = "00101";
    code1["H"] = "00111"; code1["G"] = "00110";
    code1["I"] = "01000"; code1["J"] = "01001";
    code1["K"] = "01010"; code1["L"] = "01011";
    code1["M"] = "01100"; code1["N"] = "01101";
    code1["O"] = "01110"; code1["P"] = "01111";
    code1["Q"] = "10000"; code1["R"] = "10001";
    code1["S"] = "10010"; code1["T"] = "10011";
    code1["U"] = "10100"; code1["V"] = "10101";
    code1["W"] = "10110"; code1["X"] = "10111";
    code1["Y"] = "11000"; code1["Z"] = "11001";
    code1[" "] = "11010"; code1["."] = "11011";
    code1[","] = "11100"; code1["-"] = "11101";
    code1["'"] = "11110"; code1["?"] = "11111";

    code2["101"] = " "; code2["000000"] = "'"; code2["000011"] = ",";
    code2["10010001"] = "-"; code2["010001"] = "."; code2["000001"] = "?";
    code2["100101"] = "A"; code2["10011010"] = "B"; code2["0101"] = "C";
    code2["0001"] = "D"; code2["110"] = "E"; code2["01001"] = "F";
    code2["10011011"] = "G"; code2["010000"] = "H"; code2["0111"] = "I";
    code2["10011000"] = "J"; code2["0110"] = "K"; code2["00100"] = "L";
    code2["10011001"] = "M"; code2["10011110"] = "N"; code2["00101"] = "O";
    code2["111"] = "P"; code2["10011111"] = "Q"; code2["1000"] = "R";
    code2["00110"] = "S"; code2["00111"] = "T"; code2["10011100"] = "U";
    code2["10011101"] = "V";  code2["000010"] = "W"; code2["10010010"] = "X";
    code2["10010011"] = "Y"; code2["10010000"] = "Z";

    string input;
    while(getline(cin, input)) {
        string tr1 = "";
        for(int i=0; i<input.length(); ++i) tr1 += code1[string(1,input[i])];
        string tmp = "",res = "";
        for(int i=0; i<tr1.length(); ++i) {
            tmp += string(1,tr1[i]);
            if(code2.find(tmp) != code2.end()) {
                res += code2[tmp];
                tmp = "";
            }
        }

        cout<<res<<endl;
    }
}

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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    ll N, K; cin >> N >> K;
    ll tmp = N % K;
    cout << min(abs(tmp - K),tmp) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int h,w;
    cin>>h>>w;
    set<pair<int,int>>s;
    multiset<int>ms;
    for(int i=0;i<w;i++){
        s.insert({i,i});
        ms.insert(0);
    }
    vector<int>ans;
    for(int i=1;i<=h;i++){
        int a,b;
        cin>>a>>b;
        int max_start=-1;
        for(auto j=s.lower_bound({a-1,0});j!=s.lower_bound({b,0});j=s.erase(j)){
            max_start=max(max_start,(*j).second);
            ms.erase(ms.find((*j).first-(*j).second));
        }
        if(b<w && max_start!=-1){
            s.insert({b,max_start});
            ms.insert(b-max_start);
        }
        ans.push_back(ms.size() ? *ms.begin()+i : -1);
    }
    for(int i:ans)cout<<i<<endl;
    return 0;
}

Measured memory_bytes: 22816
import scala.annotation.tailrec
import scala.io.StdIn.{readInt, readLine}

object Main extends App {
  import Implicits.ListOps

  val Zero = BigInt(0)
  val VMax = BigInt(1_000_000_000_000_000_000L)

  val n  = readInt()
  val xs = readLine().split(' ').view.map { BigInt(_) }.toList

  val (s, isOver) =
    if (xs.contains(Zero)) (Zero, false)
    else {
      val (s, ys) = xs.reduceWhile { _ * _ } { _ <= VMax }
      (s, ys.nonEmpty)
    }

  println(if (isOver) -1 else s)
}

/**
  * 拡張メソッド群
  */
object Implicits {

  /**
    * List用拡張メソッド
    * @param self 自身を表すList
    * @tparam A 要素の型
    */
  implicit class ListOps[A](self: List[A]) {

    /**
      * 条件を満たし続ける限りListの要素を集約する
      * 条件を満たさなくなった時点で処理を打切る
      * @param z 初期値
      * @param op 集約演算用の関数
      * @param p 処理を続けるかどうかを判定する述語関数
      * @return 条件を満たさなくなった時点のそれまでの計算結果と残りのリストListの組
      */
    def foldWhile[B](z: B)(op: (B, A) => B)(p: B => Boolean): (B, List[A]) = {

      @tailrec
      def go(zs: List[A], accum: B): (B, List[A]) = zs match {
        case Nil => (accum, Nil)
        case x :: xs =>
          val s = op(accum, x)
          if (p(s)) go(xs, s) else (accum, zs)
      }

      go(self, z)
    }

    /**
      * foldWhileの初期値を自身の先頭要素にした関数
      */
    def reduceWhile(op: (A, A) => A)(p: A => Boolean): (A, List[A]) =
      self.tail.foldWhile(self.head)(op)(p)
  }
}


Measured memory_bytes: 79328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){for(ll i=0;i<v.size();++i) x<<v[i]<<" ";return x;}
template <typename X> ostream& operator << (ostream& x,const set<X>& v){for(auto it:v) x<<it<<" ";return x;}
template <typename X, typename Y> ostream& operator << (ostream& x, const pair<X,Y>& v) {x<<v.ff<<" "<<v.ss;return x;}
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (auto it : v) os << it.first << "=>" << it.second << endl; return os; }
struct pair_hash {inline std::size_t operator()(const std::pair<ll, ll> & v) const {return v.first*31+v.second;}};
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL)
#define pb push_back
#define fr first
#define sc second
#define prnt(m) for(auto it = m.begin() ; it != m.end() ; ++it){cout<<*it<<endl;}
#define tra(it,m) for(auto it=m.begin();it!=m.end();++it)
#define DBG(x) cout<<"# # #     "<<x<<'\n';
#define fri(i,s,n) for(int i=s;i<n;i++)
#define mod 1000000007LL
#define mod2 998244353
#define vct2 vector<vector<ll>>
#define vct vector<ll>
#define pll pair<ll,ll>
#define rz(n) resize(n)
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define arrin(a,n) for(ll i = 0; i < n ; i++){cin>>a[i];}
#define arrout(a,n) for(ll i = 0;i < n; i++){cout<<a[i]<<" ";}
#define ex(s) cout<<s<<endl,exit(0);
#define inf 1e18
#define five 100005;
#define six 1000005;
#define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
//___________________________________________________________________________________________________________________________________________________________
const int N = five;
ll dp[2][N];
pll val[N];
ll pre[N];
int main()
{
       int n,k;
       cin>>n>>k;
       map<pair<int,int>,int> mp;
       for(ll i = 1 ; i*i <= n ; i++)
       {
              mp[mkp(i,i)] = n/i;
              mp[mkp((n/(i+1))+1,n/i)] = i;
       }
       map<int,int> mp1;
       int ii = 0;
       val[0] = {0,0};
       tra(it,mp){
              mp1[it->fr.sc] = ii;
              val[ii++].fr = it->sc;
              val[ii-1].sc = it->fr.sc-it->fr.fr+1;
       }
       fri(i,0,ii){
              dp[0][i] = val[i].sc;
       }
       fri(i,1,k){
              dp[1][0] = dp[0][0];
              fri(j,1,ii){
                     dp[1][j] = (dp[1][j-1] + dp[0][j])%mod;
              }
              fri(j,0,ii){
                     dp[0][j] = (val[j].sc*(dp[1][mp1[val[j].fr]]))%mod;
              }
       }
       dp[1][0] = dp[0][0];
       fri(j,1,ii){
              dp[1][j] = (dp[1][j-1] + dp[0][j])%mod;
       }
       cout<<dp[1][ii-1]<<endl;
}


Measured memory_bytes: 9088
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <ostream& out = cout, class... T> void prints(T&&...){ }
template <ostream& out = cout, class... T> void printd(T&&...){ }
template <ostream& out = cout, class... T> void printb(T&&...){ }
template <ostream& out = cout, class... T> void printArr(T&&...){ }
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, a, b;
    cin >> n >> a >> b;
    vector<int> hs(n);
    for(int i = 0; i < n; i++){
        cin >> hs[i];
        // scanf("%d", &hs[i]);
    }
    sort(hs.rbegin(), hs.rend());
    auto solve = [&](int num){
        int cnt = num;
        for(int i = 0; i < n; i++){
            ll hp = hs[i] - b * num;
            if(hp <= 0){ break; }
            cnt -= (hp + a - b - 1) / (a - b);
            if(cnt < 0){
                break;
            }
        }
        return cnt >= 0;
    };
    int l = 0, r = 1e9;
    while(l < r){
        int piv = (l + r) / 2;
        if(solve(piv)){
            r = piv;
        }else{
            l = piv + 1;
        }
        prints(l, r);
    }
    cout << l << '\n';
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for(int i = 0; i < (int)(n) ; i++)

// chmax, chmin
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;
}


int log2ceil(int n) {
    --n;
    n |= n >> 16;
    n |= n >> 8;
    n |= n >> 4;
    n |= n >> 2;
    n |= n >> 1;
    return n + 1;
}

template<class Monoid>
class SegmentTree {
public:
    using value_type = typename Monoid::value_type;
    using update_type = typename Monoid::value_type;

private:
    const int size_, n;
    std::vector<value_type> data;

public:
    SegmentTree(const std::vector<value_type> &vec) :
            size_(vec.size()), n(log2ceil(size_)), data(n * 2, Monoid::id()) {
        std::copy(begin(vec), end(vec), begin(data) + n);
        for (int i = n - 1; i >= 0; --i) {
            data[i] = Monoid::op(data[i * 2 + 0], data[i * 2 + 1]);
        }
    }

    SegmentTree(const int count, const value_type &value = Monoid::id()) :
            SegmentTree(std::vector<value_type>(count, value)) {}

    int size() const { return size_; }

    void update(int pos, const value_type &value) {
        assert(0 <= pos && pos < size_);  // assertion
        data[pos += n] = value;
        while (pos /= 2) {
            data[pos] = Monoid::op(data[pos * 2], data[pos * 2 + 1]);
        }
    }

    // セグメント木の区間 [l, r) を演算 Monoid::op (⋅⋅) で畳み込んだ値を返す． すなわち，al⋅al+1⋅…⋅ar−1al⋅al+1⋅…⋅ar−1 を返す． l=rl=r の場合は Monoid::id() を返す．
    value_type query(int l, int r) const {
        assert(0 <= l && l <= r && r <= size_);  // assertion
        l += n;
        r += n;
        value_type res1 = Monoid::id(), res2 = Monoid::id();
        while (l < r) {
            if (l & 1) res1 = Monoid::op(res1, data[l++]);
            if (r & 1) res2 = Monoid::op(data[--r], res2);
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(res1, res2);
    }
};

// RMQ
struct RMQ {
    using value_type = int;

    static value_type id() { return -1000000000; }

    static value_type op(const value_type &l, const value_type &r) {
        return std::max(l, r);
    }
};


void solve(long long N, long long K, std::vector<long long> A) {

    SegmentTree<RMQ> rmq(350000);


    for (int i = 0; i < A.size(); i++) {
        long long L = max(0ll, A[i] - K);
        long long R = min(A[i] + K, 340000ll) + 1;
        if( rmq.query(A[i], A[i]+1) < 0 ) {
            rmq.update(A[i], 0);
        }
        rmq.update(A[i], rmq.query(L, R) + 1);
    }

    cout << rmq.query(0, 350000) << endl;
}

int main() {
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }
    solve(N, K, std::move(A));
    return 0;
}



Measured memory_bytes: 11196
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, k: usize,
        a: [usize; n],
    }
    let mut acc = vec![0; n];
    for i in 0..n - 1 {
        acc[i + 1] = acc[i] + if a[i] < a[i + 1] { 0 } else { 1 };
    }
    let mut s = BTreeSet::new();
    for i in 0..k {
        s.insert(a[i]);
    }
    let mut ans = 1;
    let mut inc_count = 0;
    if acc[k - 1] == acc[0] {
        inc_count += 1;
    }
    for i in k..n {
        let &mi = s.iter().next().unwrap();
        let &ma = s.iter().rev().next().unwrap();
        let diff = a[i - k] != mi || a[i] < ma;
        if diff {
            if acc[i] == acc[i - (k - 1)] {
                inc_count += 1;
            }
            ans += 1;
        }
        s.remove(&a[i - k]);
        s.insert(a[i]);
    }
    if inc_count > 0 {
        ans -= inc_count - 1;
    }
    debugln!("{} {}", ans, inc_count);
    puts!("{}\n", ans);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 14588
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
  
typedef pair<double,double> P;
typedef pair<P,double> P2;
  
P rot(P p, double a){
  a=a*M_PI/180.0;
  return P(p.first*cos(a)+p.second*(-sin(a)),
  p.first*sin(a)+p.second*cos(a));
}
  
double abss(P a,P b){
  return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
  
double x,y,r;int tt;
vector<P>v;
int main(){
  
  int n;
  cin>>n;
  
    double ans=1e13;
      
    v.clear();
    
    r(i,n){
      cin>>x>>y;
      v.push_back(P(x,y));
    }
  
    r(i,1){
      sort(v.begin(),v.end());
      r(j,n){
        for(int k=j+1,c=0;k<n;k++,c++){
          if(c>50)break;
          ans=min(ans,abss(v[k],v[j]));
        }
      }
      r(j,n)v[i]=rot(v[i],0.5);
    }
  
    printf("%d\n",(int)ans);
      
}


Measured memory_bytes: 11148
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin {{{
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (i64 i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (i64 i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T> using MaxHeap = priority_queue<T>;
template <class T> using MinHeap = priority_queue<T, vector<T>, greater<>>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return n * (1 + n) >> 1; }
inline i64 updiv(i64 n, i64 d) { return (n + d - 1) / d; }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

#ifndef DEBUG
#define dump(...)
#endif

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

inline void outs() { cout << "\n"; }
template <class Head, class... Tail>
inline void outs(Head&& head, Tail&&... tail) {
    cout << head << (sizeof...(tail) ? " " : "");
    outs(forward<Tail>(tail)...);
}

template <class T>
inline void outs(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e == &vec.back()]; }

template <class T>
inline void outs(vector<vector<T>> &df) { for (auto &vec : df) outs(vec); }

inline void outl() { cout << "\n"; }
template <class Head, class... Tail>
inline void outl(Head&& head, Tail&&... tail) {
    cout << head << (sizeof...(tail) ? "\n" : "");
    outl(forward<Tail>(tail)...);
}

template <class T>
inline void outl(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

inline void outn() {}
template <class Head, class... Tail>
inline void outn(Head&& head, Tail&&... tail) {
    cout << head;
    outn(forward<Tail>(tail)...);
}

template <class T>
inline void outn(vector<T> &vec) { for (auto &e : vec) cout << e; }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}
// }}} End

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

    var(int64_t, a, b, k);

    intmax_t tmpa = a;
    a = max<intmax_t>(0LL, a - k);
    k = max<intmax_t>(0LL, k - tmpa);

    b = max<intmax_t>(0LL, b - k);

    outs(a, b);

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
ll cntr, cntg, cntb;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int N;
    string S;
    cin >> N;
    cin >> S;
    ll ans = 0;
    for(int i = 0; i < N; i++){
        if(S[i] == 'R') cntr++;
        else if(S[i] == 'G') cntg++;
        else cntb++;
    }
    ans = cntr*cntg*cntb;
    for(int i = 0; i < N; i++){
        for(int j = 1; i+2*j < N; j++){
            if((S[i] != S[i+j]) && (S[i+j] != S[i+2*j]) && (S[i+2*j] != S[i])) ans--;
        }
    }  
    cout << ans << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
#define big 998244353
#define ff first
#define se second
#define pb push_back
#define pii pair<int,int>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define mp make_pair
#define pi 3.141592653589
int power(int x,int y){
    int r=1,z=x;
    while(y){
        if(y & 1)r*=z;
        z*=z;y=y>>1;}
    return r;}
int powerm(int x,int y,int p){
    int r=1;
    while(y){
        if(y & 1)r=(r*x)%p;
        y=y>>1;
        x=(x*x)%p;}
    return r%p;}
int modinv(int x,int m){
    return powerm(x,m-2,m);}
int logarithm(int a,int b){
    int x=0;
    while(a>1){
        x++;
        a/=b;}
    return x;}
int32_t main(){
    fast;
    int n;
    cin>>n;
    vector<int> h(n),dp(n);
    for(int i=0;i<n;i++){
        cin>>h[i];
        dp[i]=INT_MAX;
    }
    dp[0]=0;
    for(int i=0;i<n;i++){
        if(i+1<n)
            dp[i+1]=min(dp[i+1],dp[i]+abs(h[i+1]-h[i]));
        if(i+2<n)
            dp[i+2]=min(dp[i+2],dp[i]+abs(h[i+2]-h[i]));
    }
    cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 4792
#include<bits/stdc++.h>
using namespace std;
int main(){
	char c,h,n;
	string x,y,z;
	cin>>x>>y>>z;
	c=x.at(0);
	h=y.at(0);
	n=z.at(0);
	c-=32;
	h-=32;
	n-=32;
	cout<<c<<h<<n;
	return 0;
}

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

int main() {
  int N, A[200], count = 0;
  bool oddFlag = false;
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  while(!oddFlag) {
    for(int i = 0; i < N; i++) {
      if(A[i] % 2) oddFlag = true;
      else A[i] /= 2;
    }
    if(!oddFlag) count++;
  }
  cout << count << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> p(n);
  int a[3];
  for(int i=0;i<n;i++){
    cin >> p.at(i);
  }
  int flag=0;
  for(int i=1;i<n-1;i++){
    a[0] = p[i-1];
    a[1] = p[i];
    a[2] = p[i+1];
    sort(a,a+3);
    if(a[1]==p[i]) flag++;
}
cout << flag << endl;
}


Measured memory_bytes: 256
gets
a = gets.split.map &:to_i

escapable = [0] * a.size

block = 0
(0..a.size-1).each do |i|
	x = a[i]
	if x < 0
		block = [block, x.abs].min
	elsif x > 0
		e = [x, block].min
		escapable[i] = e if e > escapable[i]
	else
		block = Float::INFINITY
	end
	block -= 1
end

block = 0
(a.size-1).step(0, -1) do |i|
	x = a[i]
	if x < 0
		block = [block, x.abs].min
	elsif x > 0
		e = [x, block].min
		escapable[i] = e if e > escapable[i]
	else
		block = Float::INFINITY
	end
	block -= 1
end

p escapable.inject(:+)

Measured memory_bytes: 17592
#include<cstdio>
#include <cstring>
using namespace std;
using ull = unsigned long long;
const static int MOD = 1000000007;

int main(){
	int N;
	scanf("%d", &N);
	ull digit_dp[N - 1][2][4][4];
	memset(digit_dp, 0, sizeof digit_dp);
	for (int i = 0; i < 4; ++i){
		for (int j = 0; j < 4; ++j) digit_dp[0][0][i][j] = 1;
	}
	for (int i = 1; i < N - 1; ++i){
		for (int j = 0; j < 4; ++j){
			for (int k = 0; k < 4; ++k){
				for (int l = 1; l < 4; ++l)	digit_dp[i][0][j][k] += digit_dp[i - 1][0][l][j] + digit_dp[i - 1][1][l][j];
			}
		}
		for (int j = 0; j < 4; ++j){
			for (int k = 0; k < 4; ++k){
				digit_dp[i][1][j][k] += digit_dp[i - 1][0][0][j] + digit_dp[i - 1][1][0][j];
			}
		}
		digit_dp[i][0][2][1] -= digit_dp[i - 1][1][3][2];//ATGC
		for (int j = 1; j < 4; ++j) digit_dp[i][0][j][1] -= digit_dp[i - 1][1][2][j];//AG?C
		digit_dp[i][1][1][2] = 0;//ACG
		digit_dp[i][1][2][1] = 0;//AGC
		digit_dp[i][0][0][1] -= digit_dp[i - 1][0][2][0] + digit_dp[i - 1][1][2][0];//GAC
		for (int j = 0; j < 2; ++j){
			for (int k = 0; k < 4; ++k){
				for (int l = 0; l < 4; ++l) digit_dp[i][j][k][l] %= MOD;
			}
		}
	}
	ull answer = 0;
	for (int i = 0; i < 2; ++i){
		for (int j = 0; j < 4; ++j){
			for (int k = 0; k < 4; ++k) (answer += digit_dp[N - 2][i][j][k]) %= MOD;
		}
	}
	printf("%llu\n", answer);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
int n,i=1;
main(){
    std::cin>>n;
    while((i*i+i)/2<n)i++;
    for(;i>0;i--){
        if(n-i>=0){
            std::cout<<i<<'\n';
            n-=i;
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  
  int m;
  m = n % 10;
  if (m == 3) {
    cout << "bon" << endl;
  }
  else if (m == 0 || m == 1 || m == 6 || m == 8) {
    cout << "pon" << endl;
  }
  else {
    cout << "hon" << endl;
  }
}


Measured memory_bytes: 3600
def main():
    H, W, N = map(int, input().split())
    sr, sc = map(int, input().split())
    S = input()
    T = input()
    safe = {"L": 1, "R": W, "U": 1, "D": H}
    inv = {
        "L": "R",
        "R": "L",
        "U": "D",
        "D": "U"
    }
    for i in range(N-1, -1, -1):
        t = T[i]
        if t == "L":
            safe["R"] = min(safe["R"] + 1, W)
        elif t == "U":
            safe["D"] = min(safe["D"] + 1, H)
        elif t == "R":
            safe["L"] = max(safe["L"] - 1, 1)
        elif t == "D":
            safe["U"] = max(safe["U"] - 1, 1)
        if S[i] in ("R", "D"):
            safe[S[i]] -= 1
        else:
            safe[S[i]] += 1
#        print(goal)
        if safe["D"] < safe["U"] or safe["R"] < safe["L"]:
            print("NO")
            return
    if safe["U"] <= sr <= safe["D"] and safe["L"] <= sc <= safe["R"]:
        print("YES")
    else:
        print("NO")


if __name__ == "__main__":
    main()


Measured memory_bytes: 45148
n = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


if n == 2:
    print('1')
elif n == 3:
    print('2')
else:
    div = set(make_divisors(n-1))
    div.add(2)
    div.add(n)
    div.remove(1)
    for i in range(2, 41):
        root = round(n ** (1/i))
        if root ** i == n:
            div.add(root)

    for j in make_divisors(n)[1:-1]:
        k = n // j
        while k % j == 0:
            k = k // j
        if k % j == 1:
            div.add(j)
    print(len(div))


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

typedef long long ll;
const ll MOD = 1000000007;

int n; ll c[60][60];
ll f[60][120];

int main()
{
	c[0][0] = 1;
	for(int i = 0; i < 60; ++i)
	{
		c[i][0] = 1;
		for(int j = 1; j <= i; ++j)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
	}
	scanf("%d", &n);
	f[1][n] = f[1][n - 1] = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = -i; j <= i; ++j)
		{
			if(f[i][j + n] == 0) continue;
			for(int a = 0; a <= n; ++a)
				for(int b = 0; b <= n; ++b)
					if(a + b > 0 && i + a + b <= n && (j + a - b) % 2 == 0 && abs(j) <= a + b)
						(f[i + a + b][(j + a - b) / 2 + n] += f[i][j + n] * c[i + a + b][a + b] % MOD * c[a + b][a] % MOD) %= MOD;
		}
	printf("%lld\n", f[n][n]);
	return 0;
}

Measured memory_bytes: 384
N,K=map(int,input().split())
s=input()

A=[]

if s[0]!='1':A.append(0)

cnt=1
pre=s[0]
for i in s[1:]:
	if pre!=i:
		A.append(cnt)
		cnt=1
		pre=i
	else:
		cnt+=1

if (s[-1]=='1' and len(A)%2==0) or (s[-1]=='0' and len(A)%2!=0):
	A.append(cnt)


if s[-1]!='0':
	A.append(0)
A.append(0)

dp=[0]*(len(A)//2-K+1)

if (2*K+1)>=len(A):print(sum(A))
else:
	for i in range(2*K+1):dp[0]+=A[i]
	
	i=1
	idx=0
	while len(dp)>i:
		dp[i]=dp[i-1]-A[idx]-A[idx+1]+A[idx+2*(K+1)]+A[idx-1+2*(K+1)]
		idx+=2
		i+=1
	
	print(max(dp))

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int g[50][50];

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n, m;cin >> n >> m;
    inc(i, 0, m){
        int a, b;cin >> a >> b;a--;b--;
        g[a][b]++;
        g[b][a]++;
    }
    inc(i, 0, n){
        int cnt = 0;
        inc(j, 0, n){
            cnt += g[i][j];
        }
        cout << cnt << endl;
    }
    return 0;
}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define each(it,v) for(auto &it : v)
#define all(v) (v).begin(),(v).end()
#define mod 1e9+7

using namespace std;
using vi = vector<int>;
using vl = vector<long>;
using P = pair<int,int>;

main()
{
        int n; cin>>n;
        int ans=0;
        rep(i,n)
        {
                int a; cin>>a;
                while(true)
                {
                        if(a%2==1)break;
                        a/=2;
                        ans++;
                }
        }
        cout<<ans<<endl;
}

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

#define rep(i,a,b) for(int i=int(a);i<=int(b);++i)
#define nrep(i,a,b) for(int i=int(a);i>=int(a);--i)
#define trv(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define watch(x) cout<<"\n"<<#x<<" is "<<x<<"\n"
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define ZERO(box) memset(box, 0, sizeof(box));
#define pb push_back
#define mt make_tuple
#define eb emplace_back
#define chkbit(s, b) (s & (1<<b))
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
const int mod=1e9+7;

int main(){
	int n;
	cin>>n;
	vi a(n),b(n),c(n);
	trv(i,0,n){
		cin>>a[i]>>b[i]>>c[i];
	}
	vector<vi> dp(n,vi(3));
	dp[0][0]=a[0];
	dp[0][1]=b[0];
	dp[0][2]=c[0];
	trv(i,1,n){
		dp[i][0] = max(dp[i-1][1]+a[i], dp[i-1][2]+a[i]);
		dp[i][1] = max(dp[i-1][0]+b[i], dp[i-1][2]+b[i]);
		dp[i][2] = max(dp[i-1][1]+c[i], dp[i-1][0]+c[i]);
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
	
}


Measured memory_bytes: 6912