akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			if(n == 0 && m == 0){
				break;
			}
			int[] input = new int[n];
			
			for(int i = 0; i < n ; i++){
				input[i] = sc.nextInt();
			}
			
			System.out.println(solve(input, m));
		}
	}
	
	//半分全列挙で解きたい
	static long solve(int[] array, int limit){
		int n = array.length + 1;
		int[] copyArray = new int[n];
		//0を追加した配列を作る
		for(int i = 0 ; i < n - 1; i++){
			copyArray[i] = array[i];
		}
		
		//2回投げたときに有り得る得点
		long[] twoTimes = new long[n*n];
		
		int index = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				twoTimes[index++] = copyArray[i] + copyArray[j];
			}
		}
		
		Arrays.sort(twoTimes);
		//debug
//		for(int i = 0; i < twoTimes.length; i++){
//			System.out.println(twoTimes[i]);
//		}
		
		long result = 0;
		
		for(int i = 0; i < twoTimes.length ; i++){
			//そもそも2回だけで済む場合
			if(twoTimes[i] == limit){
				System.out.println("JUST");
				return twoTimes[i];
			}
			
			//既にオーバーしている場合も論外
			else if (twoTimes[i] > limit){
//				System.out.println("OVER i = "+i+" "+twoTimes[i]);
				break;
			}
			
			//わざと少し下を狙う
			int tmpIndex = Arrays.binarySearch(twoTimes, limit - twoTimes[i] - 1);
			
			if(tmpIndex < 0){
				tmpIndex++;
				tmpIndex *= -1;
				tmpIndex--;
			}
			
			if(tmpIndex >= twoTimes.length){
				tmpIndex = twoTimes.length - 1;
			}
			
			
			for(int j = Math.max(tmpIndex, 0); j < twoTimes.length; j++){
//				if(twoTimes[i] + twoTimes[j] > limit){
//					break;
//				}
//				System.out.println("j = "+j+" "+twoTimes[i] + " "+twoTimes[j]);
				if(twoTimes[i] + twoTimes[j] > limit){
					break;
				}
				result = Math.max(result, twoTimes[i] + twoTimes[j]);
			}
		}
		return result;
	}

}



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

int main() {
  int a, b, c ,d;
  cin >> a >> b >> c >> d;
  bool turn = true;
  while(a > 0 && c > 0){
    if(turn){
      c -= b;
      turn = false;
    }
    else{
      a -= d;
      turn = true;
    }
  }
  
  if(a <= 0) cout << "No" << endl;
  else cout << "Yes" << endl;
}

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

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

    int res = 0;
    int cnt = (s.at(0) == 'R' ? 1 : 0);
    for (int i = 1; i < 3; i++) {
        if (s.at(i-1) == 'R' && s.at(i) == 'R') {
            cnt++;
        } else {
            if (res < cnt) res = cnt;
            if (s.at(i) == 'R') {
                cnt = 1;
            } else {
                cnt = 0;
            }
        }
    }

    cout << max(res,cnt) << endl;

    return 0;
}


Measured memory_bytes: 3588
n,a = map(int,input().split())
*l, = map(int,input().split())
l = [i-a for i in l] #平均値からの差分に直す。
dp_ll = [[0]*5001 for _ in range(n+1)] #5001で-2500~2500までの範囲をカバー。 
dp_ll[0][2500] = 1 #2501番目がちょうど0となる。
for i in range(0,n):
  for j in range(0,5001):
    if j-l[i] >= 0 and j-l[i] < 5001: #範囲外を参照するのを防止
      dp_ll[i+1][j] = dp_ll[i][j-l[i]]+dp_ll[i][j] 
print(dp_ll[n][2500]-1)

