akhauriyash/Code-Regression huggingface dataset:
// -----------------------------------------------
// Framework <https://github.com/vain0x/procon>
//
// See the bottom of file for solution.
// -----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let (A, B, C) = read!(i64, i64, i64);
    println!("{}", min(C, B / A));
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
	int H,W; cin >> H >> W;
	vector<vector<char>> s(H,vector<char>(W));
	rep(i,H)rep(j,W) cin >> s[i][j];

	queue<Pi> q;
	vector<vector<int>> dist(H,vector<int>(W,INF));
	dist[0][0] = 0;
	q.push(Pi(0,0));
	while(!q.empty()){
		Pi f = q.front();
		q.pop();
		int u = f.first;
		int v = f.second;
		vector<int> a{-1,0,1,0};
		vector<int> b{0,-1,0,1};
		rep(i,4){
			if(u+a[i] >= 0 && u+a[i] < H && v+b[i] >= 0 && v+b[i] < W){
				if(dist[u+a[i]][v+b[i]] == INF && s[u+a[i]][v+b[i]] == '.'){
					dist[u+a[i]][v+b[i]] = dist[u][v] + 1;
					q.push(Pi(u+a[i],v+b[i]));
                }
			}
		}
	}

	int cnt = 0;
	rep(i,H)rep(j,W){
		if(s[i][j] == '.') cnt++;
	}
	if(dist[H-1][W-1] == INF){
		cout << -1 << endl;
		return 0;
	}
	int ans = cnt - dist[H-1][W-1] - 1;
	cout << ans << endl;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define fst first
#define scd second
bool isvisit[200001];
signed main()
{
	int n, a[200001], pos = 0;
	long long m;
	scanf("%d%lld", &n, &m);
	for(int i = 0, j; i < n; ++i)
	{
		scanf("%d", &j);
		a[i] = j - 1;
	}
	for(int count = 0, iscir = true; m > 0; --m)
	{
		if(isvisit[pos] && iscir)
		{
			for(int _pos = a[pos]; ; ++count)
			{
				if(_pos == pos)
				{
					m %= (long long)(count + 1);
					iscir = false;
					break;
				}
				_pos = a[_pos];
			}
			if(m == 0)
			{
				break;
			}
		}
		isvisit[pos] = true;
		pos = a[pos];
	}
	printf("%d\n", pos + 1);
}


Measured memory_bytes: 4836
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <stdio.h>
#include <bits/stdc++.h>


using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORa(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define FORs(i,st) for(auto i : st)
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)

char int_to_char(ll x){
  if(x == -1) return '?';
  else if(x<=9)return '0' + x;
  else return 'A' + x - 10;
}



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

    ll n,m,q;
    cin>>n>>m>>q;
    while(n != 0){

      vector<string> sw(q+1);
      vector<string> light(q+1);

      FOR(i,0,n){
        sw[0].push_back('0');
      }
      FOR(i,0,m){
        light[0].push_back('0');
      }

      FOR(i,1,q+1){
        cin>>sw[i]>>light[i];
      }
      q++;

      FOR(i,1,q){
        FOR(j,0,n){
          if(sw[i-1][j] == '1' && sw[i][j] == '1') sw[i][j] = '0';
          else if(sw[i-1][j] == '0' && sw[i][j] == '1') sw[i][j] = '1';
          else if(sw[i-1][j] == '1' && sw[i][j] == '0') sw[i][j] = '1';
        }
      }

      vector<vector<ll>> v(m,vector<ll>(n,1));

      FOR(i,0,q){//クエリごと
        FOR(j,0,m){//あかりごと
          FOR(k,0,n){
            if(sw[i][k]=='0' && light[i][j] =='1')v[j][k]=0;
            if(sw[i][k]=='1' && light[i][j] =='0')v[j][k]=0;
          }
        }
      }

      vector<ll> ans;
      FOR(i,0,m){
        ll tmp=0;
        ll po=0;
        FOR(j,0,n){
          tmp+=v[i][j];
          if(v[i][j]==1)po=j;
        }
        if(tmp==1)ans.push_back(po);
        else ans.push_back(-1);
      }

      FOR(i,0,m){
        cout<<int_to_char(ans[i]);
      }
      cout<<endl;


      cin>>n>>m>>q;
    }
}



Measured memory_bytes: 4296
tmp = list(map(int, input().split()))
h = tmp[0]
w = tmp[1]
k = tmp[2]

s = []
for i in range(h):
  s.append(input())

v = [False for _ in range(h)]
a = [[0 for _ in range(w)] for _ in range(h)]

fv = -1
lv = -1

ptr = 1
for i in range(h):
  first = False
  for j in range(w):
    if first and s[i][j] == '#':
      ptr += 1
    elif s[i][j] == '#':
      first = True
    a[i][j] = ptr
  if first == True:
    ptr += 1
    v[i] = True
    lv = i
    if fv == -1:
      fv = i

cv = -1
for i in range(h):
  if i < fv:
    for j in range(w):
      print(a[fv][j], end=' ')
  elif i > lv:
    for j in range(w):
      print(a[lv][j], end=' ')
  elif v[i]:
    cv = i
    for j in range(w):
      print(a[i][j], end=' ')
  else: # Mid Invalid Row
    for j in range(w):
      print(a[cv][j], end=' ')
  print('')

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

