akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
int main()
{
    ll a, b, k;
    cin >> a >> b >> k;
    if (a - k < 0)
    {
        cout << 0 << " " << max(ll(0), b - k + a);
    }
    else
        cout << a - k << " " << b;
}

Measured memory_bytes: 256
H,W,K = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = [[0]*W for _ in range(H)]

for i in range(H):
    if "#" in S[i]:
        idx = i
        break
        
num = 1
for i in range(idx, H):
    if "#" in S[i]:
        c = -1
        for j in range(W):
            if S[i][j] == "#":
                c += 1
            ans[i][j] = str(num + max(0, c))
        num += c+1
    else:
        for j in range(W):
            ans[i][j] = ans[i-1][j]
        
for i in range(idx-1, -1, -1):
    if "#" in S[i]:
        c = -1
        for j in range(W):
            if S[i][j] == "#":
                c += 1
            ans[i][j] = str(num + max(0, c))
        num += c+1
    else:
        for j in range(W):
            ans[i][j] = ans[i+1][j]
        
for i in range(H):
    print(" ".join(ans[i]))

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


#define f(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define char_f(i,a) for(int i=(int)(a);(char)s[i]!='\0';i++)
#define rf(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define llf(i,a,b) for(long long int i=(long long int)(a);i<=(long long int)(b);i++)
#define llrf(i,a,b) for(long long int i=(long long int)(a);i>=(long long int)(b);i--)



#define ll long long
#define fi first
#define se second
#define pb push_back
#define pop pop_back
#define mem(ara) memset((ara),0,sizeof(ara))
#define memn(ara) memset((ara),-1,sizeof(ara))
#define bb begin()
#define ee end()
#define em emplace
#define eb emplace_back





#define si set<int>
#define sd set<double>
#define sll set<long long int>
#define ss set<string>
#define sc set<char>

#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pcl pair<char,long long int>
#define plc pair<long long int,char>

#define pss pair<string,string>
#define pcc pair<char,char>

#define pis pair<int,string>
#define psi pair<string,int>
#define pls pair<long long int,string>
#define psl pair<string,long long int>
#define pdd pair<double,double>
#define pcs pair<char,string>
#define psc pair<string,char>



#define vi  vector<int>
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vii vector<pii>



#define mod 1000000007
#define mx (1<<30)-1
#define llmx (1ll<<62)
#define n_size 100005
#define g_size 10000005
double PI=acos(-1);



///unsigned int uMAX=4294967295;
///unsigned ll int ullMAX=18446744073709551615;





int arr[g_size];



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

	int n,m,T,res;

	int maxi=-mx,mini=mx,count=0;

	int i,j,k;

	bool flag;

	string s1,s2;

	char s[100000];

	int ara[n_size],ara2[n_size];

	cin>>n;
	cout<<"ABC"<<n<<endl;



}


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

typedef long long ll;
ll MOD = 1e9+7;

int main()
{
	int r,g,b,n;
	ll ans=0;
	cin>>r>>g>>b>>n;
	for(int i=0;i<3001;i++)
	{
		for(int j=0;j<3001;j++)
		{
			int bb=n-(i*r+j*g);
			if(bb>=0 && bb%b==0)
				ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int H, W;
int cn = 0;
int c[10][10];
int A[210][210];
vector<vector<int>> dp(10, vector<int>(10, 100000000));

void warshall_floyd(){
  for(int k = 0; k < 10; k++){
    for(int i = 0; i < 10; i++){
      for(int j = 0; j < 10; j++){
        c[i][j]  = min(c[i][j], c[i][k] + c[k][j]);
      }
    }
  }
}

int main(){
  cin >> H >> W;

  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
      cin >> c[i][j];
    }
  }

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> A[i][j];
    }
  }

  warshall_floyd();

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(A[i][j] < 0) continue;
      cn += c[A[i][j]][1];
    }
  }

  cout << cn << endl;

 

}

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

struct Node{
  int key;
  Node *right, *left, *parent;
};

Node *root,*NIL;

Node * find(Node *u,int k){
  while(u != NIL && k != u->key){
    if(k < u->key) u = u -> left;
    else u = u->right;
  }
  return u;
}

void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z=(Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y=x;
    if(z->key < x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }
  z->parent = y;
  if(y == NIL){
    root = z;
  }
  else {
    if(z->key < y->key){
      y->left = z;
    }
    else{
      y->right = z;
    }
  }
}