Measured memory_bytes: 5620
#include<stdio.h>
int main(void){
	int N;
    int a[9][9],i,j;
  	int flag=0;
  	scanf("%d",&N);
	for(i=0;i<9;i++){
    	for(j=0;j<9;j++){
    		a[i][j] = (i+1)*(j+1);
          if(N==a[i][j]){
          	flag = 1;
          }
      }
    }
	if(flag==1) printf("Yes");
  	else printf("No");
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp(a,b) std::make_pair(a,b)
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
str s;
int main(){
  cin>>s;
  int ns=s.size();
  int m=(ns+1)/2;
  int res=0;
  rep(i,m) if(s[i]=='p') res--; 
  for(int i=m;i<ns;i++) if(s[i]=='g') res++;
  prin(res);
  return 0;
}


Measured memory_bytes: 512
n,k,q=map(int,input().split())
p=[k]*n
#m=[-1]*n
for ii in range(q):
  a=int(input())-1
  p[a]+=1
#print(p)
for ii in range(n):
  if -q+p[ii]>0:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 6584
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define _rep(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
#define ll long long
const int mod=1e9+7;
const int inf=1e9;
#define N 200005
int n;
std::pair<int,int> lup,rup,ld,rd,a[N];
inline int dis(std::pair<int,int> x,std::pair<int,int> y){
	return abs(x.first-y.first)+abs(x.second-y.second);
}
int main(){
	std::cin>>n;
	lup={inf,-inf},rup={-inf,-inf},ld={inf,inf},rd={-inf,inf};
	rep(i,1,n){
		std::cin>>a[i].first>>a[i].second;
		if(-lup.first+lup.second<-a[i].first+a[i].second)
			lup=a[i];
		if(rup.first+rup.second<a[i].first+a[i].second)
			rup=a[i];
		if(-ld.first-ld.second<-a[i].first-a[i].second)
			ld=a[i];
		if(rd.first-rd.second<a[i].first-a[i].second)
			rd=a[i];
	}
	int ans=0;
	rep(i,1,n){
		ans=std::max(ans,dis(lup,a[i]));
		ans=std::max(ans,dis(rup,a[i]));
		ans=std::max(ans,dis(ld,a[i]));
		ans=std::max(ans,dis(rd,a[i]));
	}
	std::cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 5196
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
using namespace std;
string a, b;
ll freqa[28], freqb[28];
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> a >> b;
    for(int i = 0; i < a.length(); i++){
        freqb[b[i]-'a']++;
        freqa[a[i]-'a']++;
    }
    bool ok = 1;
    sort(freqa, freqa+26); sort(freqb, freqb+26);
    for(int i = 0; i < 26; i++){
        if(freqa[i] == freqb[i])continue;
        else{
            cout << "No" << endl; return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

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

void solve() {
  string s;
  cin >> s;
  int n = 4;
  rep(i, bit32(3)) {
    int v = s[0] - '0';
    string ans;
    ans += s[0];
    rep(j, 3) if (bit32(j) & i) {
      v += s[j + 1] - '0';
      ans += '+';
      ans += s[j + 1];
    } else {
      v -= s[j + 1] - '0';
      ans += '-';
      ans += s[j + 1];
    }
    if (v == 7) {
      cout << ans << "=7" << endl;
      return;
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

int f(int a, int b) {
  int c = abs(a - b);
  return min(c, 24 - c);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  vector<int> D(24); rep(i, 24) D[i] = 0;
  D[0] ++;
  rep(i, N) {
    int d; cin >> d;
    if(D[d] == 0) {
      D[d] ++;
      continue;
    } 
    if(D[d] != 0) {
      int d_ = (d != 0 ? 24 - d : 0);
      D[d_] ++;
    }
  }
  rep(i, 24) {
    if(D[i] >= 2) {
      cout << 0 << "\n";
      return 0;
    }
  }
  int ans = 0;
  for(int bit = 0; bit < (1<<11); bit++) {
    int ret = 12;
    rep(i, 11) {
      if((bit & (1<<i))) {
        if(D[i + 1] == 1 && D[23 - i] == 0) {
           D[i + 1] = 0; D[23 - i] = 1;
        }
      }
    }
    priority_queue<int, vector<int>, greater<int>> pque;
    pque.push(24);
    rep1(j, 23) {
      if(D[j] == 1) pque.push(j);
    }
    int p = 0;
    while(pque.size()) {
      int q = pque.top(); pque.pop();
      int ret1 = f(p, q);
      ret = min(ret, ret1);
      p = q;
    }
    ans = max(ans, ret);
    rep(j, 11) {
      if((bit & (1<<j))) {
        if(D[j + 1] == 0 && D[23 - j] == 1) {
           D[j + 1] = 1; D[23 - j] = 0;
        }
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define orep(i, n) for(int i = 1; i <= (n); i++)
#define srep(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define ru(a,b) ((a+b-1) / b)
#define rng(x) (x).begin(),(x).end()
#define P pair<int,int>

typedef long long ll;
using namespace std;

int main() {
  int n; cin >> n;
  vector<int> height(n,0);
  rep(i,n) cin >> height.at(i);

  int mx = height.at(0);
  ll ans = 0;
  rep(i,n) {
    if(height.at(i) < mx) {
      ans += mx - height.at(i);
    }
    mx = max(mx,height.at(i));
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 4052
import math

def main():
  t1, t2 = map(int, input().split())
  a1, a2 = map(int, input().split())
  b1, b2 = map(int, input().split())

  sumA = t1 * a1 + t2 * a2
  sumB = t1 * b1 + t2 * b2

  if sumA == sumB:
    return 'infinity'
  if sumA < sumB:
    sumA, sumB = sumB, sumA
    a1, b1 = b1, a1
    a2, b2 = b2, a2
  # A の方が sum が大きいとする

  halfA = t1 * a1
  halfB = t1 * b1
  if halfA > halfB:
    return 0
  div, mod = divmod(halfB - halfA, sumA - sumB)
  if mod == 0:
    return div * 2
  return div * 2 + 1

print(main())

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double,int> pdi;
const int N = 100005;
int a[N];
int fa[N];
vector<int> rec[N];
set<int> big[N];
map<int, int> mp;
int fat(int x)
{
    if(fa[x] == x)
        return x;
    return fa[x] = fat(fa[x]);
}
int main()
{

    int n, m, x, y, fax, fay;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        fax = fat(x);
        fay = fat(y);
        if(fax != fay)
            fa[fax] = fay;
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        int f = fat(i);
        if(!mp.count(f))
        {
            mp.insert(pii(f, ++cnt));
        }
        int id = mp[f];
        big[id].insert(a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int f = fat(i);
        int id = mp[f];
        if(big[id].count(i))
            ans++;
    }
    printf("%d\n", ans);
}









Measured memory_bytes: 17408
fn main() {
    let s: String = read();

    let days = vec!["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"];
    let x = days.iter().position(|&x| x == s).unwrap();

    println!("{}", 7 - x);
}


fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}


Measured memory_bytes: 4352
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		int p[] = new int[N];

		for(int i = 0;i<N;i++) {
			p[i]= sc.nextInt();
		}

		Arrays.sort(p);
		int ans = 0;

		for(int i = 0;i<K;i++) {
			ans=ans+p[i];
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 38768
import sys
sys.setrecursionlimit(1000000)

nVertices = int(input())
edges = [[] for _ in range(nVertices + 1)]
length = {}
for _ in range(nVertices - 1):
    u, v, l = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)
    if u > v:
        u, v = v, u
    length[(u, v)] = l
color = [None] * (nVertices + 1)
color[1] = 0

def dfs(par, v):
    for child in edges[v]:
        if child != par:
            key = (min(v, child), max(v, child))
            if length[key] & 1 == 0:
                color[child] = color[v]
            else:
                color[child] = color[v] ^ 1
            dfs(v, child)

dfs(0, 1)
print('\n'.join(map(str, color[1:])))

Measured memory_bytes: 82804
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] S = sc.next().toCharArray();
		sc.close();
		char s = S[0];
		boolean ok = true;
		for(int i = 1; i < S.length; i++) {
			if(s == S[i]) {
				ok = false;
				break;
			}
			s = S[i];
		}
		System.out.println(ok ? "Good" : "Bad");
	}
}


Measured memory_bytes: 23636
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
   int temp;
   for (int i = 0; i < 10000; i++)
   {
       scanf("%d", &temp);
       if (0 == temp)
           break;
       printf("Case %d: %d\n", i + 1, temp);

   }


    return 0;
}



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

int main() {
  int N;
  cin >> N;
  vector<int> cards(N), sorted(N);

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

  sort(cards.begin(), cards.end(), greater<int>() );

  int alice = 0, bob = 0;
  for (int i = 0; i < N; i++) {
    if ((i % 2) == 0) {
      alice += cards.at(i);
    }
    else {
      bob += cards.at(i);
    }
  }

  cout << alice - bob << endl;
}


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

int main() {
	string str;
	int cnt;
	int len;
	int remain;

	cin >> str;

	len = str.length();
	remain = 15 - len;

	cnt = std::count(begin(str), end(str), 'o');

	if ((cnt + remain) >= 8) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	



}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;

#ifndef LOCAL
#pragma GCC optimize ("O2")
#define endl '\n'
#endif

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

ll pwr(ll a,ll b, ll mod){
    a %= mod;
    int ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

map<int,int> m;
void solve(){
	int n;
	cin >> n;
	fr(i, 1, n){
		int x;
		cin >> x;
		m[-x]++;
	}
	int v1 = 0, v2 = 0;
	for(auto &x : m){
		if(x.se >= 2){
			x.se -= 2;
			v1 = x.fi;
			break;
		}
	}
	for(auto &x : m){
		if(x.se >= 2){
			x.se -= 2;
			v2 = x.fi;
			break;
		}
	}
	cout << v1 * v2;
}
signed main(){
    IO;
    #ifdef LOCAL
        freopen("inp.txt","r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    cout << setprecision(10) << fixed;
    int t = 1;
    // cin >> t;
    fr(tt, 1, t){
        solve();
    }
    return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n, m;
	cin >> n >> m;
	ll k;
	cin >> k;
	vector<ll> a(n), b(m);
	rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i];
	vector<ll> x(n + 1), y(m + 1);
	rep(i, n) x[i + 1] = x[i] + a[i];
	rep(i, m) y[i + 1] = y[i] + b[i];
	y.pb(INF);
	int ans = 0;
	rep(i, n + 1) {
		if (x[i] > k) continue;
		int t = upper_bound(all(y), k - x[i]) - y.begin();
		chmax(ans, i + t - 1);
	}
	cout << ans << '\n';
}

Measured memory_bytes: 11116
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007
var mod1 int = 1000000007

type con struct {
	a int
	b int
}

func conunt(d int, a []int) int {
	ans := 0
	for i := 0; i < len(a); i++ {
		if a[i] == d {
			ans++
		}
	}
	return ans
}

func modPlus(a int, b int) int {
	return a%mod1 + b%mod1
}

func modTime(a int, b int) int {
	return a % mod1 * b % mod1
}

func modMinus(a int, b int) int {
	tm := (a - b) % mod1
	if tm < 0 {
		tm += mod1
	}
	return tm
}

func modDiv(a int, b int) int {
	return a % mod1 * modInv(b) % mod1
}

func modInv(a int) int {
	b := mod1
	u := 1
	v := 0
	for {
		if b == 0 {
			break
		}
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= mod1
	if u < 0 {
		u += mod1
	}
	return u
}

var inf = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	//予備
	n := iScan()
	a := make([]int, n)
	m := map[int]int{}
	ans := 0
	for i := 0; i < n; i++ {
		a[i] = iScan()
		ans += a[i]
		m[a[i]]++
	}
	q := iScan()
	b := make([]int, q)
	c := make([]int, q)
	for i := 0; i < q; i++ {
		b[i] = iScan()
		c[i] = iScan()

	}
	for i := 0; i < q; i++ {
		numB := m[b[i]]
		ans += (c[i] - b[i]) * numB
		m[c[i]] += m[b[i]]
		m[b[i]] = 0
		fmt.Println(ans)
	}
	//fmt.Println(m)
}


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

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

    long long ans(min(a, b / 2));
    a -= ans;
    b -= 2 * ans;

    if (b)
        ans += b / 4;

    cout << ans;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
listh = list(map(int, input().split()))
listans = [listh[0]]
for n in range(1,N-1):
    if (listh[n+1]-listh[n])*(listh[n]-listh[n-1])<=0:
        listans.append(listh[n])
listans.append(listh[N-1])        
#print(listans)
l =len(listans)
listans2 = []
for n in range(l-1):
    if listans[n] == listans[n+1]:
        pass
    else:
        listans2.append(listans[n])
listans2.append(listans[l-1])        
#print(listans2)    
L = len(listans2)
#print(L)
listans3 = [listans2[0]]
for n in range(1,L-1):
    if (listans2[n+1]-listans2[n])*(listans2[n]-listans2[n-1])<=0:
        listans3.append(listans2[n])
listans3.append(listans2[L-1])        
#print(listans3)
ll =len(listans3)
listodd = [listans3[x] for x in range(ll) if x%2 ==1]
#print(listodd)
listeven = [listans3[x] for x in range(ll) if x%2 ==0]
#print(listeven)
if len(listodd) == 0:
    print(listeven[0])
elif ll%2 == 0:
    if listeven[0]>listodd[0]:
        del listodd[-1]
        ans = sum(listeven)-sum(listodd)
        print(ans)

    else:  
        del listeven[0]
        ans = sum(listodd)-sum(listeven)  
        print(ans)

else:     
    if listeven[0]>listodd[0]:
        ans = sum(listeven)-sum(listodd)
        print(ans)

    else:
        del listeven[-1]
        if len(listeven) >= 1:
            del listeven[0]
        ans = sum(listodd)-sum(listeven)
        print(ans)
        

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

int main() {
  int H, W;
  string S, SS;
  cin >> H >> W;
  
  for(int i = 0; i < H; i++) {
    cin >> S;
    SS += S;
  }
    
  for(int j = 0; j < W*H; j++) { 
      int T = 0;

      if(W!=1 && (j+1)>W && (j+1)%W!=1 && SS.at(j-W-1)=='#') T++;    
      if((j+1)>W && SS.at(j-W)=='#') T++;
      if(W!=1 && (j+1)>W && (j+1)%W!=0 && SS.at(j-W+1)=='#') T++;

      if(W!=1 && (j+1)%W!=1 && SS.at(j-1)=='#') T++;
      if(SS.at(j)=='#') T++;
      if(W!=1 && (j+1)%W!=0 && SS.at(j+1)=='#') T++;

      if(W!=1 && (j+1)<=W*(H-1) && (j+1)%W!=1 && SS.at(j+W-1)=='#') T++;    
      if((j+1)<=W*(H-1) && SS.at(j+W)=='#') T++;
      if(W!=1 && (j+1)<=W*(H-1) && (j+1)%W!=0 && SS.at(j+W+1)=='#') T++;
    
      if(SS.at(j) == '#') cout << SS.at(j);
      else cout << T;
      
      if((j+1)%W==0) cout << endl;
    
  }
  
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;


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

    long long N,K;
    cin >> N >> K;
    long long ans=K;
    rep(i,N-1) ans*=(K-1);
    cout << ans << endl;


}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>

using namespace std;

struct node{
  int priority,key;
  node *right, *left;
};


node* rightRotate(node* t) {
  node* s = t->left;
  t->left = s->right;
  s->right = t;
  return s;
}

node* leftRotate(node* t) {
  node* s = t->right;
  t->right = s->left;
  s->left = t;
  return s;
}

node* MakeNode(int key, int priority){
  node* t = new node;
  t->left=NULL;
  t->right = NULL;
  t->key = key;
  t->priority = priority;
  return t;
}

node* insert(node* t, int key, int priority) {

  if(t == NULL) { return MakeNode(key,priority);}
  if(key == t->key) {return t;}

  if(key < t->key) {
    t->left = insert(t->left, key, priority);
    if( (t->priority) < (t->left->priority) ){ t = rightRotate(t); }
  }
  else{
    t->right = insert(t->right, key, priority);
    if(( t->priority) < (t->right->priority) ){ t = leftRotate(t); }
  }
  return t;
}

node* _delete(node* t, int key); //プロトタイプ宣言
node* node_delete(node* t, int key){
  if( t == NULL ) {return NULL;}
  if(  (t->key) > key ) { t->left = node_delete(t->left, key); }
  else if( (t->key) < key ) { t->right = node_delete(t->right, key); }
  else { return _delete(t, key);}
  return t;
}

node* _delete(node* t, int key){

  if( t->left == NULL && t->right == NULL) { return NULL; }
  else if( t->left == NULL ) { t = leftRotate(t); }
  else if(t->right == NULL) { t = rightRotate(t); }
  else {
    if( (t->left->priority) > (t->right->priority) ) {t = rightRotate(t);}
    else t = leftRotate(t);
  }
  return node_delete(t,key);
}


void find(node* t, int key) {

  while(t != NULL && key != t->key) {
    if(key < t->key) { t = t->left; }
    else {t = t->right;}
  }

  if(t == NULL) cout << "no" << endl;
  else cout << "yes" << endl;

}

void order (node *t, int op){

  if(op==1){
    if(t==NULL) return;
    order(t->left,1);
    cout << " " << t->key;
    order(t->right,1);
  }else if(op==2){
    if(t == NULL) return;
    cout << " " << t->key;
    order(t->left,2);
    order(t->right,2);
  }

}

int main() {

  string op;
  node* root=NULL;
  int m,key,priority;

  cin >> m;
  for(int i=0; i<m; i++) {

    cin >> op;

    if(op == "insert") {
      cin >> key >> priority;
      root = insert(root, key, priority);
    }

    else if(op == "find") {
      cin >> key;
      find(root, key);
    }

    else if(op == "delete") {
      cin >> key;
      root = node_delete(root, key);
    }

    else {
      order(root,1);
      cout << endl;
      order(root,2);
      cout << endl;
    }
  }
}


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

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

    vector<int> a(n);
    rep(i,n) cin >> a[i];

    ll ans = 0;
    {
        int h, f;
        f = 0;
        rep(i,n-1) {
            h = a[i] + f;
            if (h > a[i+1]) {
                f = h - a[i+1];
            } else {
                f = 0;
            }
            ans += f;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4044
n = int(input())
x = [int(i) for i in input().split()]
x_new = sorted(x)
med1 = x_new[n//2]
med2 =x_new[n//2-1]
for i in range(n):
    if x[i] < med1:
        print(med1)
    else:
        print(med2)

Measured memory_bytes: 93780
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 9999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define p(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
//#define int long long


using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };




ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

ll pow2(ll a, ll n) {//aのn乗を計算します。
	ll x = 1;
	while (n > 0) {//全てのbitが捨てられるまで。
		if (n & 1) {//1番右のbitが1のとき。
			x = x * a;
		}
		a = a * a;
		n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
	}
	return x;
}

long long nCr(int n, int r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	int i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}


const int MOD = 1000000007;

bool arr[1050000];
int sosuu[100010];
void Eratosthenes() {
	ll N = 1050000;
	int c = 0;
	for (int i = 0; i < N; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i < sqrt(N); i++) {
		if (arr[i]) {
			for (int j = 0; i * (j + 2) < N; j++) {
				arr[i *(j + 2)] = 0;
			}
		}
	}

	for (int i = 2; i < N; i++) {
		if (arr[i]) {
			sosuu[c] = i;
			//cout << sosuu[c] << " ";
			c++;
		}
	}
	//cout << endl;
	//cout << c << endl;
}


bool prime(ll n) {
	if (n == 1)return false;
	if (n == 2)return true;
	for (int i = 2; i < (int)sqrt(n) + 1;i++) {
		if (n%i == 0)return false;
	}
	return true;
}
vector<ll>sosu;
map<ll, int>mp;
int main() {
	ll N, P;
	cin >> N >> P;
	FOR(i, 2, 2000001) {
		if (prime(i))sosu.pb(i);
	}
	
	if (N == 1) {
		p(P);
		return 0;
	}
	ll x = P;
	if (P == 1) {
		p(1);
		return 0;
	}
	while (x >= 2) {
		for (ll i = 2; i < (ll)sqrt(P) + 1; i++) {
			if (x%i == 0) {
				mp[i]++;
				x /= i;
				break;
			}
			if (i == (ll)sqrt(P))goto END;
		}
	}
	END:
	ll ans = 1;
	for (auto x : mp) {
		while (x.second / N > 0) {
			ans *= x.first;
			x.second -= N;
		}
	}
	p(ans);
}

Measured memory_bytes: 2548
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

vector<vector<ll>> edge;
vector<map<ll,ll>> dp;
vector<ll> ans;

ll search(ll w,ll p,ll k){
    if(w>=k){return 0;}
    if(dp[w].count(k)){return dp[w][k];}
    ll ret=1;
    for(auto &i:edge[w]){
        if(i==p){continue;}
        ret+=search(i,w,k);
    }
    return dp[w][k]=ret;
}

void dfs(ll w,ll p,ll pmax){
    if(p==-1){ans[w]=1;}
    else if(p==0){ans[w]=2;}
    else if(pmax<w){
        ans[w]=ans[p];
        ans[w]++;
        for(auto &i:edge[w]){
            if(i==p){continue;}
            ans[w]+=search(i,w,max(p,pmax));
        }
    }
    else if(pmax>p){ans[w]=ans[p];}
    else{
        ans[w]=ans[p];
        ans[w]-=search(w,p,pmax);
        ans[w]+=search(w,p,p);
    }
    pmax=max(pmax,p);
    for(auto &i:edge[w]){
        if(i==p){continue;}
        dfs(i,w,pmax);
    }
}




int main(){
    ll n;
    cin>>n;
    edge.resize(n);
    dp.resize(n,map<ll,ll>());
    ans.resize(n);
    for(int i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(0,-1,-1);
    for(int i=1;i<n;i++){
        cout<<ans[i]-1;
        if(i+1!=n){cout<<" ";}
    }
    cout<<endl;
    
    
    return 0;
}


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}


/*{
  }*/

using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int,int>;

//constexpr int mod = 1e9+7;
//constexpr int inf = 1<<30;

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

  int g = 0, p = 0;
  int ans = 0;
  rep(i, 0, n){
    if(p < g){
      ans += s[i] == 'g';
      p++;
    }else{
      ans -= s[i] == 'p';
      g++;
    }
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 512
import itertools

def main():
    N = int(input())
    A = list(map(int, input().split()))

    ans = [0 for _ in range(N)]

    for i in range(N):
        ans[A[i]-1] = i+1
    for a in ans:
        print(a, end=" ")
    return 0
if __name__ == '__main__':
    main()

Measured memory_bytes: 14256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N, *XY = map(int, read().split())
    X = list(zip(XY[::2], range(N)))
    Y = list(zip(XY[1::2], range(N)))

    X.sort()
    Y.sort()

    edge = []
    for i in range(N - 1):
        edge.append((X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]))
        edge.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))

    edge.sort()

    uf = UnionFind(N)
    ans = 0
    for d, s, t in edge:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += d

    print(ans)
    return


if __name__ == '__main__':
    main()


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

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

  ll a, b, n;
  cin >> a >> b >> n;

  ll x = min(b - 1, n);
  cout << (a*x / b) - a * (x / b) << '\n';

  return (0);
}

Measured memory_bytes: 3620
#include<iostream>
using namespace std;
void heapify(long long *arr,int i,int n){
  int left = 2*i+1;
  int right = 2*i+2;
  int largest = i;
  if(left<n&&arr[left]>arr[largest]){
   	largest = left;
    
  }
  if(right<n&&arr[right]>arr[largest]){
   	largest = right;
    
  }
  if(largest != i){
    swap(arr[largest],arr[i]);
    heapify(arr,largest,n);
  }
}
int main(){
  int n,m;
  cin>>n>>m;
  long long  arr[n];
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  for(int i= n/2;i>=0;i--){
    heapify(arr,i,n);
  }
  for(int i=0;i<m;i++){
    arr[0] = arr[0]/2;
    heapify(arr,0,n);
  }
  long long  sum = 0;
  for(int i=0;i<n;i++){
    sum+=arr[i];
  }
  cout<<sum;
  
  
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };
static const int mod = 1000000007;

int N,K;
int a[5005];
int dp[5005][5005];
vector<int> A;
vector<int> B;

bool solve(int i){
    A.erase(A.begin()+i);
    //for(auto a:A)cout<<a<<" ";
    //cout<<endl;
    int n=A.size();
    for(int j=0;j<=N;++j)for(int k=0;k<=K;++k)dp[j][k]=0;
    if(A[0]<=K)dp[0][A[0]]=1;
    dp[0][0] = 1;
    int res=0;
    for(int j=1;j<n;++j){
        for(int k=0;k<K;++k){
            if(k-A[j]<0)dp[j][k] = dp[j-1][k];
            else dp[j][k] = (dp[j-1][k]||dp[j-1][k-A[j]]);
        }
    }
    //cout<<i<<endl;
    for(int k=max(0ll,K-a[i]);k<=K;++k){
        if(dp[n-1][k])res=1;
        //cout<<k<<" "<<dp[n-1][k]<<endl;
    }
    A.insert(A.begin()+i,a[i]);
    if(res)return true;
    else return false;
}

signed main(){
    cin>>N>>K;
    for(int i=0;i<N;++i){
        cin>>a[i];
        A.PB(a[i]);
        B.PB(a[i]);
    }
    if(N==1){
        cout<<0<<endl;
        return 0;
    }
    sort(a,a+N);
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    int ans = 0;
    int l = 0, r = N-1;
    int mid;
    //for(auto a:A)cout<<a<<" ";
    //cout<<endl;
    if(!solve(r)){
        cout<<N<<endl;
        return 0;
    }
    for(int i=0;i<20;++i){
        mid=(l+r)/2;
        if(!solve(mid))l=mid;
        else r=mid;
        //cout<<l<<" "<<r<<endl;
    }
    if(r==l){
        if(solve(l))cout<<l<<endl;
        else cout<<l+1<<endl;
    }
    //cout<<l<<" "<<r<<endl;
    //int it = upper_bound(A.begin(),A.end(),A[l])-A.begin();
    //cout<<l<<" "<<r<<" "<<mid<<endl;
    else cout<<l+1<<endl;
}


Measured memory_bytes: 195968
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
const ll Mod=1000000007;
const ll INF=999999999999999999;
const ll NN=(ll)(1e6+5);
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
ll n,m;
ll dp[3005][3005][4];
vector<vector<ll>> grid;
ll f(ll i,ll j,ll cnt)
{
    if(i>n||j>m)
     return 0;
    ll &ans=dp[i][j][cnt];
    if(ans!=-1)
     return ans;
    if(cnt==3)
     return ans=f(i+1,j,0);
    if(grid[i][j]==0)
     return ans=max(f(i+1,j,cnt),f(i,j+1,cnt));
    return ans=max(max(f(i+1,j,0),f(i,j+1,cnt)),grid[i][j]+max(f(i+1,j,0),f(i,j+1,cnt+1)));  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {
       ll k,i,j,x,y;
       cin>>n>>m>>k;
       grid.resize(n+1,vector<ll>(m+1));
       for(i=0;i<k;i++)
        cin>>x>>y>>grid[x][y];
       memset(dp,-1,sizeof(dp));
       ll ans=f(1,1,0);
       cout<<ans; 
   }
}

Measured memory_bytes: 356348
#include <iostream>
#include <string>
using namespace std;
int main(){
  string t;
  int ans=0;
  cin>>t;
  for(int i=0;i<t.size();i++){
    if(t.at(i)=='?'){t.at(i)='D';}
  }
  cout << t<<endl;
}
  

Measured memory_bytes: 3748
#include <iostream>
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;

int main(){
  int n;
  cin >> n;
  int m = n % 10;
  if (m == 3)
    cout << "bon" << endl;
  else if (m == 0 || m == 1 || m == 6 || m == 8)
    cout << "pon" << endl;
  else
    cout << "hon" << endl;
  
  return 0;
}

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

using namespace std;

#ifdef WIN32
	#define I64 "%I64d"
#else
	#define I64 "%lld"
#endif

typedef long long ll;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"
#define K 2000

int n, ma, mb;
int a[55];
int b[55];
int c[55];
map <int, int> g;
int ans;

inline void check(int sa, int sb, int sc) {
	int t = __gcd(sa, sb);
	sa /= t;
	sb /= t;
	if (sa == ma && sb == mb) {
		if (ans == -1 || ans > sc) {
			ans = sc;
		}
	}
}

void go(int v, int k, int sa = 0, int sb = 0, int sc = 0) {
	if (v == k) {
		if (sa + sb == 0) return;
		check(sa, sb, sc);
		if (k == n) {
			int val = mb * sa - ma * sb;
			if (g.count(val)) {
				int t = g[val] + sc;
				if (ans == -1 || ans > t) {
					ans = t;
				}
			}
		} else {
			int val = ma * sb - mb * sa;
			if (g.count(val)) {
				g[val] = min(g[val], sc);
			} else {
				g[val] = sc;
			}
		}
		return;
	}
	go(v + 1, k, sa, sb, sc);
	go(v + 1, k, sa + a[v], sb + b[v], sc + c[v]);
}

int main()
{
	#ifdef LOCAL
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	#endif

	scanf("%d%d%d", &n, &ma, &mb);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	}

	ans = -1;
	go(0, n / 2);
	go(n / 2, n);
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <list>
#include <sys/timeb.h>
#include <fstream>
#include <set>

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 reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


bool pairCompare(const Pi& firstElof, const Pi& secondElof)
{
	return firstElof.second > secondElof.second;
}

ll gcd(ll a, ll b) {
	ll temp;
	while (a % b != 0)
	{
		temp = b;
		b = a % b;
		a = temp;
	}
	return b;
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

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

	string s;
	cin >> s;
	string a = s.substr(0, 2);
	string b = s.substr(2, 4);
	//cout << a << ' ' << b << endl;
	int n = stoi(a);
	int m = stoi(b);

	bool isyymm = (0 <= n) && (n <= 99) && (1 <= m) && (m <= 12);
	bool ismmyy = (1 <= n) && (n <= 12) && (0 <= m) && (m <= 99);

	if (isyymm && ismmyy) {
		cout << "AMBIGUOUS" << endl;
	}
	else if (!isyymm && ismmyy) {
		cout << "MMYY" << endl;
	}
	else if (isyymm && !ismmyy) {
		cout << "YYMM" << endl;
	}
	else {
		cout << "NA" << 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);
		String o = sc.next();
		String e = sc.next();

		if (o.length() == e.length()) {
			for (int i = 0; i < e.length(); i++) {
				System.out.print(o.charAt(i));
				System.out.print(e.charAt(i));
			}
		} else {
			for (int i = 0; i < e.length(); i++) {
				System.out.print(o.charAt(i));
				System.out.print(e.charAt(i));
			}
			System.out.print(o.charAt(o.length() - 1));
		}
	}
}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
#define faster  ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define pb push_back
const double PI = acos(-1.0);
using namespace std;

int main()
{
    faster

    int n;
    string s;

    cin>>n>>s;

    int c=0;

    for(int i=0; i<n-2; i++)
    {
        if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
            c++;
    }


    cout<<c<<endl;



    return 0;
}


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

#define int long long
struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
const int MOD = 1e9 + 7;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))

signed main(){
    int x, now = 100;
    cin >> x;
    int ans = 0;
    while(now < x){
        ans++;
        now += now/100;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int gcd(int a, int b){
    if(a < b) swap(a,b);
    if(b == 0) return a;
    else return gcd(b, a%b);
}
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int ngcd = gcd(a,b);
    if(c%ngcd == 0) puts("YES");
    else puts("NO");
    return 0;
}

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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 100000000000000000;
double PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

long long int to_int(string S){
    int n = S.size();
    long long int ans = 0;
    vector<int> B(n);
    for(int i =0;i < n;i++){
      bool frag = 1;
        for(int j = 0;j < 10;j++){
            char a = '0' + j;
            if(S[i] == a){
                B[i] = j;
                frag = 0;
                break;
            }
        }
        if(frag) return -1;
    }
    for(int i = 0;i < n;i++){
        ans += B[i]*pow(10,(n-i-1));
    }
    return ans;
}

int CA[12]{31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
  string S,T;cin >> S >> T;
  cout << T + S << endl;
}

Measured memory_bytes: 764