int main( )
{
    int a, b;
    cin >> a >> b;
    if (max(a, b) > 8)
    {
        cout << ":(\n";
    }
    else
    {
        cout << "Yay!\n";
    }
    return 0;
}


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

long long s, e, x, cnt, t, tt, i;

int main()
{
    scanf("%lld %lld %lld", &s, &e, &x);
    t = s/x;
    if(!(s%x)) t--;
    tt = e/x;

    printf("%lld\n", tt-t);

    return 0;

}


Measured memory_bytes: 128
#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 reps(i,a,b) for(int i= a; i < b; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  int n;
  cin >> n;
  vector<int> vec(n+1, 0);
  reps(i, 1, 101) reps(j, 1, 101)  reps(k, 1, 101) {
    int v = pow(i, 2) + pow(j, 2) + pow(k, 2) + (i*j) + (j*k) + (k*i);
    if (v <= n) vec[v]++;
  }
  reps(i, 1, n+1) {
    cout << vec[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3616
import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String[] cut = input.split(" ");
		Arrays.sort(cut);
		System.out.println(cut[0]+" "+cut[1]+" "+cut[2]);
		
		
	}
}

Measured memory_bytes: 24284
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1);
int f[100];
int main()
{
    int a,b,c;
    cin >> a>> b>> c;
    if(a+b+c>=22)
        cout << "bust\n";
    else
        cout << "win\n";

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%lld%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

typedef long long ll;

const int N_MAX = 100000;
const ll INF = 1e15;

int N;
int A[N_MAX];
int op[N_MAX + 1];
ll dp[N_MAX + 1][3];

void solve() {
  fill(dp[0], dp[N + 1], -INF);
  fill(dp[0], dp[1], 0);
  int m = 1;
  REP(i, N) {
    REP(j, min(m, 3)) {
      int a = A[i] * ((j + op[i]) % 2 == 0 ? 1 : -1);
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a);
      if (j < 2 && op[i] > 0) {
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a);
      }
      if (j > 0) {
        dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + a);
      }
    }
    m += op[i];
  }

  // DUMP2D(dp, N + 1, 3);

  ll ans = -INF;
  REP(j, 3) ans = max(ans, dp[N][j]);
  printf("%lld\n", ans);
}

void input() {
  scanf("%d", &N);
  REP(i, N) {
    scanf("%d", A + i);
    if (i + 1 < N) {
      char buf[2];
      scanf("%s", buf);
      op[i + 1] = buf[0] == '-' ? 1 : 0;
    }
  }
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 3328
N=int(input())
S=[input() for _ in [0]*N]
AB=0
X_A=0
B_X=0
B_A=0
for s in S:
    AB+=s.count("AB")
    if s[0]!="B" and s[-1]=="A":X_A+=1
    if s[0]=="B" and s[-1]!="A":B_X+=1
    if s[0]=="B" and s[-1]=="A":B_A+=1
r=AB
if B_A>0:
    r+=B_A-1
    if X_A>0:r+=1;X_A-=1
    if B_X>0:r+=1;B_X-=1
r+=min(X_A,B_X)
print(r)

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

using namespace std;
using ll = long long;
using pint = pair<int, int>;

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

	ll ans = K;
	for (int i = 1; i < N; ++i) {
		ans *= (K - 1);
	}

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

Measured memory_bytes: 3596
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
    let s:Vec<char> = get_input().chars().collect();
    let acgt = vec!['A', 'C', 'G', 'T'];

    let mut ans = 0;
    let mut max = 0;

    for i in s {
        if acgt.clone().into_iter().filter(|&x| x == i).count() > 0 {
            max += 1;
        } else {
            if max > ans {
                ans = max;
            }
            max = 0;
        }
    }
    println!("{}", std::cmp::max(ans,max));
}


Measured memory_bytes: 4352
s = input()
t = input()
cnt = 0
for i in range(len(s) - len(t), -1, -1):
    cnt = 0
    for j in range(len(t)):
        if s[j + i] == "?" or s[j + i] == t[j]:
            cnt += 1
        else:
            break
    if cnt == len(t):
        for j in range(len(s)):
            if i <= j < i + len(t):
                print(t[j - i], end = "")
            elif s[j] == "?":
                print("a", end = "")
            else:
                print(s[j], end = "")
        print()
        break
if cnt != len(t):
    print("UNRESTORABLE")

Measured memory_bytes: 38256
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val s = sc.next
  val k = sc.nextInt

  val target = s.charAt(k - 1)

  val res =
    s.foldLeft(""){case (str, c) =>
      str + (if(c == target) c else '*')
    }

  println(res)
}


Measured memory_bytes: 25936
def main():
    H,W = map(int,input().split())

    C = 10
    c = []
    for i in range(C):
        c.append(list(map(int,input().split())))

    a = []
    for i in range(H):
        a.append(list(map(int,input().split())))

    for k in range(C):
        for i in range(C):
            for j in range(C):
                c[i][j] = min(c[i][j],c[i][k]+c[k][j])

    ans = 0
    for i in range(H):
        for j in range(W):
            if a[i][j] != -1:
                ans += c[a[i][j]][1]
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    int *num;
    num = new int [N];
    for(int i=0;i<N;i++){
        cin >> num[i];
    }
    for(int i=0;i<N-1;i++){
        cout << num[N-i-1] << ' ';
    }
    cout << num[0] << endl;
    delete[] num;
    return 0;
} 