void inorder(Node *u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node *u){
  if(u == NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n,i,x;
  string com;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    cin >> com;
    if(com[0] == 'f'){
      scanf("%d",&x);
      Node *t = find(root,x);
      if(t != NIL)printf("yes\n");
      else printf("no\n");
    }
    else if(com == "insert"){
      scanf("%d",&x);
      insert(x);
    }
    else if(com == "print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}





Measured memory_bytes: 22060
fun main(args: Array<String>) {
    abc072c()
}

fun abc072c() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(" ").map { it.toInt() }
        .sorted().toIntArray()

    val grouped = aList.groupBy { it }

    val answer = grouped.map {
        (grouped[it.key - 1]?.size ?: 0) +
                it.value.size +
                (grouped[it.key + 1]?.size ?: 0)
    }.max()

    println(answer)
}


Measured memory_bytes: 58128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define SZ(x) ((int)(x).size())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll X, K, D; cin >> X >> K >> D;
    X = abs(X);
    if(X / D >= K){
        cout << (X - D*K);
    }
    else{
        ll c1 = X - (X / D * D);
        ll c2 = abs(X - ((X/D+1) * D));
        if((K-(X/D))&1)
            cout << c2;
        else
            cout << c1;
    }
}

Measured memory_bytes: 3664
S = list(input())
is_ok = False
for n, s in enumerate(S):
    if n % 2 == 0:
        if s == "R" or s == "U" or s == "D":
            is_ok = True
        else:
            is_ok = False
            break
    if n % 2 == 1:
        if s == "L" or s == "U" or s == "D":
            is_ok = True
        else:
            is_ok = False
            break
if is_ok:
    print("Yes")
else:
    print("No")

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

int main() {
  int64_t X, K, D;
  cin >> X >> K >> D;
  int64_t quo = abs(X) / D;
  int64_t rem = abs(X) % D;
  if (quo >= K){
    if (X >= 0) cout << X - K * D << endl;
    else cout << abs(X + K * D) << endl;
  }
  else if ((K - quo) % 2 == 0) cout << rem << endl;
  else cout << D - rem << endl;
}


Measured memory_bytes: 3632
#include<stdio.h>
char check(int test1 , int test2 , int test3) {
	int sumScore = test1 + test2;
	if (test1 == -1 || test2 == -1) {
		return 'F';
	}
	if (sumScore >= 80) {
		return 'A';
	}
	if (sumScore >= 65) {
		return 'B';
	}
	if (sumScore >= 50) {
		return 'C';
	}
	if (sumScore >= 30) {
		if (test3 >= 50) {
			return 'C';
		} else {
			return 'D';
		}	
	}
	return 'F';
}
int main () {
	int test1 , test2 , test3;
	while(1) {
		scanf("%d %d %d" , &test1 , &test2 , &test3);
		if (test1 == -1 && test2 == -1 && test3 == -1) break;
		printf("%c\n" , check(test1 , test2 , test3));
	}
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
using namespace std;
int main(){
	int a,b,c,i,count=0,siki;
	cin>>a>>b>>c;
	for(i=a;i<=b;i++){
		siki=c%i;
		if(siki==0){
		count++;
		}
	}
	cout<<count<<endl;
return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> V(N);
  REP(i, N) cin >> V[i];
  vector<int> C(N);
  REP(i, N) cin >> C[i];
  int ans = 0;
  for(int i = 0; i < N; i++) {
    if(V[i] > C[i]) { ans += V[i] - C[i]; }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int a, b;
		a = sc.nextInt();
		b = sc.nextInt();
		sc.close();
		int c = a + b;
		
		if(a % 3 == 0 || b % 3 == 0 || c % 3 == 0)
			System.out.println("Possible");
		else
			System.out.println("Impossible");
	}	
}


Measured memory_bytes: 20948
S = input()

a = int(S[:2])
b = int(S[2:])

if a in range(1, 13):
    if b in range(1, 13):
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if b in range(1, 13):
        print("YYMM")
    else:
        print("NA")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using Graph= vector<vector<int>>;

void DFS(const Graph gph, int from, int to, unordered_map<int, int> *pre, unordered_map<int, int> *low, set<pair<int, int>> *bridges){
  int pre_to= pre->size();
  pre->operator[](to)= pre_to;
  low->operator[](to)= pre_to;

  for(auto ngh:gph.at(to)){
    if(ngh != from){
      if(!pre->count(ngh)){
        DFS(gph, to, ngh, pre, low, bridges);
      }
      low->at(to)= min(low->at(to), low->at(ngh));
    }
  }
  if(from != -1 && pre->at(to)==low->at(to)){
    bridges->insert(make_pair(from, to));
  }
}

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

  Graph gph= vector<vector<int>>(N);
  int v1,v2;
  for(int j=0; j<M; j++){
    cin >> v1 >> v2;
    v1--; v2--; // 1-indexed -> 0-indexed
    gph.at(v1).emplace_back(v2);
    gph.at(v2).emplace_back(v1);
  }

  unordered_map<int, int> pre;
  unordered_map<int, int> low;
  set<pair<int, int>> bridges;
  DFS(gph, -1, 0, &pre, &low, &bridges);

  int ans= bridges.size();
  cout << ans << endl;
}

Measured memory_bytes: 3688
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, k; cin >> n >> k;
  set<int> snuke;
  for(int i = 0, d; i < k; ++i){
    cin >> d;
    for(int j = 0, temp; j < d; ++j){
      cin >> temp;
      snuke.insert(temp);
    }
  }
  cout << n - snuke.size() << endl;
}

