akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
#define MAX_I ll_MAX //1e9
#define MIN_I ll_MIN //-1e9
#define MAX_UI Ull_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<ll,ll> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,ll> PCI;
  typedef pair<ll,char> PIC;
  typedef pair<ll,ll> PLI;
  typedef pair<ll,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

ll N,K;
vector<ll> v;

map<PII, ll> memo;
ll dfs(ll x, ll l, ll r, ll k, priority_queue<ll, vector<ll>, greater<ll> >que){
  if(k >= K) return memo[PII(l,r)] = x;
  if(memo.count(PII(l,r))) return memo[PII(l,r)];
  ll r1=0,r2=0;
  priority_queue<ll, vector<ll>, greater<ll> > que_l = que, que_r = que;
  if(l<r){
    que_l.push(v[l]);
    r1 = dfs(x+v[l], l+1, r, k+1,que_l);
    que_r.push(v[r-1]);
    r2 = dfs(x+v[r-1], l, r-1, k+1, que_r);
  }
  while(k<K && !que.empty()){
    ll x_ = que.top();
    que.pop();
    if(x_<0) x -= x_;
    else break;
    k++;
  }
  return memo[PII(l,r)] = max(x,max(r1,r2));
  return 0;
}

int main(void){
  cin >> N >> K;
  ll i;
  v.resize(N);
  REP(i,N) cin >> v[i];

  //累積和
  priority_queue<ll, vector<ll>, greater<ll> >que;
  cout << dfs(0, 0, N, 0, que ) << endl;
  return 0;
}


Measured memory_bytes: 384
//--https://kenkoooo.com/atcoder/#/table/soma62jp


#include <iostream>
#include <string>
#include <cmath>
#include <sstream>
#include <iomanip>

using namespace std;

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

	int A,B;
	char op;

	cin >> A >> op >> B;

	if(op=='+'){
		cout << A+B << endl;
	}else{
		cout << A-B << endl;
	}

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<int,int> P;