Measured memory_bytes: 3068
#include<iostream>
#include<string>

using namespace std;

void solve() {
    string s, t;
    cin >> s >> t;
    t.pop_back();
    cout << (s == t ? "Yes" : "No");
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

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

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimize("Ofast")
//1.0 * clock() / CLOCKS_PER_SEC

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int NN = 1e6 + 7;
const int N = 3e3 + 7;
const int M = 20;
const int mod = 998244353;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;

ll n,s;
ll a[N];
ll d[N][N];
ll sum[N][N];

void solve1()
{
    cin >> n >> s;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i];
        d[i][a[i]] = i;
    }
    ll ans = 0;
    for( int i = 1; i <= n; i++ ){
        for( int j = a[i]; j <= s; j++ ){
            d[i][j] = ( d[i][j] + sum[i - 1][j - a[i]] ) % mod;
        }
        for( int j = 0; j <= s; j++ ){
            sum[i][j] = ( sum[i - 1][j] + d[i][j] ) % mod;
        }
        ans = ( ans + d[i][s] * (n - i + 1) % mod ) % mod;
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); srand(time(0));
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int cghf = 1;//cin >> cghf;
    while( cghf-- ){
        solve1();
    }
}


Measured memory_bytes: 141568
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const int big=1e16+10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(b==0){return a;}return gcd(b,a%b);}//a>b
llint lcm(llint a,llint b){return (a/gcd(max(a,b),min(a,b)))*b;}
int main(void){
	llint i,n,wa=0,gen=0,ans=big;cin>>n;
	vector<llint>a(n);
	for(i=0;i<n;i++){
		cin>>a[i];wa+=a[i];
	}
	for(i=0;i<n-1;i++){
		gen+=a[i];
		mineq(ans,abs((2*gen)-wa));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
/***
 *          _           _       _ _                             _
 *      ___| |__   ___ | | ___ (_) |__  _   _  __ _ _ __   ___ | |__   ___   __ _
 *     / __| '_ \ / _ \| |/ _ \| | '_ \| | | |/ _` | '_ \ / _ \| '_ \ / _ \ / _` |
 *    | (__| | | | (_) | | (_) | | | | | |_| | (_| | | | | (_) | | | | (_) | (_| |
 *     \___|_| |_|\___/|_|\___/|_|_| |_|\__,_|\__,_|_| |_|\___/|_| |_|\___/ \__,_|
 *
 *                _       ____            _____     _
 *      /\/\     /_\     /___ \  /\ /\    \_   \   /_\
 *     /    \   //_\\   //  / / / / \ \    / /\/  //_\\
 *    / /\/\ \ /  _  \ / \_/ /  \ \_/ / /\/ /_   /  _  \
 *    \/    \/ \_/ \_/ \___,_\   \___/  \____/   \_/ \_/
 *
 */
#include<bits/stdc++.h>
using namespace std;
#define g(a,b,c) for(int a=b;a<c;a++)
#define ff(a,b,c) for(int a=c;a>b;a--)
#define ffk(a,b,c) for(int a=b;a<=c;a++)
#define fff(a,b,c) for(int a=c;a>=b;a--)
long long h[100005];
long long maxx=0;
int main (){
long long  n;
cin>>n;
bool ck=1;
for(long long i=0;i<n;i++){
	cin>>h[i];
}
for(long long i=n-1;i>0;i--){
	if(h[i]<h[i-1]-1){
		cout<<"No";
		return 0;
	}
	else {
		if(h[i]==h[i-1]-1){
			h[i-1]=h[i-1]-1;
		}
	}
}
cout<<"Yes";
return 0;
}


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES 
#include<iomanip> 
#include<cmath>  
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
typedef long long ll;
#define repi(i,a,b) for(ll i = (ll)(a) ; i < (ll)(b) ; i++)
#define repd(i,a,b) for(ll i = (ll)(a) ; i > (ll)(b) ; i--)
#define rd(x) cin >> x
#define wr(x)  cout << x
#define wrln(x) cout << x << endl

int a, b, c, d;

int main() {
	cin >> a >> b >> c >> d;

	int t1 = max(a, c), t2 = min(b, d);
	
	wrln(max(t2 - t1, 0));

	return 0;
}

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


inline vector<int> getDivisors(int n){
	vector<int> v;
	for(int i = 1; i*i <= n; i++){
		if(n % i == 0){
			v.push_back(i);
			if( i*i != n ) v.push_back(n/i);
		}
	}
	return v;
}
int S[100010] = {};
int C[100010] = {};

int add(int x,int a){
	for(;x < 100010; x+=x&-x){
		C[x] += a;
	}
}
int get(int x){
	int ans = 0;
	for(;x > 0; x-=x&-x){
		ans += C[x];
	}
	return ans;
}

int main(){
	int N,W;
	cin >> N >> W;
	for(int i = 1; i <= W; i++){
		vector<int> g = getDivisors(i);
		for(int j = 0; j < g.size(); j++){
			if(S[g[j]]==1) add(g[j],1);
			S[g[j]]++;
		}
	}
	
	int o = 0;
	cout << W;
	for(int i = 1; i <= N-W; i++){
		vector<int> g = getDivisors(i);
		for(int j = 0; j < g.size(); j++){
			if(S[g[j]]==2) add(g[j],-1);
			S[g[j]]--;
		}
		g = getDivisors(i+W);
		for(int j = 0; j < g.size(); j++){
			if(S[g[j]]==1) add(g[j],1);
			S[g[j]]++;
		}
		int o = 0;
		cout << " " << get(i)+W;
		
	}
	cout << endl;
}

Measured memory_bytes: 1828
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1000003 ;

int main(){
  int n,d;
  cin >> n >> d;
  int x[n][d];
  rep(i,n){
    rep(j,d)cin >> x[i][j];
  }
  ll cnt=0;
  rep(i,n){
    for(int j=i+1;j<n;j++){
      ll dis=0;
      rep(k,d){
        dis+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
      }
      bool ok=false;
      for(int k=1;k*k<=dis;k++){
        if(k*k==dis)ok=true;
      }
      if(ok)cnt++;
    }
  }
  cout << cnt << endl;
return 0;}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int numN = scan.nextInt();
		int numL = scan.nextInt();

		ArrayList<String> strS = new ArrayList<>();

		for (int i = 0; i < numN; i++) {
			strS.add(scan.next());
		}

		Collections.sort(strS);

		StringBuilder strSB = new StringBuilder();

		for (String str : strS) {
			strSB.append(str);
		}
		System.out.println(strSB);
	}
}