Measured memory_bytes: 3628
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();

        int ans = Integer.MAX_VALUE;
        int tmp = 0;
        for(int i = 0; i <= 100000; i++){
            tmp = i * 2*C + Math.max(0, X - i) * A + Math.max(0, Y - i) * B;
            ans = Math.min(tmp, ans);
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
i = 0
x = []
y = []
while 1:
    try:
        a,b = map(float,input().split(","))
        x.append(a)
        y.append(b)
    except EOFError:
        break

S = 0
for i in range(len(x)-2):
    a = ((x[0]-x[i+1]) ** 2 + (y[0]-y[i+1]) ** 2) ** 0.5
    b = ((x[0]-x[i+2]) ** 2 + (y[0]-y[i+2]) ** 2) ** 0.5
    c = ((x[i+1]-x[i+2]) ** 2 + (y[i+1]-y[i+2]) ** 2) ** 0.5
    z = (a + b + c)/2
    S += (z * (z - a) * (z - b) * (z - c)) ** 0.5
print(S)


Measured memory_bytes: 5640
// problem: "https://atcoder.jp/contests/abc152/tasks/abc152_b"

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ll a,b;
    cin>>a>>b;

    ll m = min(a,b);
    ll M = max(a,b);

    M--;
    while(M--)
        m = 10*m + m%10;

    cout<<m;
    
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		int c = Integer.parseInt( a + "" + b );
		
		int d = (int) Math.sqrt(c);
		
		System.out.println( c == d * d ? "Yes" : "No" );
	}
}


Measured memory_bytes: 21716
N,K= map(int,input().split())
H = [0]+list(map(int,input().split()))+[0]
dp = [[0]*(K+2) for i in [0]*(N+2)]
for i in range(1,N+2):
    for j in range(K+1):
        dp[i][j] = min([dp[i-k][j-k+1] + max(0,H[i]-H[i-k]) for k in range(1,min(j+1,i)+1)])
print(dp[N+1][K])



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

using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;

const int N = 1e5 + 5;

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> x;
  for (int i = 1 ; i <= n ; i++)
    cin >> a[i];
  sort(a + 1,a + n + 1);
  for (int i = 1 ; i <= n ; i++) {
    if ((a[i] += a[i - 1]) > x) break;
    if (n == i && a[i] != x) break;
    ans = i;
  }
  cout << ans << endl;
}

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

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    int n, w;
    cin >> n >> w;
    vector<pair<int, int> > value_weights (n, pair<int, int> (0, 0));
    for (int i = 0; i < n; i++)
        cin >> value_weights[i].first >> value_weights[i].second;
    vector<int> memoization (w+1, -1);
    memoization[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = w; j >= value_weights[i].second; j--)
        {
            memoization[j] = max(memoization[j], memoization[j-value_weights[i].second] + value_weights[i].first);
        }
    }
    cout << *max_element(memoization.begin(), memoization.end()) << endl;
    return 0;
}


Measured memory_bytes: 3236
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
int main() {
	string a, b, c;
	cin >> a >> b >> c;
	char n = 'a';
	while (1) {
		if (n == 'a') {
			if (a.size() == 0) {
				cout << 'A' << endl;
				return 0;
			}
			else {
				n = a[0];
				a = a.substr(1);
			}
		}
		if (n == 'b') {
			if (b.size() == 0) {
				cout << 'B' << endl;
				return 0;
			}
			else {
				n = b[0];
				b = b.substr(1);
			}
		}
		if (n == 'c') {
			if (c.size() == 0) {
				cout << 'C' << endl;
				return 0;
			}
			else {
				n = c[0];
				c = c.substr(1);
			}
		}
	}
	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

int g[200005] = {0};

bool check(int n){
    rep(i,n){
        if(g[i] >= 2) return true;
    }
    return false;
}

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

    rep(i,m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(a == 0) g[b]++;
        else if(b == n - 1) g[a]++;
    }
    cout << (check(n) ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}


Measured memory_bytes: 1024
import numpy as np
from time import time
start = time()
def scoring(c,s,t):
    score = 0
    from_last = np.zeros(26)
    for i in range(s.shape[0]):
        from_last = from_last+1
        score += s[i,t[i]-1]
        from_last[t[i]-1] = 0
        score = score - (c*from_last).sum()
    return score



D = int(input())
c = list(map(int,input().split()))
s = np.empty((D,26))
for i in range(D):
    s[i,:] = np.array(list(map(int,input().split())))

from_last = np.zeros(26)
t = []
for i in range(D):
    from_last = from_last+1
    chosen = (s[i,:]-c*from_last).flatten().argmax()+ 1
    from_last[chosen-1] = 0
    t.append(chosen)

freq = np.zeros(26)
for i in t:
    freq[i-1] += 1
w = c*(365-freq)
num = np.arange(1,27)
score = scoring(c,s,t)
while time()-start < 1.85:
    i = np.random.randint(D)
    old = t[i]
    t[i] = np.random.choice(num, p = w/w.sum())
    new_score = scoring(c,s,t)
    if new_score > score:
        score = new_score
        w[t[i]-1] -= c[t[i]-1]
        w[old-1] += c[old-1]
    else:
        t[i] = old


for i in t:
	print(i)


Measured memory_bytes: 27516
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let it = stdin.lock().bytes().map(|c| c.unwrap() as char);
    let (fs, ft) = (|c: &char| c.is_whitespace(), |c: &char| !c.is_whitespace());
    let token = it.skip_while(fs).take_while(ft).collect::<String>();
    token.parse().ok().unwrap()
}
#[allow(dead_code)]
fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    f(std::io::BufWriter::new(out.lock()));
}
#[allow(unused_macros)]
macro_rules! debug {
    ($($var:expr),*) => { #[cfg(debug_assertions)] {
        $({ match &$var { v => eprint!("{}={:?} ", stringify!($var), v) } })*
        eprintln!();
    }};
}