int main(){
  int n;
  cin >> n;
  int d[n];
  rep(i,n)cin >> d[i];
  int ans = 0;
  rep(i,n)rep(j,i){
    ans += d[i]*d[j];
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
x = range(n)
P =[]
s = 0
for i in x:P += [[int(i) for i in input().split()]]
P+=[P[0]]
for i in x:s += P[i][0]*P[i+1][1] - P[i][1]*P[i+1][0]
print(s*0.5)

Measured memory_bytes: 7728
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const int N = 200010, INF = 1e9 + 10;
int n, a[N], ans[N];
VI e[N], dp;

void dfs(int now, int past){
    int i = lower_bound(ALL(dp), a[now]) - dp.begin();
    int v = dp[i];
    dp[i] = a[now];
    for (int next : e[now]){
        if (next == past) continue;
        dfs(next, now);
    }
    ans[now] = lower_bound(ALL(dp), INF) - dp.begin();
    dp[i] = v;
}

int main(void){
    cin >> n;
    REP(i,n){
        a[i] = in();
    }
    REP(i,n-1){
        int u = in() - 1, v = in() - 1;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dp.assign(n, INF);
    dfs(0, -1);
    REP(i,n){
        printf("%d\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 30852
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn=1000+5;

int main()
{
    int n,m;
    cin>>n>>m;
    ll ans=1900*m+100*(n-m);
    while(m){
        ans*=2LL;
        m--;
    }
cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int x;
    cin>>x;
    vi dp(x+200);
    int a[]={100,101,102,103,104,105};
    rep(i,6)dp[a[i]]=1;
    REP(i,100,x){
        rep(j,6){
            dp[i+a[j]]|=dp[i];
        }
    }
    cout<<dp[x]<<endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n; cin>>n;
	int a[100001];
	for(int i=1;i<=n;i++) cin>>a[i];
	int x=1;
	int ans=0;
	while(x!=2)
	{
		ans++;
		int y=a[x];
		a[x]=-1;
		x=y;
		if(x==-1)
		{
			cout<<-1;
			return 0;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 768
T = input()

S = T[::-1]
i = 0
while i <= len(S) - 1:
    if S[i] == "r":
        if S[i:i+7] == "remaerd":
            i += 7
        elif S[i:i+6] == "resare":
            i += 6
        else:
            print("NO")
            exit()
    elif S[i] == "m":
        if S[i:i+5] == "maerd":
            i += 5
        else:
            print("NO")
            exit()
    elif S[i] == "e":
        if S[i:i+5] == "esare":
            i += 5
        else:
            print("NO")
            exit()
    else:
        print("NO")
        exit()
print("YES")


Measured memory_bytes: 40816
#include<bits/stdc++.h>
#define longinf 9223372036854775807LL
#define intinf 2147483647
#define inf 1000000007
#define lol long long
#define in(n,s) insert(n,s)//ノート参照
#define SYOU(x) setprecision(x)
#define abs(x,y) (max(x,y)-min(x,y))
#define mp make_pair
#define fi first
#define se second
using namespace std;
int gcd(int x,int y){//最大公約数
  if(y>x) swap(x,y);
  int r=x%y;
  while(r!=0){
    x=y;
    y=r;
    r=x%y;
  }
  return y;
}
int Lcm(int x,int y){//最小公倍数
  int t=x*y;
  return t/gcd(x,y);
}
lol a,b,c,d,e,g,h,ans=0;
lol dp[111111];
lol i[111111];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >>a;
  for(int n=0;n<a;n++) cin >>i[n],dp[n]=intinf;
  dp[0]=0;
  for(int n=0;n<a-2;n++){
      dp[n+1]=min(dp[n+1],dp[n]+abs(i[n],i[n+1]));
      dp[n+2]=min(dp[n+2],dp[n]+abs(i[n],i[n+2]));
  }
  dp[a-1]=min(dp[a-1],dp[a-2]+abs(i[a-2],i[a-1]));
  cout <<dp[a-1]<<'\n';
  return (0);
}


Measured memory_bytes: 1792
s = input()

ans = 'Yes'
if s != s[::-1]:
  ans ='No'

tmp = s[:(len(s)- 1) // 2]
if tmp != tmp[::-1]:
  ans = 'No'

tmp = s[(len(s)+3) //2 - 1:]
if tmp != tmp[::-1]:
  ans = 'No'

print(ans)

Measured memory_bytes: 3060
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int main(void){
	int N=0,A=0,B=0,D=0;
	double all=0,sumn=0,ksum=0;
	scanf("%d",&N);
	scanf("%d %d",&A,&B);
	scanf("%d",&D);
	all=D/A;
	sumn=A;
	ksum=D;
	double top1[N]={0};
	for(int i=0;i<N;i++)
	{
		scanf("%lf",&top1[i]);
	}
	sort(top1,top1+N,greater<int>());
	for(int i=0;i<N;i++)
	{
		if(all<(top1[i]+ksum)/(B+sumn)){
			all=(top1[i]+ksum)/(B+sumn);
			ksum+=top1[i];
			sumn=sumn+B;
		}
		else{
			break;
		}
	}
	printf("%d\n",(int)all);
	return 0;
}


Measured memory_bytes: 3284
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef pair<int, int> P;

int main(int argc, const char * argv[]) {
  ll n, k;
  cin >> n >> k;
  ll ans = n - ((n/k) *k);
  ans = min(ans, abs(ans - k));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
int main() {
  int R,G,B,N; cin>>R>>G>>B>>N;
  int O=0,P=0;
  int ans=0;
  for(int i=0;R*i<=N;i++){
    O=N-R*i;
    for(int j=0;G*j<=O;j++){
      P=O-G*j;
      if(P%B==0) ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun May 17 20:23:09 2020

@author: Kanaru Sato
"""
import math

a,b,h,m = list(map(int,input().split()))

s = a**2+b**2-2*a*b*math.cos(math.pi*(11*m-60*h)/360)
ans = math.sqrt(s)

print(ans)

Measured memory_bytes: 9516
import java.util.Scanner;

public class Main {
    static char[] s;
    static int[] a;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        s = sc.next().toCharArray();
        a = new int[n+1];
        for (int i = 0; i < n; i++) {
            if(s[i] == 'W') {
                a[i+1] = a[i];
            }
            else {
                a[i+1] = a[i] + 1;
            }
        }
        int min = 100000000;
        for (int i = 0; i < n; i++) {
            int l = i - a[i];
            int r = (a[n] - a[i+1]);
            min =Math.min(min, l+r);
        }
        System.out.println(min);
    }
}


Measured memory_bytes: 31020
use std::io::*;

fn main(){ 
    let (a,b,c) = (read::<i32>(),read::<i32>(),read::<i32>());
    let (d,e,f) = (read::<i32>(),read::<i32>(),read::<i32>());
    let (g,h,i) = (read::<i32>(),read::<i32>(),read::<i32>());
    println!("{}", if a-b==d-e && d-e==g-h && b-c==e-f && e-f==h-i && a-d==b-e && b-e==c-f && d-g==e-h && e-h==f-i {"Yes"} else{"No"})
}
fn read<T: std::str::FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin.bytes().map(|c| c.expect("Error") as char) 
        .skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("Error")
}

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

int main() {
  double a,b;
  double x;

  cin >> a >> b;
  x = (a+b)/2;
  if(x-(int)x >0){
    x = (int)x + 1;
  }
  cout << x << endl;
}


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() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, x; cin >> n >> x;
  int ans = 0, sum = 0;
  for(int i = 0; i <= n && sum <= x; ++i) {
    int y; cin >> y;
    sum += y;
    ++ans;
  } cout << ans;
}
    


Measured memory_bytes: 256
# 辺を消していく操作は難しい
# 操作を逆から考え、辺を足していくと考える
#####################


class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
############################################
N, M = map(int, input().split())
uf = UnionFind(N)
edges = []

for i in range(M):
    A, B = map(int, input().split())
    # 0-indexに直す
    edges.append((A - 1, B - 1))

# n_C_2 = N*(N-1)//2
# [辺が(M-1)本(=1本崩落), ..., 辺が1本(=M-1本崩落), 辺が0本(=M本崩落)]
# [-1]はn_C_2のまま、[-2]から[-M]に向かって逆順に更新していく（辺を増やしていく）

total = [N * (N - 1) // 2 for _ in range(M)]

# -i-1 = -1,-2,...,-(M-1)
# -i-2 = -2,-3,...,-M
for i in range(M - 1):
    u, v = edges[-i - 1]
    # 既に同じ集合に属しているなら、辺を足しても、行き来出来ない組み合わせ数は変わらない（減らない）
    if uf.same(u, v):
        total[-i - 2] = total[-i - 1]
    # uとvが異なる集合に属している場合
    # 辺を張ることで、ダメな組み合わせが(uの要素数)*(vの要素数)だけ減る　（行き来できるようになる）
    else:
        total[-i - 2] = total[-i - 1] - uf.size(u) * uf.size(v)
        uf.unite(u, v)

for t in total:
    print(t)


Measured memory_bytes: 27292
#include <bits/stdc++.h>
/*
#include<algorithm>
#include<array>
#include<cassert>
#include<cmath>
#include<cstdlib>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<typeinfo>
#include<utility>
#include<vector>
*/
#define int long long int
#define double long double
using namespace std;
#define MOD 1000000007
#define INF 1000000000000000007
const int MAX_N = 1 << 17;
#define rep(i, n) for (int(i) = 0, i##_len = (n); (i) < i##_len; (i)++)
#define reps(i, x) for (int(i) = 1; (i) <= (int)(x); (i)++)
#define rrep(i, x) for (int(i) = ((int)(x)-1); (i) >= 0; (i)--)
#define rreps(i, x) for (int(i) = ((int)(x)); (i) > 0; (i)--)
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define pb push_back
#define mp make_pair
#define bit(n) ((int)(1) << (n))
#define all(x) (x).begin(), (x).end()
#define debug(x) std::cout << #x << ": " << (x) << std::endl
#define nint int
using namespace std;

int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};
typedef pair<int, int> pii;
typedef pair<double, double> dop;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct aaa {
    aaa()
    {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} aaaaaaa;


signed main()
{
    int n;
    cin >> n;
    std::vector<int> h(n);
    rep(i,n){
        cin >> h[i];
    }
    int ma = 0;
    int out = 0;
    for(int i = 1; i < n; i++){
        if(h[i] > h[i - 1]){
            chmax(ma,out);
            out = 0;
        } else {
            out++;
        }

    }
    chmax(ma,out);
    cout << ma << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};
int main(void){
  string s;
  cin >> s;

  int N = s.length();
  cout << s[0] << N - 2 << s[N - 1] << endl;
}


Measured memory_bytes: 3620
import sys
sys.setrecursionlimit(10**6)

N = int(input())
S = input()

result = S.count('.')
r = result
def dfs(i):
    global result
    global r
    if i == N:
        return float('inf')
    if S[i] == '#':
        r += 1
    else:
        r -= 1
    result = min(result,r)
    return min(result,dfs(i+1))

print(dfs(0))

Measured memory_bytes: 181480
from collections import deque

N, M = list(map(int, input().split()))

# N個の空の配列
# g[0]は空のまま
path_list = [[] for i in range(N + 1)]

# 繋がっている部屋をメモ
for i in range(M):
    a, b = list(map(int, input().split()))
    path_list[a].append(b)
    path_list[b].append(a)

queue = deque([1])
d = [None] * (N + 1)

while queue:
    # popleft()で先頭の要素を返しつつ削除
    v = queue.popleft()
    # vから行ける全ての部屋について
    for i in path_list[v]:
        if d[i] is None:
            d[i] = v
            queue.append(i)

print("Yes")
# 2番以降の部屋について
for i in d[2:]:
    print(i)


Measured memory_bytes: 34860
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int INF = 1e9;
inline int read(){
	int X = 0,w = 0 ;
	char ch = 0;
	while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
	while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
	return w ? -X : X;
}
int n,a[5005];
int t;
int dp[3005][3005];
int g[5005][5005];
char c;
int calc(int x,int b,int w)
{
	return g[x][b]-g[x-1][b]+g[x][w]-g[x][n]-g[x-1][w]+g[x-1][n];
}
int main()
{
	cin>>n;
	for(int i=1;i<=(n<<1);i++)
	{
		cin>>c>>a[i];
		if(c=='W')
		{
			a[i]+=n;
		}
		for(int j=1;j<i;j++)
		{
			g[a[j]][a[i]]=1;
		}
	}
	for(int i=1;i<=(n<<1);i++)
	{
		for(int j=1;j<=(n<<1);j++)
		{
			g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
		}
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			dp[i][j]=INF;
		}
	}
	dp[0][0]=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(!i and !j)
			{
				continue;
			}
			dp[i][j]=min(i?dp[i-1][j]+calc(i,i,j+n):INF,j?dp[i][j-1]+calc(j+n,i,j+n):INF);
		}
	}
	cout<<dp[n][n]<<endl;
	return 0;
}

Measured memory_bytes: 106752
from collections import Counter

n = int(input())
l = []
for i in range(n):
    l.append(input())

c = Counter(l)
common = c.most_common()
max_count = common[0][1]
tmp = []
for s, num in common:
    if num == max_count:
        tmp.append(s)
    else:
        break

for item in sorted(tmp):
    print(item)


Measured memory_bytes: 120016
// AOJ 1169 The Most Powerful Spell
// 2018.4.17 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define QMAX 15000
typedef struct { char s; int t; char lab[405]; } QUE;
QUE que[QMAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
	que[0] = que[--qsize];
	min_heapify(0);
}

void enq(int s, int t, char *lab)
{
	int i, min;
	QUE qt;

	i = qsize++;
	que[i].s = s, que[i].t = t, strcpy(que[i].lab, lab);
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		i = min;
	}
}

// バッファ入力から数値を得る
char buf[20], *p;
int in()
{
	int n = 0;
	while (*p >= '0') n = 10*n + (*p++ & 0xf);
	p++;
	return n;
}

char hi[42], to[42][42];
char w[42][42]; char lab[42][42][8];
char dist[42][510][510];
char str[510], nstr[510], *ans;

char *dijkstra(int n, int start, int goal)
{
	int i, s, e, t, nt;

	for (s = 0; s < n; s++) for (i = 0; i < 400; i++) {
		dist[s][i][0] = 0x7e, dist[s][i][1] = 0;
	}
	qsize = 0;
	dist[start][0][0] = 0, enq(start, 0, "");
	while (qsize) {
		s = que[0].s, t = que[0].t, strcpy(str, que[0].lab), deq();
		if (strcmp(dist[s][t], str) < 0) continue;
		for (i = 0; i < hi[s]; i++) {
			e = to[s][i], nt = t + w[s][i];
			if (nt > 400) continue;
			memcpy(nstr, str, t), strcpy(nstr+t, lab[s][i]);
			if (strcmp(dist[e][nt], nstr) > 0) {
				strcpy(dist[e][nt], nstr);
				enq(e, nt, nstr);
			}
		}
	}
	str[0] = 0x7e, str[1] = 0, ans = str;
	for (i = 0; i < 400; i++) {
		if (strcmp(ans, dist[goal][i]) > 0) {
			if (i > 300) return NULL;
			ans = dist[goal][i];
		}
	}
	if (*ans == 0x7e) return NULL;
	return ans;
}

int main()
{
	int n, a, s, g, k, x, y;
	char *q;

	while (fgets(p=buf, 20, stdin) && *p != '0') {
		n = in(), a = in(), s = in(), g = in();
		memset(hi, 0, sizeof(hi));
		while (a--) {
			fgets(p=buf, 20, stdin);
			x = in(), y = in();
			k = hi[x]++;
			to[x][k] = y;
			q = lab[x][k]; while (*p > ' ') *q++ = *p++; *q = 0;
			w[x][k] = q - lab[x][k];
		}

		if ((q = dijkstra(n, s, g)) == NULL) puts("NO");
		else puts(q);
	}
	return 0;
}


Measured memory_bytes: 9972
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define PI acos(-1)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}



int main(){
   int a,b,c,k;
   cin>>a>>b>>c>>k;

   bool f=false;

   rep(i,k){
      if(a>=b) {
         b*=2; 
         continue;
      }
      if(b>=c) c*=2;
   }
   if(a<b && b<c) cout<<"Yes";
   else cout<<"No";



return 0;
}


Measured memory_bytes: 3624
#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>;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x%mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint& operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		assert(n < mod);
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
}c(200005);


//m^n
mint f(int m, int n) {
	if (0 == n) {
		return 1;
	}
	mint x = f(m, n / 2);
	x *= x;
	if (1 == n % 2) {
		x *= (mint)m;
	}
	return x;
}
// nCa
mint choose(long long n, long long a) {
	mint x = 1;
	mint y = 1;
	for (int m = 0; m < a; ++m) {
		x *= (mint)(n - m);
		y *= (mint)(a - m);
	}
	return x / y;
}
// nPk
mint nPk(int n, int a) {
	mint ret = choose(n, a);
	for (int n = 1; n <= a; ++n) {
		ret *= n;
	}
	return ret;
}


int main() {
	long long N, M,K;
	cin >> N >> M >> K;
	mint ans = choose(N * M - 2,K-2);
	mint anssub = 0;
	for (int n = 1;n<=N-1; ++n) {
		anssub += (mint)M*M*(N-n)*n;
	}
	for (int m = 1; m <= M - 1; ++m) {
		anssub += (mint)N*N*(M - m)*m;
	}
	ans *= anssub;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 6140
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cctype>
#include <cmath>
#include <map>
#include <set>
#define rep(i, m, n) for (int i = m; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define ll long long
#define ull unsigned long long
#define push(a) push_back(a)
#define pop(a) pop_back(a)
#define debug(x) cout << #x << ": " << x << endl
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define PI 3.14159265358979
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int main(){
    int n;
    string s;
    set<string> a;
    cin>>n;
    rep(i,0,n){
        cin>>s;
        a.insert(s);
    }
    if(a.size()==4){
        cout<<"Four"<<endl;
    }else{
        cout<<"Three"<<endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector1d(type,name,...) vector<type>name(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll updivide(ll a,ll b){if(a%b==0) return a/b;else return (a/b)+1;}

int main(){
    INT(n,k);
    string s;
    cin>>s;
    int d=0;
    vector<int> line;
    for(int i=0;i<n;i++){
        d=i;
        while(i+1<n&&s[i]==s[i+1])i++;
        line.push_back(i-d+1);
    }
    vector<int> sum;
    sum.push_back(0);
    for(int i=1;i<=line.size();i++){
        sum.push_back(sum[i-1]+line[i-1]);
    }
    int m=sum.size(),ans=0,l,r;
    if(s[0]=='0'){
        ans=sum[min(2*k,m-1)];
        for(l=2;l<m;l+=2){
            r=min(l+2*k,m-1);
            ans=max(ans,sum[r]-sum[l-1]);
        }
    }else{
        for(l=1;l<m;l+=2){
            r=min(l+2*k,m-1);
            ans=max(ans,sum[r]-sum[l-1]);
        }
    }
    out(ans);
}

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

int main() {
    int X;
    cin >> X;
    int N = 1000;
    vector<ll> A(N);
    for (ll i = 0; i < (ll)N; ++i) {
        A[i] = i*i*i*i*i;
    }
    int a = 0, b = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (A[i] + A[j] == X) a = i, b = -j;
            if (A[i] - A[j] == X) a = i, b = j;
        }
    }
    cout << a << " " << b << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_p(x) cerr<<#x": "<<(x).first<<' '<<(x).second<<endl
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<endl;}
#define all(v) v.begin(), v.end()
#define fi first
#define se second
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

template<typename T1, typename T2>
ostream& operator <<(ostream &out, const pair<T1, T2> &item) {
	out << '(' << item.first << ", " << item.second << ')';
	return out;
}

template <typename T>
ostream& operator <<(ostream &out, const vector<T>& v) {
	for(const auto &item : v) out << item << ' ';
	return out;
}

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

	int n;
	string s;
	map<string, int> cnt;

	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> s;
		++cnt[s];
	}

	int mx = 0;
	for(const auto &item : cnt) mx = max(mx, item.se);

	for(const auto &item : cnt) if(item.se == mx) cout << item.fi << '\n';

	return 0;
}



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

typedef long long ll;
const int maxn=1e6+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=998244353;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int ll

#ifdef HNO2
#define IOS
#else
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#endif // HNO2

int ppow(int x,int y)
{
    if (y==0) return 1;
    int ret=ppow(x,y/2);
    ret=ret*ret%mod;
    if (y&1) ret=ret*x%mod;
    return ret;
}

int p[maxn],invp[maxn];

inline int C(int x,int y)
{
    return p[x]*invp[y]%mod*invp[x-y]%mod;
}

int32_t main()
{
    IOS
    p[0]=invp[0]=1;
    for (int i=1;i<=200000;i++)
    {
        p[i]=p[i-1]*i%mod;
        invp[i]=ppow(p[i],mod-2);
    }
    int n,m,k;
    cin>>n>>m>>k;

    int ans=0;
    for (int i=0;i<=k;i++)
        ans=(ans+C(n-1,n-i-1)*m%mod*ppow(m-1,n-i-1)%mod)%mod;
    cout<<ans<<endl;
}



Measured memory_bytes: 6764
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <set>
#include <deque>
#include <map>
#include <bitset>
#include <functional>

#define INF 10000000000
using namespace std;
using P = pair<long, long>;

int main(){
    long long n, m;
	cin >> n >> m;

	vector<long long>graph[100010];

	long long i;
	for(i = 0; i < m; i++){
		long long a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	long long used[100010];
	for(i = 0; i < 100010; i++){
		used[i] = -1;
	}

	queue<pair<long long, long long>> q;
	q.push({-1, 0});
	while(!q.empty()){
		long long before = q.front().first;
		long long now = q.front().second;
		q.pop();

		if(used[now] != -1) continue;

		used[now] = before;

		for(long long j = 0; j < graph[now].size(); j++){
			q.push({now, graph[now][j]});
		}
	}

	long long flag = 1;
	for(i = 1; i < n; i++){
		if(used[i] == -1){
			flag = 0;
			break;
		}
	}

	if(flag == 0){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
		for(i = 1; i < n; i++) cout << used[i]+1 << endl;
	}
}

Measured memory_bytes: 18508
#include <iostream>
#include <algorithm>
#define rng(x1, y1, x2, y2) (sum[y2][x2] + sum[y1][x1] - sum[y2][x1] - sum[y1][x2])
using namespace std;
int H, W, ra, o, a[40][40], sum[40][40], dp[40][40][40][40];
int solve(int x1, int y1, int x2, int y2) {
	if (dp[y1][x1][y2][x2] != -1) return dp[y1][x1][y2][x2];
	int rng_ = rng(x1, y1, x2, y2);
	int ret = 1000000 + rng_;
	for (int i = x1 + 1; i < x2; i++) {
		int petl = rng(x1, y1, i, y2);
		int petr = rng(i, y1, x2, y2);
		if (min(petl, petr) >= o) {
			int resl = solve(x1, y1, i, y2);
			int resr = solve(i, y1, x2, y2);
			int res = (resl + resr) / 1000000 * 1000000 + min(resl % 1000000, resr % 1000000);
			ret = max(ret, res);
		}
	}
	for (int i = y1 + 1; i < y2; i++) {
		int petl = rng(x1, y1, x2, i);
		int petr = rng(x1, i, x2, y2);
		if (min(petl, petr) >= o) {
			int resl = solve(x1, y1, x2, i);
			int resr = solve(x1, i, x2, y2);
			int res = (resl + resr) / 1000000 * 1000000 + min(resl % 1000000, resr % 1000000);
			ret = max(ret, res);
		}
	}
	return dp[y1][x1][y2][x2] = ret;
}
int main() {
	while (cin >> H >> W >> ra, H) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) cin >> a[i][j];
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + a[i][j];
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				for (int k = i + 1; k <= H; k++) {
					for (int l = j + 1; l <= W; l++) dp[i][j][k][l] = -1;
				}
			}
		}
		o = sum[H][W] - ra;
		int ret = solve(0, 0, W, H);
		cout << ret / 1000000 << ' ' << ret % 1000000 - o << endl;
	}
}

Measured memory_bytes: 9004
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,sum=0,tmp=0,diff=1e9;cin>>n;
  lvector W(n);rep(i,n) {cin>>W[i];sum+=W[i];}
  rep(i,n) {
    tmp+=W[i],sum-=W[i];
    diff=min(diff,abs(tmp-sum)); 
  }
  print(diff);
  return 0;
}

Measured memory_bytes: 3628
//containing t test cases
#include<bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define mkp make_pair
#define fi first
#define se second
#define ll long long
#define scan(n) ll a[n]; for(ll i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(ll i=x;i<y;i++)
//#define int long long
using namespace std;
typedef vector<int>vi ;
typedef vector<ll>vll ;
typedef vector<vector<ll> >vvl ; 
typedef pair<ll,ll> pll ;
typedef vector<pair<ll,ll> > vpll;
/*vi adj[200005];
ll vis[200005];
ll parent[200005];
ll level[200005];
ll arr[200005];
ll size[200005];*/
//endl mut bhool!
int main()
{
	fast;
	int test=1;
	//cin>>test;
	while(test--)
	{
		ll n,k;
		cin>>n>>k;
		ll x,d;
		ll vis[n+1]={0};
		for(ll i=1;i<=k;i++)
		{
			cin>>d;
			for(ll j=1;j<=d;j++)
			{
				cin>>x;
				vis[x]=1;
			}
		}		
		ll cnt=0;
		for(ll i=1;i<=n;i++)
		{
			if(vis[i]==0)
				cnt++;
		}
		cout<<cnt;
	}
	return 0;
}
/*
cout<<"YES"<<endl;
cout<<"NO"<<endl;
*/

Measured memory_bytes: 3656
using System.Collections.Generic;
using System.Linq;
using System;

public class Runner
{
    public int rclass { get; set; }
    public int rno { get; set; }
    public decimal rtime { get; set; }
}

public class hello
{
    public static void Main()
    {
        var runners = new List<Runner>();
        var nokori = new List<Runner>();
        var RClass = new int[] { 0, 1, 2 };
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 8; j++)
            {
                string[] line = Console.ReadLine().Trim().Split(' ');
                runners.Add(new Runner { rclass = i, rno = int.Parse(line[0]), rtime = decimal.Parse(line[1]) });
            }
        foreach (var c in RClass)
        {
            var rr = runners.Where(x => x.rclass == c).OrderBy(y => y.rtime).Take(2);
            foreach (var x in rr)
                Console.WriteLine("{0} {1}", x.rno, x.rtime);
            var rrr = runners.Where(x => x.rclass == c).OrderByDescending(y => y.rtime).Take(6);
            foreach (var x in rrr)
                nokori.Add(x);
        }
        var res = nokori.OrderBy(x => x.rtime).Take(2);
        foreach (var x in res)
        {
            Console.WriteLine("{0} {1}", x.rno, x.rtime);
        }
    }
}

Measured memory_bytes: 10188
#p gets.to_i ** 3

=begin
n = gets.to_i

a = gets.split(" ").map{|x| x.to_i}
b = gets.split(" ").map{|x| x.to_i}
c = gets.split(" ").map{|x| x.to_i}

temp = -1
sum = 0
n.times do |i|
  sum += c[a[i] - 2] if a[i] == temp + 1
  temp = a[i]
  sum += b[a[i] - 1]
end
p sum
=end

n = gets.to_i
b = Array.new()
b += gets.split(" ").map{|x| x.to_i}

sum = b[0]

for i in 0..(n - 2) do
  sum += b[i..(i + 1)].min
end
p sum


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

int main() {
  int N, K, x;
  cin >> N >> K;
  x = 1;
  
  for (int i = 0; i < N; i++){
    if (x * 2 < x + K){
      x = x * 2;
    }
    else {
      x = x + K;
    }
  }
  
  cout << x << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mod int(1e9+7)
#define N int(2e5+100)
#define ll long long int
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define si second
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int a,b,c,d,i=0;
   cin>>a>>b>>c>>d;
   while(a>0&&c>0){
      if(i%2)
         a-=d;
      else
         c-=b;
      i++;
   }
   cout<<((a<=0)?"No\n":"Yes\n");
   return 0;
}


Measured memory_bytes: 3652
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


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

  int x, y;
  int ans = 2e9;
  cin >> x >> y;
  int t = 0;
  if (x > y) {
    if (abs(x) >= abs(y)) {
      x = -x;
      t = 1;
    } else if (abs(y) > abs(x)) {
      y = -y;
      t = 1;
    }
  }
  if (x <= y) {
    ans = min(y - x, ans);
    if (-x <= y) {
      ans = min(y + x + 1, ans);
    }
    if (x <= -y) {
      ans = min(-y - x + 1, ans);
    }
  }
  ans += t;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

PY = []
for i in range(M):
    x = list(map(int, input().split()))
    x.append(i)
    PY.append(x)
    
PY = sorted(PY, key=lambda x: (x[0], x[1]))
num = PY[0][0]
ans = []
count = 1
for i in range(M):
    if PY[i][0] == num:
        tmp = [num, count, PY[i][2]]
        ans.append(tmp)
        count += 1
    else:
        num = PY[i][0]
        count = 1
        tmp = [num, count, PY[i][2]]
        ans.append(tmp)
        count += 1

ans = sorted(ans, key=lambda x: x[2])

for i in range(M):
    prefecture = str(ans[i][0])
    number = str(ans[i][1])
    print(prefecture.zfill(6) + number.zfill(6))

Measured memory_bytes: 43108
// B - Choose Integers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int main() {
	int A, B, C;
	cin >> A >> B >> C;

	string ans = "NO";

	for (int i=1; i<=B; i++) {
		if ((A * i) % B == C) ans = "YES";
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import numpy as np

MOD = 10**9 + 7

N, k = map(int, input().split())

n = N+1
ans = 0
a = np.arange(n)
l = np.cumsum(a)
r = np.cumsum(a[::-1])[::-1]
l %= MOD
r %= MOD
for i in range(k, n+1):
    ans += r[-i] - l[i-1] +1
    ans %= MOD
print(ans)

Measured memory_bytes: 31352
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

int main() {
	vector<vector<int>>a(3, vector<int>(3));

	for (int i = 0; i < 3; i++) {
		cin >> a.at(i).at(0) >> a.at(i).at(1) >> a.at(i).at(2);
	}

	int N;
	cin >> N;

	vector<int> b(N);
	for (int i = 0; i < N; i++) {
		cin >> b.at(i);
	}

	for (int i = 0; i < N; i++) {
		for (int n = 0; n < 3; n++) {
			for (int m = 0; m < 3; m++) {
				if (b.at(i) == a.at(n).at(m)) {
					a.at(n).at(m) = 0;
				}
			}
		}
	}

	bool ans = false;

	for (int i = 0; i < 3; i++) {
		if (a.at(i).at(0) == 0 && a.at(i).at(1) == 0 && a.at(i).at(2) == 0) {
			ans = true;
			break;
		}
		if (a.at(0).at(i) == 0 && a.at(1).at(i) == 0 && a.at(2).at(i) == 0) {
			ans = true;
			break;
		}
	}

	if (a.at(0).at(0) == 0 && a.at(1).at(1) == 0 && a.at(2).at(2) == 0) {
		ans = true;
	}

	if (a.at(0).at(2) == 0 && a.at(1).at(1) == 0 && a.at(2).at(0) == 0) {
		ans = true;
	}

	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
N = int(input())
A_list = list(map(int, input().split()))
ans = 10000000000
cum_sum1 = 0
cum_sum2 = sum(A_list)
for i in range(N-1):
    cum_sum1 += A_list[i]
    cum_sum2 -= A_list[i]
    tmp = abs(cum_sum1-cum_sum2)
    if tmp < ans:
        ans = tmp
print(ans)

Measured memory_bytes: 26220
#include <bits/stdc++.h>
using namespace std;
#define mid ((s + e) / 2)
#define makefast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define comp(x) (lower_bound(vec.begin(), vec.end(), x) - vec.begin())
long long M = 1e9 + 7;
//>>>>>>>>>>>>>>>>>>>

const int N = 1e6 + 7;

int n;
int x[N];
int a[N];
int ord[N];
int main() {
	makefast;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
		a[x[i]] = i;
		ord[i] = i;
	}
	sort (ord + 1, ord + n + 1, [](int v, int u) {
		return x[v] < x[u];		
	});
	int pnt = n * n;
	for (int i = n; i >= 1; i--) {
		int v = ord[i];
		for (int j = 1; j <= n - v; j++) {
			while (a[pnt]) {
				pnt--;
			}
			if (pnt < x[v]) {
				cout << "No";
				return 0;
			}
			a[pnt] = v;
		}
	}
	pnt = 1;
	for (int i = 1; i <= n; i++) {
		int v = ord[i];
		for (int j = 1; j <= v - 1; j++) {
			while (a[pnt])
				pnt++;
			if (x[v] < pnt) {
				cout << "No";
				return 0;
			}
			a[pnt] = v;
		}
	}
	cout << "Yes" << '\n';
	for (int i = 1; i <= n * n; i++)
		cout << a[i] << ' ';

}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define INF 1e9;
using namespace std;
typedef long long ll;

vector<bool> prime_table(int n) {
  vector<bool> prime(n + 1, true);
  if (n >= 0) prime[0] = false;
  if (n >= 1) prime[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (!prime[i]) continue;
    for (int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
int main() {
  int NUM = 100500;

  auto t = prime_table(NUM);

  ll sum[NUM];

  sum[0] = 0;
  sum[1] = 0;

  FOR(i, 2, NUM + 1) {
    sum[i] = sum[i - 1];
    if ((i + 1) % 2 == 0) {
      if (t[i] && t[(i + 1) / 2]) {
        sum[i]++;
      }
    }
  }

  ll Q;
  cin >> Q;
  REP(i, Q) {
    ll l, r;
    cin >> l >> r;
    cout << sum[r] - sum[l - 1] << endl;
  }

  return 0;
}

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

#define MP make_pair
#define A first
#define B second

#define PB push_back

#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define FOR(i, n) FR(i, 0, n)

//typedef long long ll;

const int MAXN = 1234567;

pair<int, int> lis[MAXN];
int n, n1;

priority_queue<int> Q;
long long tot;
long long num;

int main() {
	scanf("%d", &n);
	FOR(i, n) {
		int t, h;
		scanf("%d%d", &h, &t);
		lis[i] = MP(h + t, t);
	}
	sort(lis, lis + n);
	num = 0;
	tot = 0;
	long long ans = 0;

	FOR(i, n) {
		int t = lis[i].B;
		int h = lis[i].A;
		tot += t;
		Q.push(t);
		num++;
		while(tot > h) {
			tot -= Q.top();
			num--;
			Q.pop();
		}
		ans = max(ans, num);
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 9984
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
ll dp[2010][2010];
const ll MOD = 1000000007;

void _main()
{
    int N, M;
    cin >> N >> M;
    vector<int> S(N), T(M);
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, M) cin >> T[i];
    rep(i, 1, N + 1) rep(j, 1, M + 1)
    {
        if (S[i - 1] == T[j - 1])
        {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] + 1) % MOD;
        }
        else
        {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD;
            while (dp[i][j] < 0) dp[i][j] += MOD;
        }
    }
    cout << (dp[N][M] + 1) % MOD << endl;
}


Measured memory_bytes: 31744
#!/usr/bin/env pypy3


def solve(n, xs):
    res = [sum(abs(xs[i + 1] - xs[i]) for i in range(n))
           + abs(xs[n] - xs[0])] * (n + 1)
    res[0] = None
    for j in range(1, n + 1):
        if j <= n - 1:
            res[j] += abs(xs[j + 1] - xs[j - 1])
            res[j] -= abs(xs[j] - xs[j - 1]) + abs(xs[j + 1] - xs[j])
        else:
            res[j] += abs(xs[0] - xs[n - 1])
            res[j] -= abs(xs[n] - xs[n - 1]) + abs(xs[0] - xs[n])
    return res


def main():
    n = int(input())
    xs = [0]
    xs.extend(int(x) for x in input().split())
    res = solve(n, xs)
    for r in res[1:]:
        print(r)


if __name__ == '__main__':
    main()


Measured memory_bytes: 63724
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int w, h, x, y; cin>>w>>h>>x>>y;
	printf("%.10lf ", (double)w*(double)h/2.0);
	if(x*2==w && y*2==h) cout<<1<<endl;
	else cout<<0<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#include <stdlib.h>
 
int main(void){
	int n, k, i;
	int p[200000];
	int a[200000];
	scanf("%d %d", &n, &k);
	for(i=0; i<n; i++){
		scanf("%d", p+i);
	}
	a[0]=p[0];
	for(i=1; i<k; i++){
		a[i] = a[i-1]+p[i];
	}
	int max=a[k-1];
	for(i=k; i<n; i++){
		a[i] = a[i-1]+p[i]-p[i-k];
		if(a[i]>max) max=a[i];
	}
	long ans = ((long)max)+k;
	if(ans%2==0) printf("%ld\n", ans/2);
	else printf("%ld.5\n", ans/2);
}

Measured memory_bytes: 1664