Measured memory_bytes: 21972
#include <stdio.h>
#include <stdlib.h>
void push(int);
int pop(void);
int top=0, S[101];
int i;

int main(void)
{
	int x, y;
	char str[8];
	while ( scanf("%s",str) != EOF ) {
		switch ( str[0] ) {
		case '+':
			y = pop();
			x = pop();
			push(x+y);
			break;
		case '-':
			y = pop();
			x = pop();
			push(x-y);
			break;
		case '*':
			y = pop();
			x = pop();
			push(x*y);
			break;
		default:
			push( atoi(str) );
			break;
		}
	}
	/*for(i = 0;i <= top;i++){
		printf("%d",S[i]);
		if(i != top){
			printf(" ");
		}
		else{
			printf("\n");
		}
	}*/
	printf("%d\n",S[top]);
		return 0;
}

void push(int x)
{
	top++;
	S[top] = x;
}

int pop(void)
{
	top--;
	return S[top+1];
}

Measured memory_bytes: 548
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,D;
  cin>>N>>D;
  int a[N][D];
  for(int i = 0;i<N;i++){
    for(int k = 0;k<D;k++){
      cin>>a[i][k];
    }
  }
  int ans = 0;
  int temp = 0;
  for(int i = 0;i<N-1;i++){
    for(int k = i+1;k<N;k++){
      temp = 0;
      for(int p = 0;p<D;p++){
        temp += (a[i][p]-a[k][p])*(a[i][p]-a[k][p]);
      }
      for(int q = 0;q<1000;q++){
        if(temp == q*q){
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int N, D;
  int i, j, k;
  cin >> N >> D;
  
  vector<vector<int>> data(N, vector<int>(D));

  for (i = 0; i < N; i++){
    for (j = 0; j < D; j++){
      cin >> data.at(i).at(j);
    }
  }
  int count = 0;  
  double t;
  int distance;
  for (k = 0; k < N - 1; k++){
	for (i = k + 1; i < N; i++){
      
      t = 0;
      for (j = 0; j < D; j++){
  	    t += (data.at(i).at(j) - data.at(k).at(j))*(data.at(i).at(j) - data.at(k).at(j));
      }
      t = sqrt(t);
      distance = (ceil(t) + floor(t))/2;
      if (t == distance){
        count++;
      }
      
    }
  }
  cout << count;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll; 
typedef pair<int,int> P;
typedef pair<ll,P> lP;
int p[100000],q[100000];
ll w,h;
ll ans;
vector<lP> v;
int main(){
  cin>>w>>h;
  for(int i=0;i<w;i++)cin>>p[i],v.push_back(lP(p[i],P(i,0)));
  for(int i=0;i<h;i++)cin>>q[i],v.push_back(lP(q[i],P(i,1)));
  sort(v.begin(),v.end());
  ll g=(w+1)*(h+1)-1,t=0,y=0;
  for(int i=0;i<v.size();i++){
    if(v[i].s.s==0){
      ll k=h+1-y;
      t++;
      g-=k;
      ans+=k*v[i].f;
    }
    if(v[i].s.s==1){
      ll k=w+1-t;
      y++;
      g-=k; 
      ans+=k*v[i].f;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 5104
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(ll)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll n,m;cin>>n>>m;
    ll g=m/n;
    for(;g>=1;g--){
        if(m%g==0){
            cout<<g<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef long long ll;

int main () {
  ll n, x;
  cin >> n >> x;

  ll ans = n;
  ll p = x, q = n - x;
  if (p < q) swap(p, q);
  while (true) {
    if (p % q == 0) {
      ans += (2 * (p / q) - 1) * q;
      break;
    } else {
      ans += 2 * q * (p / q);
      p %= q;
      swap(p, q);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false; }

const int INF=1e18;
const int MOD=1e9+7;
const int MAX_T = 1e5 + 3;

int a[MAX_T][30];

signed main(){
    int n, c; cin >> n >> c;
    REP(i,n){
        int s, t, c; cin >> s >> t >> c; t++; c--;
        a[s][c]++;
        a[t][c]--;
    }
    REP(i,1e5+2) REP(j,30) a[i+1][j] += a[i][j];
    REP(i,1e5+2) REP(j,30) if(a[i][j] == 0 and a[i+1][j] == 1) a[i][j] == 1;
    REP(i,1e5+2) REP(j,30) a[i][j] = min(a[i][j],1ll);
    int x = 0;
    REP(i,1e5+1){
        int sum = 0;
        REP(j,30) sum += a[i][j];
        chmax(x ,sum);
    }
    cout << x << endl;
}

Measured memory_bytes: 23680
#!python3

from heapq import heappop, heappush


INF = 10 ** 18

# input
N, M, S = list(map(int, input().split()))
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]


def solve(link):
    ans = {}
    lim = 50 * (N - 1)
    w = [[INF] * (lim + 1) for _ in range(N)]

    # (time, node, silver)
    hq = [(0, 0, min(S, lim))]
    while hq:
        t, v, s = heappop(hq)
        if t > w[v][s]:
            continue
        if v not in ans:
            ans[v] = t
            if len(ans) == N:
                break
        
        # buy
        if s < lim:
            c, d = CD[v]
            new_s = min(lim, s + c)
            new_t = t + d
            if new_t < w[v][new_s]:
                w[v][new_s] = new_t
                heappush(hq, (new_t, v, new_s))
        
        # move
        for u, a, b in link[v]:
            if s < a:
                continue
            new_s = s - a
            new_t = t + b
            if new_t < w[u][new_s]:
                w[u][new_s] = new_t
                heappush(hq, (new_t, u, new_s))
        
    return ans


def main():
    link = [[] for _ in range(N)]
    for u, v, a, b in UVAB:
        link[u - 1].append((v - 1, a, b))
        link[v - 1].append((u - 1, a, b))
    
    ans = solve(link)
    for i in range(1, N):
        print(ans[i])


if __name__ == "__main__":
    main()


Measured memory_bytes: 23864
INF = 10**9 + 7


def main():
    N, M, X = (int(i) for i in input().split())
    CA = [[int(i) for i in input().split()] for j in range(N)]
    ans = INF
    for bit in range(1 << N):
        wakaru = [0]*M
        cur = 0
        for i in range(N):
            if bit & (1 << i):
                c, *A = CA[i]
                cur += c
                for j in range(M):
                    wakaru[j] += A[j]
        if all(m >= X for m in wakaru):
            ans = min(ans, cur)

    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 74772
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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

ans = 0
for i in range(n-1):
    if (a[i] > a[i+1]):
        ans += a[i]-a[i+1]
        a[i+1] = a[i]
print(ans)



Measured memory_bytes: 31832
#!/usr/bin/env python
# coding: utf-8

# In[17]:


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


# In[18]:


d_s = sorted(d)
print(d_s[len(d_s)//2] - d_s[len(d_s)//2-1])


# In[ ]:






Measured memory_bytes: 14428
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

int main(){
    ll n, m;
    cin >> n >> m;
    ll x[100002], y[100002];
    ll dx[100002], dy[100002];
    cin >> x[0];
    for(int i = 1; i < n; i++){
        cin >> x[i];
        dx[i] = x[i] - x[i - 1];
    }
    cin >> y[0];
    for(int i = 1; i < m; i++){
        cin >> y[i];
        dy[i] = y[i] - y[i - 1];
    }
    ll linearx = 0;
    for(ll i = 1; i < n; i++){
        linearx = (linearx + i * (n - i) * dx[i]) % MOD;
    }
    ll lineary = 0;
    for(ll i = 1; i < m; i++){
        lineary = (lineary + i * (m - i) * dy[i]) % MOD;
    }
    cout << linearx * lineary % MOD << endl;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<bool> z(n);
    vector<int> res;
    for (int i = 0; i < n; i++) {
        int x = -1;
        for (int j = 0; j < n - i; j++) {
            if (a[j] == j + 1) {
                x = j;
            }
        }
//        cout << x << "\n";
        if (x == -1) {
            cout << -1;
            return 0;
        }
        res.push_back(x + 1);
        for (int k = x; k < n - 1; k++) {
            a[k] = a[k + 1];
        }
    }
    for (int i = 0; i < n; i++) cout << res[n - 1 - i] << "\n";

    return 0;
}

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

using namespace std;

int main(){
  int N;
  cin>>N;
  vector<int>num(N);
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>num.at(i);
  }
  
  int ans=0;
  int current_min=1e9;
  
  for(int i=0;i<N;i++){
    current_min=min(current_min,num.at(i));
    if(current_min==num.at(i)){
      sum++;
    }
  }
  
  cout<<sum<<endl;
}

      
      
      


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

#define ll long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MAX = 1e5 + 5;

int main()
{
	IOS
	int t = 1;
	cin >> t;
	int ac = 0, wa = 0, tle = 0, re = 0;
	while(t--)
	{
		string s;
		cin >> s;
		if(s == "AC") ac += 1;
		else if(s == "WA") wa++;
		else if(s == "TLE") tle++;
		else re++;
	}
	cout << "AC x " << ac << endl;
	cout << "WA x " << wa << endl;
	cout << "TLE x " << tle << endl;
	cout << "RE x " << re << endl;
	return 0;
}


Measured memory_bytes: 3608
n=int(input())
h=list(map(int,input().split()))
h[0]-=1
for i in range(1,n):
    if h[i]>h[i-1]:
        h[i]-=1
    elif h[i]<h[i-1]:
        h[0]=-100
        break
if h[0]==-100:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 14380
import sys
input = sys.stdin.readline
K = int(input())
N = len(input().rstrip())
mod = 10**9 + 7
pow25 = [1]
pow26 = [1]
x = 1
y = 1
for i in range(K):
    x *= 25
    y *= 26
    x %= mod
    y %= mod
    pow25.append(x)
    pow26.append(y)

def comb(n, r, mod):
    if r<0 or r>n:
        return 0
    r = min(r, n-r)
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, N + K + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    finv.append((finv[-1] * inv[-1]) % mod)

ans = 0
for i in range(K+1):
    ans += (((comb(i+N-1, N-1, mod) * pow25[i]) % mod) * pow26[K-i]) % mod
print(ans%mod)

Measured memory_bytes: 229168
#include<stdio.h>
int main()
{
   long long int a,b,c,k,i,sum=0;
    scanf("%lld %lld %lld %lld",&a,&b,&c,&k);

for(i=1;i<=k;i++)
{
    if(i<=a)
    {
        sum=sum+1;
    }
    else if(i>a&&i<=(a+b))
    {
        sum=sum+0;
    }
    else
    {
    sum=sum+(-1);
    }
}
printf("%lld",sum);
return 0;
}

Measured memory_bytes: 1708
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scan(&a, &b)
	if a < b {
		for i := 0; i < b; i++ {
			fmt.Print(a)
		}
	} else {
		for i := 0; i < a; i++ {
			fmt.Print(b)
		}
	}
	fmt.Println("")
}

Measured memory_bytes: 512
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        (wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

struct UnionFind {
	vector<int>Par, Rank;
	UnionFind(int n) {
		Par.resize(n);
		Rank.resize(n);
		for (int i = 0; i < n; i++) {
			Par[i] = i;
			Rank[i] = 0;
		}
	}

	int find(int x) {
		if (Par[x] == x) {
			return x;
		}
		else {
			return Par[x] = find(Par[x]);
		}
	}

	void unite(int  x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (Rank[x] < Rank[y]) {
			Par[x] = y;
		}
		else {
			Par[y] = x;
			if (Rank[x] == Rank[y])Rank[x]++;
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int n, k, l;
int p, q;

int main() {
	cin >> n >> k >> l;
	UnionFind uf(n * 2+120);
	REP(i, k) {
		cin >> p >> q;
		p--, q--;
		uf.unite(p, q);
	}
	REP(i, l) {
		cin >> p >> q;
		p--, q--;
		uf.unite(n + p, n + q);
	}
	vector<pair<int, int>> pa;
	map<pair<int, int>,int> mp;
	REP(i, n) {
		pa.emplace_back(make_pair(uf.find(i), uf.find(n + i)));
	}
 	REP(i, n) {
		mp[pa[i]]++;
	}
	REP(i, n) {
		if (i)cout << " ";
		cout << mp[pa[i]];
	}
	cout << endl;
	//system("pause");
}

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

#define int long long
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; }

signed main(){
	int n;
	string s;
	int ans = 0;
	cin >> n >> s;

	int x = 0;
	for(int i = 0;i < n;i++){
		x += (s[i] == 'I' ? 1 : -1);
		chmax(ans, x);
	}

	cout << ans << endl;

	return 0;
}


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

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

  int ans = 1;
  for (int i = 0; i < n; i++) {
    if (2*ans >= ans+k) ans = ans+k;
    else ans = 2*ans;
  }

  cout << ans << endl;

}


Measured memory_bytes: 3588
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cout << (#x) << ": " << (x) << endl
#define DEBUG_VEC(v)            \
    cerr << #v << ": ";         \
    REP(__i, (v).size())        \
    cerr << ((v)[__i]) << ", "; \
    cerr << endl

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main()
{
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vi V(N), C(N);
    REP(i, N) cin >> V[i];
    REP(i, N) cin >> C[i];

    int ans = 0;
    REP(i, N)  ans += max(0, V[i] - C[i]);

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

using namespace std;

int main() {
    size_t a1, a2, a3;
    cin >> a1 >> a2 >> a3;
    if (a1 + a2 + a3 > 21)
        cout << "bust" << endl;
    else
        cout << "win" << endl;

    return 0;
}


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

int main() {
    int N, Y;
    cin >> N >> Y;
    int res100 = -1, res50 = -1, res10 = -1;
    for (int a = 0; a <= N; ++a) {
        for (int b = 0; b + a <= N; ++b) { 
            int c = N - a - b;  
            int total = 10000*a + 5000*b + 1000*c;
            if (total == Y) {
                res100 = a;
                res50 = b;
                res10 = c;
            }
        }
    }
    cout << res100 << " " << res50 << " " << res10 << endl;
}

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

#define all(x) (x).begin(),(x).end()

#define MOD 1000000007

using namespace std;

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

	if( equal( s.begin(), s.end(), t.begin(), t.end()-1 ) )	cout << "Yes" << endl;
	else	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * A-Z Cat
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		line = br.readLine();

		StringBuilder sb = new StringBuilder();
		boolean a = true;

		for (char c : line.toCharArray()) {
			if (c == 'A' && a) {
				a = false;
			}
			if (c == 'Z' && !a) {
				sb.append("AZ");
				a = true;
			}
		}

		if (sb.length() != 0) {
			System.out.println(sb.toString());
		} else {
			System.out.println(-1);
		}
	}
}

Measured memory_bytes: 24484
#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>

int N;
int a[100002], b[100002], c[100002];

// ボトムアップに解く
int solveBottomUp() {
  // DP
  int dp[100002][3]; // dp[i][j] := i日目にjを選んだ時の幸福度最大値
  memset(dp, 0, sizeof(dp)); // 0で初期化しておく
  
  // 1日目は先に埋めておく
  dp[1][0] = a[1];
  dp[1][1] = b[1];
  dp[1][2] = c[1];

  // DP更新
  for (int i = 2; i <= N; i++) {
    // i日目に0(A)を選んだ時の幸福度最大値
    //  = 前日にB,Cを選んだ時の最大値のmax + i日目にAを選ぶ最大値
    dp[i][0] = std::max(dp[i - 1][1], dp[i - 1][2]) + a[i];

    // i日目に1(B)を選んだ時の幸福度最大値
    dp[i][1] = std::max(dp[i - 1][0], dp[i - 1][2]) + b[i];

    // i日目に2(C)を選んだ時の幸福度最大値
    dp[i][2] = std::max(dp[i - 1][0], dp[i - 1][1]) + c[i];
  }

  // N日目にA,B,Cを選んだ時の最大値の最大値を取る
  int result = std::max(dp[N][0], std::max(dp[N][1], dp[N][2]));

  return result;
}


// トップダウンに解く
int memo[100002][3]; // memo[i][j] := i日目にjを選んだ時の幸福度最大値
int solveRecursive(int n, int action) {
  int &cache = memo[n][action];
  if (cache != -1) return cache;
  if (n == 0) return 0;
  if (action == 0) {
    return cache = std::max(solveRecursive(n-1, 1), solveRecursive(n-1, 2)) + a[n];
  }
  if (action == 1) {
    return cache = std::max(solveRecursive(n-1, 0), solveRecursive(n-1, 2)) + b[n];
  }
  if (action == 2) {
    return cache = std::max(solveRecursive(n-1, 0), solveRecursive(n-1, 1)) + c[n];
  }
  assert(0);
  return -1;
}
int solveTopDown() {
  memset(memo, -1, sizeof(memo)); // -1で初期化しておく
  int result_a = solveRecursive(N, 0);
  int result_b = solveRecursive(N, 1);
  int result_c = solveRecursive(N, 2);
  return std::max(result_a, std::max(result_b, result_c));
}

int main(void) {
  std::cin >> N;
  // 入力の受け取り
  for (int i = 1; i <= N; i++) { // 1-indexedで入れる
    std::cin >> a[i] >> b[i] >> c[i];
  }
  
  std::cout << solveBottomUp() << std::endl;
  // std::cout << solveTopDown() << std::endl;

  return 0;
}

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


using namespace std;

/* macros */
#define all(v)			((v).begin()), ((v).end())
#define SIZE(v)			((int)((v).size()))
#define LOG(x)			log((double)x)
#define TOLOWER(x)          transform(all(x),x.begin(),::tolower)
#define TOUPPER(x)          transform(all(x),x.begin(),::toupper)
#define ROUND(x,m)			(round((double)x/m)*m)
#define DIGITS(x)			(floor(log10((double)x))+1)
#define READSTR(x)			getline(cin,x)
#define sort_g(a,b)              sort(a, b, greater<int>());
#define IOS() ios_base::sync_with_stdio(0);cin.tie(NULL);
#define REP(i, n) for (int i = 0; i < n; i++)
#define FILE_INPUT() 	freopen( "input.txt", "r", stdin)
#define FILE_OUTPUT()   freopen( "output.txt", "w", stdout)

/*typedefs*/
typedef long long ll;
/*functions*/
bool myCmp(pair<int,int> &p1 , pair<int,int>&p2)
{
    return p1.first > p2.first;
}
unsigned long long
choose(unsigned long long n, unsigned long long k) {
    if (k > n) {
        return 0;
    }
    unsigned long long r = 1;
    for (unsigned long long d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}
int toInt(string str) {
    int num;
    istringstream iss(str); //put string in input stream
    iss>>num; return num; //read from stream as integer
}

template <class T> string toStr(T par) {
    ostringstream oss;  //output stream string
    oss<<par;    //write par to the stream
    return oss.str(); //return string of output
}


string front_chars;
string s;

int main() {
    IOS();
    int q;

    bool isRev = false;
    cin>>s>>q;
    while(q--)
    {
        int t;
        cin>>t;
        if(t == 1)
        {
            isRev = !isRev;

        }
        else
        {
            int f;
            char nc;
            cin>>f>>nc;
            if( ((f == 1 ) && (!isRev) ) ||((f == 2) && (isRev)))
            {
                front_chars.push_back(nc);
                //cout<<"Front "<<nc<<" "<<front_chars<<endl;
            }
            else
            {
                s.push_back( nc);
                //cout<<"Back "<<nc<<" "<<s<<endl;
            }
        }
    }
    if(isRev)
    {
        reverse(s.begin(),s.end());
        s = s+ front_chars;
    }
    else
    {
        reverse(front_chars.begin(),front_chars.end());
        s.insert(0,front_chars);
    }
    cout<<s<<endl;

    return 0;
}


Measured memory_bytes: 1104
S = input()
n = False
s = False
e = False
w = False

if 'N' in S:
    n = True
if 'S' in S:
    s = True
if 'E' in S:
    e = True
if 'W' in S:
    w = True

if n == s and e == w:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
import sys

for s in sys.stdin:
  i=s.find("+")
  j=s.find("=")
  A=[s[0:i],s[i+1:j],s[j+1:-1]]
  f=0
  for e in A:
    if e!=e[0]=="X": f=1; break
  m="NA"
  for c in "0123456789"[f:]:
    if eval(s[:-1].replace("X",c).replace("=","==")): m=c; break
  print m

Measured memory_bytes: 4260
#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 MOD=1000000007;
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(){
   ll n,m;
   cin>>n>>m;

   if(2*n<=m){
      cout<<n+(m-2*n)/4;
   }
   else{
      cout<<m/2;
   }
   
   return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define REP(name, stop) for (ll(name) = 0; (name) < (stop); (name)++)
using ll = long long;
using vi = vector<ll>;

int main(void) {
    ll n, r;
    cin >> n >> r;
    ll ans;
    if (n >= 10) {
        ans = r;
    } else {
        ans = r + 100 * (10 - n);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($N,$X) =  explode(" ",trim(fgets(STDIN)));
$L =  explode(" ",trim(fgets(STDIN)));

$D = 0;
for($i=0;$i<$N;$i++) {
  $x = $D + $L[$i];
  if ($x > $X) break;
  $D += $L[$i];
}
printf("%d\n",$i+1);


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

int x, res = 0;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  
  cin >> x;
  res += x / 500 * 1000;
  x %= 500;
  res += x / 5 * 5;
  cout << res << "\n";
  
  return 0;
}

Measured memory_bytes: 256
n=int(input())
arr=[]
from collections import Counter
c=Counter([])
for _ in range (n):
    s=input()
    z=[item for item in s]
    z.sort()
    z=tuple(z)
    c[z]+=1
ans=0
for item in c.values():
    ans+=(item*(item-1))//2
print (ans)

Measured memory_bytes: 28156
#include <algorithm>
#include <complex>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep0(i, n) rep(i, 0, n)
#define rep1(i, n) rep(i, 1, n + 1)

typedef long long ll;

int main()
{
    string s;
    cin >> s;
    bool b[26];
    rep0(i, 26) b[i] = false;
    rep0(i, s.size()) b[s[i]-'a'] = true;
    rep0(i, 26) {
        if (!b[i]) {
            cout << char(i + 'a') << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

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

using namespace std;

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

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

    int q;
    cin >> q;
    while (q--) {
        int b, m, e;
        cin >> b >> m >> e;
        rotate(a.begin() + b, a.begin() + m, a.begin() + e);
    }

    for (int i = 0; i < a.size(); ++i) {
        cout << (i ? " " : "") << a[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3168
open System 

type Explicit =          
    static member inline ($) (_:int32, _:Explicit) = int
    static member inline ($) (_:int64, _:Explicit) = int64

let inline convert (value:'a): 'b = 
    (Unchecked.defaultof<'b> $ Unchecked.defaultof<Explicit>) value

let inline fromInt (x: int): 'a = convert x

module NumericLiteralG =
    let inline FromZero(): ^a = LanguagePrimitives.GenericZero
    let inline FromOne(): ^a = LanguagePrimitives.GenericOne
    let inline FromInt32 n = fromInt n

let inline extGcd (x: 'a) (y: 'a): 'a*'a*'a =
    let inline divRem x y = x / y, x % y 
    let rec f u v u' v' x y =
        if y = 0G then u, v, x 
        else let d, r = divRem x y in f u' v' (u - d * u') (v - d * v') y r 
    f 1G 0G 0G 1G x y 

let inline inverse (m: 'a) (x: 'a): 'a =
    extGcd x m 
    |> fun (x,_,_) -> (x + m) % m 
    
let inline combination (m: 'a) (size: int) : int -> int -> 'a =
    let facts, invFacts = 
        let facts = Array.zeroCreate <| size+1
        let invFacts = Array.zeroCreate <| size+1 
        facts.[0] <- 1G 
        invFacts.[0] <- inverse m facts.[0]
        for i in 1..size-1 do 
            facts.[i] <- fromInt i * facts.[i-1] % m
            invFacts.[i] <- inverse m facts.[i]
        facts, invFacts
    (fun n r -> 
        if n < 0 || r < 0 || n < r then failwithf "invalid arg, n: %d, r: %d" n r
        elif r = 0 || n = r then 1G
        elif n = 0 then 0G 
        else (facts.[n] * invFacts.[r] % m) * invFacts.[n-r] % m)
    
let MOD = int64 1e9 + 7L

let R() = Console.ReadLine()

let N, K = let t = R().Split() |> Array.map (string>>int) in int t.[0], int t.[1]

let comb = combination MOD N 

for i in 1..K do 
    if N - K + 1 < i then 0L
    else ((comb (N - K + 1) i) * (comb (K - 1) (i - 1))) % MOD
    |> Console.WriteLine

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

int main(void){
    int d;
    cin >> d ;
    if(d==25){
        cout << "Christmas" << endl;

    }else if(d==24){
        cout << "Christmas Eve" << endl;
    }else if(d==23){
        cout << "Christmas Eve Eve" << endl;
    }else if(d==22){

        cout << "Christmas Eve Eve Eve" << endl;
    }
    return 0;
}

Measured memory_bytes: 256