fn main() {
    let n: usize = input();
    let a: Vec<i32> = (0..n).map(|_| input()).collect();

    let mut sum = 0;
    let mut r = 0;
    let mut ans = 0;
    for l in 0..n {
        while r < n && sum + a[r] == sum ^ a[r] {
            debug!(l, r, sum);
            sum += a[r];
            r += 1;
        }
        sum -= a[l];
        ans += r - l;
        debug!(ans, l, r, sum);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N,D, count = 0;
  cin >> N >> D;
  vector<long long> X(N),Y(N);
  for(int i=0;i<N;i++){
    cin >> X.at(i) >> Y.at(i);
    if(X.at(i)*X.at(i) + Y.at(i)*Y.at(i) <= D*D)
      count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 6356
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * (100001)
ans = sum(A)
for a in A:
  cnt[a] += 1
Q = int(input())
for _ in range(Q):
  B, C = map(int, input().split())
  cnt[C] += cnt[B]
  ans += cnt[B] * (C-B)
  cnt[B] = 0
  print(ans)

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

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define rep(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pf push_front
#define pb push_back
#define FST first
#define SEC second
#define sz(obj) ((int)(obj).size())

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

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

  int n, l;
  cin >> n >> l;
  vector<string> s(n);

  rep(i, n) cin >> s[i];
  sort(begin(s), end(s));
  rep(i, n) cout << s[i];
  cout << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;
int n,x;
int d[20],c[20];
int dp[200010];
int bfs() {
    rep(i,200010) dp[i]=INF;
    dp[0]=0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,0));
    
    while(que.size()) {
        P p=que.top(); que.pop();
        int cost=p.fr;
        int pos=p.sc;
        // printf("%d %d\n",cost,pos);
        if(pos==x) return cost;
        rep(i,n) {
            int t=pos+d[i];
            if(0<=t&&t<200010&&c[i]+cost<dp[t]) {
                dp[t]=c[i]+cost;
                que.push(P(dp[t],t));
            }
            t-=d[i]*2;
            if(0<=t&&t<200010&&c[i]+cost<dp[t]) {
                dp[t]=c[i]+cost;
                que.push(P(dp[t],t));
            }
        }
    }
    return -1;
}
int main() {
    cin>>n>>x;
    rep(i,n) cin>>d[i]>>c[i];
    cout<<bfs()<<endl;
    return 0;
}


Measured memory_bytes: 3876
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  cout<<fixed;
  // a-k = -(b-k) a+b = 2k
  ll a,b;
  cin>>a>>b;
  if((a+b)%2==0) {
    cout << (a+b)/2 << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
    exit()
ma = [None]*n
ma[0] = 1
for i in range(n-1):
    ma[i+1] = (ma[i]-a[i])*2
node = a[-1]
ans = node
for i in range(n-1, -1, -1):
    mi = (node+1)//2
    if ma[i]-a[i]<mi:
        print(-1)
        exit()
    node = min(ma[i]-a[i], node) + a[i]
    ans += node
print(ans)

Measured memory_bytes: 674532
fn main() {
    proconio::input! {
        mut n: usize,
    }
    let mut s=vec![];
    while n>0 {
        n-=1;
        s.push((n%26)as u8+b'a');
        n/=26;
    }
    s.reverse();
    println!("{}",String::from_utf8(s).unwrap());
}

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

    // define
# define loop(i,a,n) for(int i=a;i<n;++i)
# define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(0);
# define ll long long int 
# define endl '\n'
# define mp make_pair
# define mt make_tuple
# define pb push_back
# define eb emplace_back
# define in insert
# define rev(i,a,n) for(int i=n-1;i>=a;--i)
# define test int t; cin>>t; while(t--)

/* debug */
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _itRS(_ss); err(_itRS, args); }

void err(istream_iterator<string> itRS) {}
template<typename T, typename... Args>
void err(istream_iterator<string> itRS, T a, Args... args) {
    cerr << *itRS << " = " << a << endl;
    err(++itRS, args...);
}


const int MOD=1000000007;


int T[10001];
int main()
{
    fast
    int h,a;
    cin>>h>>a;
    int d[a];
    ll sum=0;
    for(int i=0;i<a;i++)
    {
        cin>>d[i];
        sum=sum+d[i];
    }
    if(sum>=h) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define f1(n) for(int i=0;i<n;++i)
#define f2(n) for(int i=1;i<=n;++i)
#define lson(x) x<<1
#define rson(x) x<<1|1
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
const int maxn = 4e5 + 5;
const int mod = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll Inf = (ll)1e15;
int gcd(int a, int b) {  //a,b的最大公余数
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

int exgcd(int a, int b, int& x, int& y) {  //ax+by=gcd(a,b)  不定方程的解x,y，函数返回gcd(a,b)
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	int ans = exgcd(b, a % b, x, y);
	int tx = x;
	x = y;
	y = tx - a / b * y;
	return ans;
}

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

	string s;
	cin >> s;
	if (s[2] == s[3] && s[4] == s[5])cout << "Yes\n";
	else cout << "No\n";

	
	
	
	return 0;
}

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

int M, N;
char A[50][51], B[50][51];
bool E[10][10];

int c = 0;
bool passed[10];

void dfs(int idx) {
    passed[idx] = true;
    bool f = true;
    for (int i = 0; i < N; i++) {
        if(!passed[i]) {
            f = false;
            if (E[idx][i]) {
                E[idx][i] = E[i][idx] = false;
                dfs(i);
                E[idx][i] = E[i][idx] = true;
            }
        }
    }
    if (f) c++;
    passed[idx] = false;
}

void solve() {
    for (int i = 0; i < N; i++) passed[i] = false;
    dfs(0);
    cout << c << endl;
}

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

    for (int i = 0; i < M; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        v1--; v2--;
        E[v1][v2] = E[v2][v1] = true;
    }

    solve();
}

Measured memory_bytes: 256
/*
(1)for binary shift operator always use 'LL' 1LL<<63

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set_pair tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define Luv(...) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }
  const double  pi=3.1415926535; 
  struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator () (std::pair<T1, T2> const &pair) const
	{
		std::size_t h1 = std::hash<T1>()(pair.first);
		std::size_t h2 = std::hash<T2>()(pair.second);

		return h1 ^ h2;
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,i;cin>>n;
	if(n==1){
		cout<<1;
	
	return 0;
}
	for(i=1;i<=n;i++)
		if(((i*10)+7)%n==0)
			break;

		if(i==n+1) cout<<"-1";
		else {
			ll x=7;
			for(i=1;;i++)
				if(x%n==0)
					break;
				else x=(x*10+7)%n;

				cout<<i<<endl;
		}

	return 0;
} 

Measured memory_bytes: 3620
// JAI SHREE RAM
/*
	Author: gourav_raj
*/
#pragma GCC optimize("O3")
typedef long long int ll;
typedef unsigned long long int ull;
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MOD 1000000007
#define max3(a,b,c) max(a,max(b,c))
#define max4(a,b,c,d) max3(a,max(b,c),d)
#define max5(a,b,c,d,e) max4(a,max(b,c),d,e)
#define min3(a,b,c) min(a,min(b,c))
#define min4(a,b,c,d) min3(a,min(b,c),d)
#define min5(a,b,c,d,e) min4(a,min(b,c),d,e)
#define M_PI           3.14159265358979323846  /* pi */
#define sec second
#define fir first
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repe(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define entire(a) (a).begin(),(a).end()
#define pb push_back
#define pii pair<int,int>
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	std::vector<int> v(n);
	rep(i,n)cin>>v[i];
	sort(entire(v));
	ll res=v[n-1],k=n-2;
	for(int i=n-1-1;;i--)
	{
		
			if(!k)break;
			res+=v[i],k--;
			if(!k)break;
			res+=v[i],k--;
		
			if(!k)break;
	}
	

	cout<<res<<endl;
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fast
	int T = 1;
	// cin >> T;
	while (T--)
	{
		solve();
	}
	return 0;
}

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

class P
{
    static void Main()
    {
        int a = int.Parse(Console.ReadLine());
        int b = int.Parse(Console.ReadLine());
        int h = int.Parse(Console.ReadLine());
        Console.WriteLine((a + b) * h / 2);
    }
}

Measured memory_bytes: 11092
/*----------------
     Smit Patel
     DA-IICT
----------------*/
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
// https://atcoder.jp/contests/dp/tasks/dp_d
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ins insert
#define fori(i,a,n) for(ll i=a; i<n; i++)
#define ford(i,a,n) for(int i=a; i>n; i--)
#define clr(a,b) memset(a,b,sizeof(a))
#define deb(x) cout<<#x<<" : "<<x<<endl;
#define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define bp __builtin_popcount
#define mod 1000000007
#define eps 1e-6
#define infi 1000000002
#define infll 1e18+5
#define N 200005
#define LN 20

typedef long double ld;
typedef long long ll;
typedef map<ll,ll> mll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef set<ll> sll;

ll choose(ll n,ll k);
bool isprime(ll n);
ll power(ll x,ll y,ll p);
ll power(ll x,ll y);
ll gcd(ll a,ll b);

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll n,w;
  cin>>n>>w;
  ll we[n],v[n];
  fori(i,0,n)
  {
    cin>>we[i]>>v[i];
  }
  ll dp[n+1][w+1]={};
  fori(i,0,n+1)
  {
    fori(j,0,w+1)
    {
      if(i==0 || w==0)
        dp[i][j]=0;
      else if(we[i-1]<=j)
      {
        dp[i][j]=max(v[i-1]+dp[i-1][j-we[i-1]],dp[i-1][j]);
      }
      else
      {
        dp[i][j]=dp[i-1][j];
      }
    }
  }
  cout<<dp[n][w]<<endl;
  return 0;
}

ll gcd(ll a,ll b)
{
  if(b==0)
    return a;
  return gcd(b,a%b);
}

ll choose(ll n,ll k)
{
  if(k==0)
    return 1;
  return (n* choose(n-1,k-1))/k;
}

bool isprime(ll n)
{
  for(ll i=2;i*i<=n;i++)
  {
    if(n%i==0)
      return false;
  }
  return true;
}

ll power(ll x,ll y,ll p)
{
  ll res=1;
  x=x%p;
  while(y>0)
  {
    if(y&1)
      res=(res*x)%p;
    y=y>>1;
    x=(x*x)%p;
  }
  return res;
}

ll power(ll x,ll y)
{
  ll res=1;
  while(y>0)
  {
    if(y&1)
      res=res*x;
    y=y>>1;
    x=x*x;
  }
  return res;
}


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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1001001001;

const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    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 {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= 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 {
        mint res(*this);
        return res /= a;
    }
};

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];
    }
} comb(100005);

vector<int> to[1000005];
int k;
mint ans;

mint f(int n, int k) {
    if(n < 0) return 0;
    // n  p k
    mint res = comb(n, k);
    res *= comb.fact[k];
    return res;
}

void dfs(int v, int p = -1) {
    for (int u : to[v]) {
        if (u == p) continue;
        dfs(u, v);
    }
    int nk = (p == -1) ? k : k - 2;
    int c = (p == -1) ? to[v].size() + 1 : to[v].size() - 1;
    ans *= f(nk, c);
}


int main() {
    int n;
    cin >> n >> k;
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ans = 1;
    dfs(0);
    cout << ans.x << endl;
}



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

int main()
{
    ll sum = 0;
    int h, n;
    cin >> h >> n;
    rep(i, n){
        ll a;
        cin >> a;
        sum += a;
    }
    if(h > sum){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
    system("pause");
}

Measured memory_bytes: 504
# -*- coding: utf-8 -*-

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

# kは全体-(i+j)で出せるのでループは2重でいい
for i in range(N+1):
    for j in range(N+1):
        k = N - (i + j)
        # kがマイナスになったらその先は周回する必要なし
        if k < 0:
            break
        # 条件を満たす値なら出力して終了
        if i * 10000 + j * 5000 + k * 1000 == Y:
            print(str(i) + " " + str(j) + " " + str(k))
            exit()
# 1つも候補がなかった場合
print("-1 -1 -1")

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

int main() {
    int r , g , b;
    cin >> r >> g >> b;
    int sum = r * 100 + g * 10 + b;
    if(sum % 4 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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

typedef long long ll;

const int mod = 1e9 + 7;
int N;
ll K;

struct matrix {
    int n;
    vector<vector<ll>> mat;

    matrix(int m, int p) {
        n = m;
        mat.resize(m, vector<ll> (m, 0));
        if (p == 1) {
            for (int i = 0; i < m; i++) {
                mat[i][i] = 1;
            }
        }
    }
    matrix multiply(const matrix& b) {
        matrix p = matrix(n, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    p.mat[i][j] = (p.mat[i][j] + mat[i][k] * b.mat[k][j]) % mod;
                }
            }
        }
        return p;
    }
    matrix expo(ll pow) {
        matrix e = matrix(n, 1);
        while (pow) {
            if (pow & 1) {
                e = e.multiply(*this);
            }
            *this = multiply(*this);
            pow = pow >> 1;
        }
        return e;
    }
};

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

    cin >> N >> K;
    matrix g = matrix(N, 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> g.mat[i][j];
        }
    }
    matrix res = g.expo(K);
    ll answer = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            answer = (answer + res.mat[i][j]) % mod;
        }
    }
    cout << answer;

    return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

typedef pair<int,int> pp;

const int MAXN = 1001, MAXM = 101;

int ans[MAXM];

int main()
{
    int n,m;
    while(cin >> n >> m && n)
    {
        memset(ans, 0, sizeof(ans));
        int t;
        rep(i,n)rep(j,m){ cin >> t; ans[j]+=t;}
        vector<pp> b;
        REP(m){b.push_back(pp(-ans[i], i));}

        sort(all(b));

        REP(m){cout << b[i].second + 1; if(i==m-1) break; cout << " ";}
        cout << endl;

    }
    return 0;
}

Measured memory_bytes: 912
//2019.4.13 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
#define RG register
inline int read(){
    res s=0,ch=getchar();
    bool w=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline LL Read(){
    RG LL s=0;
    res ch=getchar();
    bool w=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void swap(res &x,res &y){
    x^=y^=x^=y;
}
namespace MAIN{
    int A,B;
    inline void MAIN(){
        A=read(),B=read();
        res ans=max(A+B,A*2-1);
        ans=max(ans,B*2-1);
        printf("%d\n",ans);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

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

int main()
{
    int n, debt = 100000;
    double rate = 0.05;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        debt *= (1.00 + rate);
        if ((debt % 1000) != 0){
            debt = debt / 1000 * 1000 + 1000;
        }
    }
    cout << debt << endl;
    
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;



int main() {
#ifdef HOME
	ifstream cin("C.in");
	ofstream cout("C.out");
#endif
	int i;
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	string str;
	cin >> str;
	for(i = 0; i < str.size(); i++) {
		char ch;
		if(i % 2) {
			ch = 'i';
		}
		else {
			ch = 'h';
		}
		if(str[i] != ch) {
			cout << "No";
			return 0;
		}
	}
	if(str.size() & 1) {
		cout << "No";
		return 0;
	}
	cout << "Yes";

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){

  int N;
  cin>>N;
  vector<int>L(N);
  int allsum=0;
  for(int i=0;i<=N-1;i++){
  
    cin>>L[i];
    allsum+=L[i];
  }
  sort(L.begin(),L.end());
  if(allsum-L[N-1]>L[N-1])cout<<"Yes";
  else cout<<"No";
  return 0;
}

Measured memory_bytes: 3632
// 参考
// https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// Input macro
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

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

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

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

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

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

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

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

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r"redcoder
" => r"1",

r"vvvvvv
" => r"0",

r"abcdabc
" => r"2"
}

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        s: String
    }

    let mut ans = 0;

    let char_vec: Vec<char> = s.chars().collect();
    for i in 0..char_vec.len() / 2 {
        if char_vec[i] != char_vec[s.len() - 1 - i] {
            ans += 1
        }
    }

    ans.to_string()
}


Measured memory_bytes: 4352
import sys
from collections import defaultdict
input=sys.stdin.readline


def solve():
    N = int(input())
    par = {i:[] for i in range(1, N+1)}

    for i in range(2, N+1):
        a = int(input())
        par[a].append(i)

    q = [1]
    l = []
    while q:
        s = q.pop()
        l.append(s)
        for t in par[s]:
            q.append(t)

    dp = defaultdict(int)
    for s in l[::-1]:
        depth = 1
        res = []
        for t in par[s]:
            res.append(dp[t])
        res.sort(reverse=True)
        for i, j in enumerate(res, start=1):
            depth = max(depth, i+j)
        dp[s] = depth

    print(dp[1]-1)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 110248
main :: IO ()
main = do
  n <- readLn :: IO Int
  print $ fibonacci n

fibonacci :: Int -> Int
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci n = fib (n - 2) [1, 1]
  where
    fib 0 (x:y:_) = x + y
    fib i (x:y:z) = fib (i - 1) $ (x + y):x:y:z



Measured memory_bytes: 3576
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPI(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define ALL(x) (x).begin(),(x).end()

int main () {
  int n, a;
  priority_queue<int> as;
  int alice = 0;
  int bob = 0;

  cin >> n;

  REP(i,n) {
    cin >> a;
    as.push(a);
  }

  for(int i = 0; !as.empty(); i++) {
    if (i % 2 == 0) {
      alice += as.top();
    }
    else {
      bob += as.top();
    }

    as.pop();
  }

  cout << (alice - bob) << endl;

  return 0;
}


Measured memory_bytes: 256
# ALDS1_8_B: Binary Search Tree 2: Search

class BinaryTree
  class Node
    attr_reader :key
    attr_accessor :left, :right

    def initialize(key)
      @key = key
      @left = @right = NIL
    end
  end

  NIL = Node.new(-1)

  def initialize
    @root = NIL
  end

  def insert(key)
    parent = NIL
    node   = @root
    while node != NIL
      parent = node 
      node = key < node.key ? node.left : node.right
    end

    new_node = Node.new key
    if parent == NIL
      @root = new_node
    elsif key < parent.key
      parent.left = new_node
    else
      parent.right = new_node
    end
  end

  def has?(key)
    node = @root
    while node != NIL
      return true if node.key == key
      node = key < node.key ? node.left : node.right
    end
    false
  end

  def keys_by_preorder(node = @root)
    return [] if node == NIL
    left_keys  = keys_by_preorder(node.left)
    right_keys = keys_by_preorder(node.right)
    [node.key] + left_keys + right_keys
  end

  def keys_by_inorder(node = @root)
    return [] if node == NIL
    left_keys  = keys_by_inorder(node.left)
    right_keys = keys_by_inorder(node.right)
    left_keys + [node.key] + right_keys
  end
end

tree = BinaryTree.new

n_commands = gets.to_i
n_commands.times do
  command = gets.chomp
  case command
  when /insert (-?\d+)/
    key = $1.to_i
    tree.insert key
  when /find (-?\d+)/
    key = $1.to_i
    puts tree.has?(key) ? 'yes' : 'no'
  when /print/
    puts ' ' << tree.keys_by_inorder.join(' ')
    puts ' ' << tree.keys_by_preorder.join(' ')
  end
end

Measured memory_bytes: 87740
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
int main() {
    int s;
    cin >> s;
    if( (1<=s%100 && s%100 <=12) && (1<=(s/100) && (s/100)<=12)) cout << "AMBIGUOUS";
    else if(!(1<=s%100 && s%100 <=12) && (1<=(s/100) && (s/100)<=12)) cout << "MMYY";
    else if((1<=s%100 && s%100 <=12) && !(1<=(s/100) && (s/100)<=12)) cout << "YYMM";
    else if(!(1<=s%100 && s%100 <=12) && !(1<=(s/100) && (s/100)<=12)) cout << "NA";
}

Measured memory_bytes: 256
// B - ∵∴∵
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

#define MOD 1000000007
#define rp(i,n) for(int i=0;i<(n);i++)
#define irp(i,n) for(int i=(n);i>=0;i--)
#define up(i,s,e,d) for(int i=(s);i<(e);i+=(d))
#define dw(i,s,e,d) for(int i=(s);i>(e);i-=(d))
// #define in(x) cin>>(x)
#define ot(x) cout<<(x)
#define ote(x) cout<<(x)<<endl
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define vecmax(v) (*max_element(v.begin(),v.end()))
#define range(v,x) (iota((v).begin(),(v).end(),(x)))
void bye(auto x, int code=0){cout<<(x)<<endl;exit(code);}
// int in(){int x;cin>>x;return x;}
int in(){int x;scanf("%d",&x);return x;}
// template<class T> T in(){T x;cin>>x;return x;}

void vprn(vector<int> &v){ for(int i=0;i<v.size();i++) cout<<v[i]<<(i<v.size()-1?",\t":"\n"); }
void vvprn(vector<vector<int>> &vv){ for(auto v:vv) vprn(v); }

// template<class T> void vprn(T &v, string s, string m, string e)
// {cout<<s;for(int i=0;i<v.size();i++)cout<<v[i]<<m;cout<<e;}
// template<class T> void vvprn(T &vv, string s, string m, string e)
// {for(auto v:vv) vprn(v,s,m,e);}

#define otreal(n,p) cout<<fixed<<setprecision(p)<<(n)

int main(){
	vector<string> s(2);
	cin>>s[0]>>s[1];
	rp(i,s[0].size()+s[1].size()){
		ot(s[i%2][i/2]);
	}
	ot("\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ll INF = 1e18;
#define pu push
#define pb push_back
#define mp make_pair
#define print(x) cout << (x) << endl;
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define fi first
#define sc second

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if (S.at(2)==S.at(3)&&S.at(4)==S.at(5)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
/* テンプレートここまで */

int main() {
  int a, b; cin >> a >> b;
  cout << (a-1) * (b-1) << endl;
}


Measured memory_bytes: 764
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
//#include<math.h>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007ll
#define pb push_back
#define fi first
#define se second
#define mk make_pair
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

int n, ans1, ans2;
string s;

signed main()
{
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        if(s[i] == '('){
            ans2++;
        }
        else if(s[i] == ')'){
            ans2 = max(ans2 - 1, 0ll);
        }
        if(s[n - 1 - i] == '('){
            ans1 = max(ans1 - 1, 0ll);
        }
        else if(s[n - 1 - i] == ')'){
            ans1++;
        }
    }
    for(int i = 0; i < ans1; i++){
        printf("(");
    }
    for(int i = 0; i < n; i++){
        printf("%c", s[i]);
    }
    for(int i = 0; i < ans2; i++){
        printf(")");
    }
    printf("\n");


    return 0;
}
/*


*/


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

using namespace std;
typedef long long ll;

map<char,ll> mp;
bool vis[200005];
int main()
{
   ll n,k,r,si,p;
   cin >> n >> k;
   cin >> r >> si >> p;
   mp['r'] = p;
   mp['s'] = r;
   mp['p'] = si;


    string s;
    cin >> s;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(i < k){
            ans += mp[s[i]],vis[i] = 1;
        }
        else {
            if(s[i] != s[i-k]){
                ans += mp[s[i]],vis[i] = 1;
            }
            else{
                if(!vis[i-k])
                    vis[i] = 1,ans += mp[s[i]];
                else
                    vis[i] = 0;
            }
        }
    }

    cout << ans << endl;

}


Measured memory_bytes: 512