akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
  vector<int> a;
  a = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
  int k;
  cin >> k;
  cout << a.at(k - 1) << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define null nullptr
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mp make_pair
#define test int t; cin>>t; while(t--)
#define FAST                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

using namespace std;

typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;
typedef unordered_map<int,int> mp;

const int mod = 1e9+7;



int32_t main(){
    FAST;

    int n;  cin >> n;
    cout << ((n)*(n-1))/2 ;
    

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }

vector<vector<char>> OP;
int len;

void func(vector<char> op){
    if(op.size() == len-1){
        OP.push_back(op);
        return;
    }

    op.push_back('+');
    func(op);
    op.pop_back();

    op.push_back('&');
    func(op);
}

int main(){
    string s; cin >> s;
    len = s.size();
    vector<char> v; 
    func(v);
    
    ll res = 0;
    if(OP.empty()) res = stoi(s);
    for(vector<char> op: OP){
        ll sum = 0, num = s[0] - '0';
        rep(i, op.size()){
            if(op[i] == '+'){
                sum += num; num = s[i+1] - '0';
            }else{
                num = num*10 + s[i+1] - '0';
            }
        }
        res += sum + num;
    }

    cout << res << ln;
}


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

//const long long INF = 1000000001;
const int INF = 2147483647;

const long long MOD = 1000000009;

typedef long long ll;

const int max = 100000; //配列の最大長

int main(void){
  std::map<std::string,int> mp;

  int N;
  std::cin >> N;
  for(int i=0; i<N; i++){
    std::string s;
    std::cin >> s;
    mp[s]++;
  }

  int M;
  std::cin >> M;
  for(int i=0; i<M; i++){
    std::string s;
    std::cin >> s;
    mp[s]--;
  }

  int ans = 0;
  for(auto iter=mp.begin(); iter!=mp.end(); iter++){
    if(ans < iter->second){
      ans = iter->second;
    }
  }

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


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

dp = [0] * N
dp[0] = 0
dp[1] = abs(hhh[1] - hhh[0])

for i in range(2, N):
    dp[i] = min(abs(hhh[i] - hhh[i - 1]) + dp[i - 1], abs(hhh[i] - hhh[i - 2]) + dp[i - 2])

print(dp[N-1])


Measured memory_bytes: 13928
n = int(input())
A = [int(input()) for _ in range(n)]
max_idx = A.index(max(A))
max_num = max(A)
second_max_num = sorted(A)[-2]

for i in range(max_idx):
  print(max_num)
print(second_max_num)
for i in range(max_idx+1, n):
  print(max_num)

Measured memory_bytes: 13384
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main(){
  int N;
  cin >> N;
  string S1, S2;
  cin >> S1 >> S2;
  long long int start = 1;
  for (int i = 0; i < N; i++){
    if (S1[i] == S2[i]){
      if (i == 0){
        start *= (long long int)3;
      }else if (S1[i-1] == S2[i-1]){
        start *= (long long int)2;
      }else{
        start *= (long long int)1;
      }
      start %= (long long int)1000000007;      
    }else{
      if (i == 0){
        start *= (long long int)6;
      }else if (S1[i-1] == S2[i-1]){
        start *= (long long int)2;
      }else{
        start *= (long long int)3;
      }
      start %= (long long int)1000000007;
      i++;
    }
  }
  cout << start;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n, k;
    cin >> n  >> k;
    string s;
    cin >> s;
    int diff = 0;
    for (int i = 0; i < n - 1 ; i ++){
        if (s[i] != s[i+1]){
            diff++;
        }
    }
    int ans = n - 1 - max(0, diff - 2* k);
    cout << ans;
    return 0;
}



Measured memory_bytes: 512
from itertools import combinations_with_replacement
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    x = int(readline())

    ab = [i**5 for i in range(10**3)]

    C = combinations_with_replacement(ab, 2)
    for a, b in C:
        if a + b == x:
            print(int(pow(b, 0.2)), -int(pow(a, 0.2)))
            break
        
        if b - a == x:
            print(int(pow(b, 0.2)), int(pow(a, 0.2)))
            break


if __name__ == "__main__":
    main()


Measured memory_bytes: 9460
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	final int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int sx = sc.nextInt();
			int sy = sc.nextInt();
			if ((sx | sy) == 0)
				break;
			int[][] map = new int[10][10];
			int n = sc.nextInt();
			for (int i = 0; i < n; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				map[y][x] = i + 1;
			}
			Queue<Point> q = new LinkedList<Point>();
			q.add(new Point(sx, sy, 0));
			boolean ok = false;
			while (!q.isEmpty()) {
				Point p = q.poll();
				int x = p.x;
				int y = p.y;
				int c = p.c;
				if (c == n + 1) {
					ok = true;
					break;
				}
				if (c != 0) {
					boolean dead = true;
					for (int i = -1; i <= 1; i++) {
						for (int j = -1; j <= 1; j++) {
							int nx = x + j;
							int ny = y + i;
							if (nx >= 0 && ny >= 0 && nx < 10 && ny < 10
									&& map[ny][nx] == c) {
								dead = false;
								i = INF;
								break;
							}
						}
					}
					if (dead)
						continue;
				}
				int dx[] = { 2, 2, 2, 1, 0, -1, -2, -2, -2, -1, 0, 1 };
				int dy[] = { -1, 0, 1, 2, 2, 2, 1, 0, -1, -2, -2, -2 };
				for (int i = 0; i < 12; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx >= 0 && ny >= 0 && nx < 10 && ny < 10) {
						q.add(new Point(nx, ny, c + 1));
					}
				}
			}
			System.out.println(ok ? "OK" : "NA");
		}
	}

	public static void main(String[] args) throws Exception {
		new Main().run();
	}
}

class Point {
	int x;
	int y;
	int c;

	Point(int x, int y, int c) {
		this.x = x;
		this.y = y;
		this.c = c;
	}
}

Measured memory_bytes: 12000
#include <stdio.h>
#include <stdlib.h>

int main(void){
    char s[20];
    scanf("%s", s);
    if(s[5] == '0' && (s[6] =='1'||s[6] =='2'||s[6] =='3'||s[6] =='4')) printf("Heisei");
    else printf("TBD");
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int i,j;
    int H,W;
    
    cin >> H >> W;
    
    vector<char> a(H*W);
    
    //読み込み
    for(i=0;i<H*W;i++) cin >> a[i];
    
    for(i=0;i<W+2;i++) cout << '#';
    cout << endl;
    
    for(i=0;i<H;i++){
        cout << '#';
        for(j=0;j<W;j++) cout << a.at(j+W*i);
        cout << '#' << endl;
    }
    for(i=0;i<W+2;i++) cout << '#';
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    if (N % K == 0) printf("0\n");
    else printf("1\n");
}

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

using namespace std;
// using P = pair<long, long>;
using P = pair<double, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))

#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define concat(xs, ys) (xs).insert((xs).end(), (ys).begin(), (ys).end())

const int mod = 1000000007;

struct Group {
  long base;
  vector<long> xs;
};

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

  string s;
  cin >> s;

  if (s == "SUN") {
    cout << 7 << endl;
  }
    if (s == "MON") {
    cout << 6 << endl;
  }
    if (s == "TUE") {
    cout << 5 << endl;
  }
    if (s == "WED") {
    cout << 4 << endl;
  }
    if (s == "THU") {
    cout << 3 << endl;
  }
    if (s == "FRI") {
    cout << 2 << endl;
  }
    if (s == "SAT") {
    cout << 1 << endl;
  }
}


Measured memory_bytes: 256
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N)]

AB=AB[::-1]
#print(AB)

ans=0
for ab in AB:
  ab[0]+=ans
  ans+=(ab[1]-ab[0]%ab[1])%ab[1]
  #print(ans)
print(ans)

Measured memory_bytes: 31332
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
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;
}
using namespace std;

 
void solve(){
	string s;
    cin>>s;
    vector<int>v(3,0);
    rep(i,s.size()){
        if(s[i]=='a')++v[0];
        else if(s[i]=='b')++v[1];
        else ++v[2];
    }
    sort(begin(v),end(v));
    if(v.back()-v[1]<=1&&v.back()-v[0]<=1)cout<<"YES\n";
    else cout<<"NO\n";
}
 
signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 512
import numpy as np
n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
#d = [[0]*n for x in range(n)]
s = 0
m = 1
for i in range(1, n):
    m = m * i
for i in range(n):
    for j in range(i + 1, n):
        #d[i][j] = ((p[j][0] - p[i][0])**2 + (p[j][1] - p[i][1])**2)**0.5
        s += ((p[j][0] - p[i][0])**2 + (p[j][1] - p[i][1])**2)**0.5*m
        #print("i:{}, j:{} / ({},{}) - ({},{}) d:{}".format(i, j, p[i][0], p[i][1], p[j][0], p[j][1], d[i][j]))
l = m * n / 2
print(s / l)


Measured memory_bytes: 12392
#include <cstdio>
#include <cstring>
#pragma warning(disable : 4996)
#define rng(x, y) (0 <= x && x < W && 0 <= y && y < H)
int H, W, n, gx, gy, x[12][12], d[4] = { 1, 0, -1, 0 };
int solve(int sx, int sy, int depth) {
	if (depth == n) {
		if (sx == gx || sy == gy) return 1;
		return 0;
	}
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		int tx = sx + d[i], ty = sy + d[i ^ 1];
		while (rng(tx, ty)) {
			if (x[ty][tx] == 1) {
				x[ty][tx] = 0;
				ret += solve(tx, ty, depth + 1);
				x[ty][tx] = 1;
				break;
			}
			tx += d[i];
			ty += d[i ^ 1];
		}
	}
	return ret;
}
int main() {
	while (scanf("%d%d", &W, &H), W | H) {
		n = 0;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) scanf("%d", &x[i][j]);
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (x[i][j] == 1) n++;
				if (x[i][j] == 2) gx = j, gy = i;
			}
		}
		printf("%d\n", solve(gx, gy, 0));
	}
	return 0;
}

Measured memory_bytes: 2608
import java.util.*;

class Main{
    public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		int iin = sc.nextInt();
		int iis = 0;
		int iism = 0;
		int iimm = 0;
		int irt = 0;
		TreeMap<Integer,Integer> ihm = new TreeMap<Integer,Integer>();
		for(int i=0;i<iin;i++){
			iis = sc.nextInt();
			if(iis<iism || i==0){
				iism = iis;
			}
			if(iis>iimm || i==0){
				iimm = iis;
			}
			if(ihm.containsKey(iis)){
				int iat = ihm.get(iis);
				iat++;
				ihm.put(iis, iat);
			}
			else{
				ihm.put(iis, 1);
			}
		}
		for(int i=iism;i<=iimm;i++){
			iis = 0;
			if(ihm.containsKey(i-1)){
				iis += ihm.get(i-1);
			}
			if(ihm.containsKey(i)){
				iis += ihm.get(i);
			}
			if(ihm.containsKey(i+1)){
				iis += ihm.get(i+1);
				iism = i + 1;
			}
			if(irt<iis){
				irt = iis;
			}
			else if(iis==0){
				i = ihm.higherKey(i) - 1;
			}
		}
		System.out.println(irt);
    }
}


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

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr int INF = 1001001001;

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 (a>b) { a=b; return 1; } return 0; }

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    
    int ans = min(n * a, b);
    cout << ans << endl;
    
    return 0;
}


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

using namespace std;

int main(void) {
  
  int N;
  cin >> N;
  if (N % 1000 == 0) {
    cout << 0 << endl;
  } else {
    cout << (N / 1000 + 1) * 1000 - N << endl;
  }

}


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

using namespace std;

#define rep(i, a, b)  for(int i = (a); i < (b); i++)
#define rrep(i, a, b) for(int i = (a); i > (b); i--)
#define sq(x) ((x) * (x))
#define bit(x) bitset<32>(x)
#define vsort(v)  sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<llint>())
#define debug(x) cout << #x << " " << (x) << endl
#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


template<typename Tn> Tn __lcm(Tn a, Tn b)
{
    return a / __gcd(a, b) * b;
}

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

int main()
{
    int n;
    int d[100001];

    ci >> n;
    rep(i, 0, n) ci >> d[i];

    sort(d, d + n);

    co << d[n / 2] - d[n / 2 - 1] << en;
    
  
    return 0;
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
I=lambda:int(input())
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))

N,T=MI()
dp=[[0]*(T+1) for _ in [0]*(N+1)]
food=[tuple(MI()) for _ in [0]*N]
food.sort()

for n in range(N):
    a,b=food[n]
    for t in range(T+1):
        if t<T:
            # たべる
            dp[n+1][min(t+a,T)]=max(dp[n][t]+b,dp[n+1][min(t+a,T)])
        # たべない
        dp[n+1][t]=max(dp[n][t],dp[n+1][t])
print(dp[N][T])

Measured memory_bytes: 139604
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   " << endl;
		for(int j=0; j<v[i].size(); j++){
			cout << v[i][j] << "   ";
		}
		cout << endl;
	}
}




int main(){//
	int H, N;
	cin >> H >> N;
	vector<int> A(N), B(N);
	for(int i=0; i<N; i++) cin >> A[i] >> B[i];

	const int H_MAX = 10000;
	const int B_MAX = 10000;
	const int INF = H_MAX*B_MAX+1;
	//dp[n][h]: 0~n-1番目までの魔法を考慮して体力hを減らすのに必要な最小魔力
	vector<vector<int>> dp(N+1, vector<int>(H+H_MAX+1, INF));
	dp[0][0] = 0;//魔法使わないで体力0を減らすのに必要な魔力は0
	for(int n=0; n<=N; n++) dp[n][0] = 0;

	for(int n=0; n<N; n++){
		for(int h=0; h<=H+H_MAX; h++){
			dp[n+1][h] = min(dp[n+1][h], dp[n][h]+0*B[n]);//魔法n番を使わない
			if(h+A[n] < (int)dp[0].size()) dp[n+1][h+A[n]] = min(dp[n+1][h+A[n]], dp[n][h] + B[n]);//魔法nを使う(1回目)
			if(h+A[n] < (int)dp[0].size()) dp[n+1][h+A[n]] = min(dp[n+1][h+A[n]], dp[n+1][h]+B[n]);//魔法nを使う(2回目以降)(1回目の時のh+A[n]が今回のhと等しくなる時に影響)
		}
	}
	//print_vec2(dp);
	int ans = INF;
	for(int h=H; h<=H+H_MAX; h++){//答えは体力H以上削った場合の最小消費体力
		ans = min(ans, dp[N][h]);
	}
	cout << ans << endl;

}


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

int main(){
  int64_t N,M;
  int64_t mod=1e9+7;
  cin >> N >> M;
  vector<int64_t> a(M);
  for(int64_t i=0;i<M;i++){
    cin >> a.at(i);
  }
  vector<int64_t> ans(N+1,0);
  ans.at(0)=1;
  vector<bool> flag(N+1,true);
  for(int64_t i=0;i<M;i++){
  flag.at(a.at(i))=false;
  }
  if(M>0){
    if(a.at(0)!=1){
      ans.at(1)=1;
    }
  }else{
    ans.at(1)=1;
  }
  for(int64_t i=2;i<=N;i++){
    if(!flag.at(i)){
      continue;
    }
    ans.at(i)=ans.at(i-1)+ans.at(i-2);
    ans.at(i)%=mod;
  }
  cout << ans.at(N) << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int A[55][55];
vector<vector<int> >s[55];
int n,m,a[3],x,y,d[55];
int dp[111][55][55];
int main(){
  cin>>n>>m;
  r(i,3)cin>>a[i];
  r(i,m){
    cin>>x>>y;
    x--;y--;
    A[x][y]=1;
    dp[1][x][y]=1;
  }
  r(i,55)s[i].resize(n);
  for(int i=1;i<101;i++){
    r(j,n){
      r(k,n)if(dp[i][j][k]){
        r(l,n){
          if(A[k][l]){
            dp[i+1][j][l]=1;
          }
        }
      }
    }
  }
  r(i,3){
    r(j,n){
      r(k,n){
        if(dp[a[i]][j][k]){
          s[j][i].push_back(k);
        }
      }
    }
  }
  r(i,n)d[i]=1e8;
  d[n-1]=0;
  while(1){
    r(i,n){
      int X=0;
      r(j,3){
        int c=1e8;
        r(k,s[i][j].size()){
          x=s[i][j][k];
          c=min(c,d[x]);
        }
        X=max(X,c);
      }
      X++;
      if(d[i]>X){
        d[i]=X;
        goto L;
      }
    }
    break;
    L:;
  }
  if(d[0]==1e8) cout<<"IMPOSSIBLE"<<endl;
  else cout<<d[0]<<endl;
}


Measured memory_bytes: 4472
import java.util.*;

public class Main {

    public static void main(String[] args) {
//        long startTime = System.currentTimeMillis();
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Map<Integer, Map.Entry<String, Integer>> spMap = new HashMap<>();

        for (int i = 0; i < N; i++) {
            Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<>(scanner.next(), scanner.nextInt());
            spMap.put(i, entry);
        }
        scanner.close();

        List<Map.Entry<Integer, Map.Entry<String, Integer>>> entryList = new ArrayList<>(spMap.entrySet());

        //compareを使用して値を比較する
        Collections.sort(entryList, (obj1, obj2) -> {
            //降順
            return obj2.getValue().getValue().compareTo(obj1.getValue().getValue());
        });

//        entryList.forEach(integerEntryEntry -> {
//            Map.Entry<String,Integer> map = integerEntryEntry.getValue();
//            System.out.println(map.getKey()+" "+map.getValue());
//        });
//
//        System.out.println("========");

        // keyを昇順
        Collections.sort(entryList, Comparator.comparing(obj -> obj.getValue().getKey()));

//        entryList.forEach(integerEntryEntry -> {
//            Map.Entry<String,Integer> map = integerEntryEntry.getValue();
//            System.out.println(map.getKey()+" "+map.getValue());
//        });

        // out
        entryList.forEach(entry ->
                System.out.println((entry.getKey()+1))
        );
//        System.out.println(System.currentTimeMillis() - startTime);
    }


}


Measured memory_bytes: 26448
#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 each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

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

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 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> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(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) { each(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; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { cout << p.first << ' ' << p.second; return os; }

void solve() {
  pqasc<int> fr;
  pqdesc<int> ba;

  int N; cin >> N;
  vi32 a(3 * N); cin >> a;

  i64 fsum = 0, bsum = 0;
  rep(i, N) fr.push(a[i]), fsum += a[i];
  rep(i, N) ba.push(a[i + 2 * N]), bsum += a[i + 2 * N];

  vi64 fsums(N + 1), bsums(N + 1);
  fsums[0] = fsum, bsums[N] = bsum;

  for (int i = N; i < 2 * N; i++) {
    if (fr.top() < a[i]) {
      fsum = fsum - fr.top() + a[i];
      fr.pop(), fr.push(a[i]);
    }
    fsums[i - N + 1] = fsum;
  }
  for (int i = 2 * N - 1; i >= N; i--) {
    if (ba.top() > a[i]) {
      bsum = bsum - ba.top() + a[i];
      ba.pop(), ba.push(a[i]);
    }
    bsums[i - N] = bsum;
  }

  i64 ans = -1e18;
  rep(i, N + 1) amax(ans, fsums[i] - bsums[i]);
  cout << ans << '\n';
}


Measured memory_bytes: 3960
#include<iostream>
#include<algorithm>
#define MOD 1000000007
#define Nmax 2000010
using namespace std;

//***
long long inv[Nmax],fact[Nmax],invfact[Nmax];
void PRE(){
	inv[1]=fact[0]=invfact[0]=1;
	for(int i=1;i<Nmax;i++){
		if(i>1)inv[i]=(MOD-(MOD/i)*inv[MOD%i]%MOD)%MOD;
		fact[i]=fact[i-1]*i%MOD;
		invfact[i]=invfact[i-1]*inv[i]%MOD;
	}
}
long long C(int n,int k){
	return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;
}
//***

int vis[100010];
int main(){
	PRE();
	int n,m;cin>>n;
	for(int i=0;i<100010;i++)vis[i]=-1;
	for(int i=0;i<=n;i++){
		int a;cin>>a;a--;
		if(vis[a]!=-1){
			m=n+vis[a]-i;
		}
		else vis[a]=i;
	}
	for(int k=1;k<=n+1;k++){
		long long ans=C(n+1,k);
		if(k-1<=m){
			ans-=C(m,k-1);
		}
		ans%=MOD;
		if(ans<0)ans+=MOD;
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 48512
/*-- ILSH  --*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;

#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < int > 
#define pii pair< ll, ll > 
#define len length 
#define fi first
#define se second
#define dt cout<<"HEre\n";
#define sz size
const ll inf=1e18+1e17;
const ll mod = 1e9+7;


ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}
const ll N=4e5+5;
ll arr[N];

void solve() {
	int n;
	cin>>n;
	ll val=1000;
	for ( int i=0;i<n;i++)
		cin>>arr[i];
	for ( int i=0;i<n-1;i++)
		if ( arr[i+1]>arr[i])
			val=(val/arr[i])*arr[i+1]+val%arr[i];
		cout<<val<<'\n';
  
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie( NULL);
	cout.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen ("INPUT.txt" , "r" , stdin);
		freopen ("OUTPUT.txt", "w" , stdout);
	#endif
	ll t=1;
//	cin>>t;
	for ( ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
    	solve();
    }
    //	cout << clock() / double(CLOCKS_PER_SEC) << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 3e5 + 5, M = 1e9 + 5;
ll w[N], v[N], dp[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	ll n, W;
	cin >> n >> W;
	for(ll i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for(ll i = w[1]; i <= W; i++) dp[i] = v[1];
	for(ll i = 2; i <= n; i++)
		for(ll j = W; j >= w[i]; j--)
			dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
	cout << dp[W];
}

Measured memory_bytes: 5120
#include<iostream>
#include<string>
#include<algorithm>
#include<cctype>
#include<vector>
#include<map>
#include<iomanip>
using namespace std;
#define fr first
#define sc second
typedef pair<int,int> P;
int main(){
  int X,Y,Z,N,E,A;
  while(cin >> X >> Y >> Z , X){
    int jump[X];
    P ivent[Y+1];
    for(int i = 0 ; i <= Y ; i++ ) ivent[i] = P( 0 , 0 );
    double dp[51][5001]={{}};
    dp[0][0] = 1.0;

    for(int i = 0 ; i < X ; i++ ){
      cin >> jump[i];
    }
    for(int i = 0 ; i < Z ; i++ ){
      cin >> N >> E >> A;
      switch(E){
      case 1: ivent[N].fr = A; break;
      case 2: ivent[N].sc = A; break;
      case 3: ivent[N].sc = -A; break;
      }
    }
    for(int i = 0 ; i < Y ; i++ ){
      for(int j = 0 ; j < 5001 ; j++ ){
        if(dp[i][j]){
          for(int k = 0 , p_mas , p_money ; k < X ; k++ ){
            p_mas = min( i + jump[k] , Y );
            p_money = max(0,ivent[p_mas].sc + j );
            p_mas = min( p_mas + ivent[p_mas].fr , Y );

            dp[p_mas][p_money] += dp[i][j] / X;
          }
        }
      }
    }
    double ans = 0.0;
    for(int i = 0 ; i < 5001 ; i++ ){
      ans += dp[Y][i] * i;
    }
    cout << (int)ans << endl;
  }
}

Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  string s;
  cin>>s;
  int ans = 0;
  for (int i=1; i<n-1; i++) {
    string s1 = s.substr(0, i);
    string s2 = s.substr(i, n - 1);
    set<char> cs1(s1.begin(), s1.end());
    set<char> cs2(s2.begin(), s2.end());
    int cnt = 0;
    for (char c: cs1) {
      if (cs2.find(c) != cs2.end()) {
        ++cnt;
      }
    }
    ans = max(cnt, ans);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>

using namespace std;

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

int buy_A(int n){
	return 5*380*0.80*(int)(n/5) + 380 * (n%5);
}

int buy_B(int n){
	return 4*550*0.85*(int)(n/4) + 550 * (n%4);
}

int buy_C(int n){
	return 3*850*0.88*(int)(n/3) + 850 * (n%3);
}

int main(){
	int W;
	while(~scanf("%d",&W)){
		if(W==0) break;
		W/=100;
		int res=numeric_limits<int>::max();


		//25,17,10
		for(int a=0; a<=30;a++){
			for(int b=0; b<=30;b++){
				for(int c=0; c<=30;c++){
					if(a*2+b*3+c*5 - W == 0){
						res = min(res,buy_A(a)+buy_B(b)+buy_C(c));
					}

				}
			}

		}

		cout << res << endl;

	}
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int h,w; cin>>h>>w;
	vector<string>s(h); for(auto&&i:s)cin>>i;
	vector<vector<int>>L(h+2,vector<int>(w+2,0)),R(h+2,vector<int>(w+2,0)),
	U(h+2,vector<int>(w+2,0)),D(h+2,vector<int>(w+2,0));
	for(int i=1;i<h+1;++i){
		for(int j=1;j<w+1;++j){
			if(s.at(i-1).at(j-1)=='.'){
				L.at(i).at(j)=L.at(i).at(j-1)+1;
				U.at(i).at(j)=U.at(i-1).at(j)+1;
			}
			if(s.at(h-i).at(w-j)=='.'){
				R.at(h+1-i).at(w+1-j)=R.at(h+1-i).at(w+2-j)+1;
				D.at(h+1-i).at(w+1-j)=D.at(h+2-i).at(w+1-j)+1;
			}
		}
	}
	int ans=0;
	for(int i=1;i<h+1;++i){
		for(int j=1;j<w+1;++j){
			ans=max(ans,L.at(i).at(j)+R.at(i).at(j)+U.at(i).at(j)+D.at(i).at(j)-3);
		}
	}
	cout<<ans<<"\n"s;
}

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

#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

const int N = 2e5 + 11;



int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s,t;
    cin>>s>>t;
    int l=t.length();
    if (s==t.substr(0,l-1))
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    
    
}


Measured memory_bytes: 3652
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int p[1000000];
int main()
{
	for (int i = 2; i < 1000; ++i)
	{
		if (!p[i])
		{
			for (int j = 2*i; j < 1000000; j += i)
				p[j] = 1;
		}
	}

	int n;
	while (scanf("%d", &n), n)
	{
		int ans = 0;
		for (int i = 3; i <= n/2; ++i)
			if (!p[i] && !p[n-i])
				++ans;
		printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 0
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B
import qualified Data.Array.IArray as A
import qualified Data.Map.Strict as M

main = do
  [n,m] <- map read . words <$> getLine
  es <- readUndirectedEdge <$> B.getContents
  print (nsp n m es)

nsp n m es = div (foldr (check n memo) 0 es) 2
  where
    memo = warshallFloyd n es

check n memo ((i,j),w) acc
  | any (\x -> abs (memo !? (x,j) - memo !? (x,i)) == w) [1..n] = acc
  | otherwise = acc + 1

(!?) m k = M.findWithDefault 100000 k m

type Memo = M.Map (Vertex, Vertex) Weight

warshallFloyd :: Int -> [Edge] -> Memo
warshallFloyd n es = foldl shorten m0 kij
  where
    m0 = M.fromList es
    kij = [(k, i, j) | k <- [1 .. n], i <- [1 .. n], j <- [1 .. n]]

shorten :: Memo -> (Vertex, Vertex, Vertex) -> Memo
shorten m (k, i, j)
  | i == j = M.insert (i, j) 0 m
  | otherwise = case connect m k i j of
    Nothing -> m
    Just w -> M.insertWith min (i, j) w m

connect :: Memo -> Vertex -> Vertex -> Vertex -> Maybe Weight
connect m k i j = do
  w1 <- M.lookup (i, k) m
  w2 <- M.lookup (k, j) m
  return (w1 + w2)

type Bound = (Vertex, Vertex)
type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), Weight)
type Path = [Vertex]
type Graph = A.Array Vertex (S.Set (Vertex, Weight))

buildG :: Bound -> [Edge] -> Graph
buildG b = A.accumArray (flip S.insert) S.empty b . map (\((s, t), w) -> (s, (t, w)))

from :: Graph -> Vertex -> S.Set (Vertex, Weight)
from = (A.!)

size :: Graph -> Int
size g = let (i,j) = A.bounds g in j - i + 1

readUndirectedEdge :: B.ByteString -> [Edge]
readUndirectedEdge = concatMap (constructTwoWay . map readInt . B.words) . B.lines

constructTwoWay :: [Int] -> [Edge]
constructTwoWay [s,t,w] = [((s, t), w), ((t, s), w)]
constructTwoWay _ = undefined

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt


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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define size(x) int(x.size())
#define pb push_back

using namespace std;
using ll=long long;
using pii= pair<int, int>;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x,y;
    cin>>x>>y;
    for(int i=0;i<=x;i++){
        if(2*i+4*(x-i)==y){
            cout<<"Yes\n";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}



Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
typedef long long LL;
using namespace std;
int main() {
	int n;
	scanf("%d",&n);
	vector<int>array;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int temp;
		scanf("%d", &temp);
		ans += temp;
	}
	printf("%d\n", ans - n);
	return 0;

}

Measured memory_bytes: 504
#include "bits/stdc++.h"
using namespace std;

int N, M, S, T, INF = 1145141919;
static int Dis[100000][4] = {};
static vector<int> V[100000];

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) for (int j = 0; j < 4; j++) Dis[i][j] = INF;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		V[u].push_back(v);
	}
	cin >> S >> T;
	S--, T--;
	Dis[S][0] = 0;
	queue<pair<int, int> > Q;
	for (int i : V[S]) Q.push({ i, 1 });
	while (!Q.empty()) {
		pair<int, int> p = Q.front();
		Q.pop();
		if (Dis[p.first][p.second % 3] != INF) continue;
		Dis[p.first][p.second % 3] = p.second;
		for (int next : V[p.first]) {
			if (Dis[next][(p.second + 1) % 3] == INF) {
				Q.push({ next, p.second + 1 });
			}
		}
	}
	if (Dis[T][0] == INF) {
		cout << -1;
		return 0;
	}
	cout << Dis[T][0] / 3;
}

Measured memory_bytes: 7296
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <ctime>
#include <map>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;



int main()
{
    // 整数の入力
    ll N,K,total;
    cin >> N >> K;
    total = 0;
    for(int i = 0;i<N;i++){
        ll h;
        cin >> h;
        if(h >= K){
            total++;
        }
    }

    cout << total << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

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

    int h, w, k;
    cin >> h >> w >> k;

    if(w == 1){
        cout << 1 << endl;
        return 0;
    }

    vector<vector<int>> line(w, vector<int>(w));
    rep(s, 1 << (w - 1)){
        bool ok = true;
        rep(i, w - 2){
            if((s >> i) % 2 == 1 && (s >> (i + 1)) % 2 == 1){
                ok = false;
            }
        }
        if(not ok){
            continue;
        }

        vector<int> pos(w);
        rep(i, w) pos[i] = i;

        rep(i, w - 1){
            if((s >> i) % 2 == 0){
                continue;
            }
            swap(pos[i], pos[i+1]);
        }
        rep(i, w){
            line[i][pos[i]]++;
        }
    }

    vector<vector<int>> dp(h+1, vector<int>(w));
    dp[0][0] = 1;
    rep(i, h){
        rep(j, w){
            rep(l, w){
                dp[i+1][l] += dp[i][j] * line[j][l] % MOD;
                dp[i+1][l] %= MOD;
            }
        }
    }
    cout << dp[h][k-1] << endl;

    return 0;
}


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

int n,t;

inline int qr()
{
	int w=1,x=0;char a=0;
	while(a<'0'||a>'9'){if(a=='-')w=-1;a=getchar();}
	while(a>='0'&&a<='9'){x=(x<<3)+(x<<1)+(a^48);a=getchar();}
	return x*w;
}

int main()
{
	n=qr();
	t=qr();
	if(n%t==0)
		printf("%d\n",n/t);
	else
		printf("%d\n",n/t+1);
	return 0;
} 

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

As = list(map(int, input().split()))

A_minus = []
minus_A_minus = []

for i in range(n):
    A_minus.append(As[i] - i - 1)
    minus_A_minus.append(-As[i] - i - 1)

dic_AM = {}
dic_MAM = {}

for i in range(n):
    AM = A_minus[i]
    MAM = minus_A_minus[i]
    if dic_AM.get(AM, None) is None:
        dic_AM[AM] = 1
    else:
        dic_AM[AM] += 1
    if dic_MAM.get(MAM, None) is None:
        dic_MAM[MAM] = 1
    else:
        dic_MAM[MAM] += 1

ans = 0

for k in dic_AM:
    if k in dic_MAM:
        ans += dic_AM[k] * dic_MAM[k]

print(ans)

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

typedef long long ll;

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

    int r, g, b, N;
    cin>>r>>g>>b>>N;

    int ans = 0;
    for (int i=0;i<=N;++i){
        for (int j=0;j<=N;++j){
            int res = i*r + j*g;
            if (N>=res && (N-res)%b==0) ans++;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 256
def solve():
  n = int(input())
  works = [list(map(int, input().split())) for i in range(n)]
  works = sorted(works, key=lambda x:x[1])
  if works[0][0] > works[0][1]:
    print("No")
    exit()
  sum = 0
  for i in works:
    sum += i[0]
    if sum > i[1]:
      print("No")
      exit()
  print("Yes")
  return 0
 
if __name__ == "__main__":
  solve()


Measured memory_bytes: 55208
#!/usr/bin/env python


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    b = list(reversed(b))
    bad = next((x for x, y in zip(a, b) if x == y), None)
    if bad is None:
        print('Yes')
        print(' '.join(map(str, b)))
    else:
        l_1 = sum(1 for x, y in zip(a, b) if x < bad < y)
        l_2 = sum(1 for x, y in zip(a, b) if x < y and bad in (x, y))
        l_3 = sum(1 for x, y in zip(a, b) if x == y)
        l_4 = sum(1 for x, y in zip(a, b) if x > y and bad in (x, y))
        l_5 = sum(1 for x, y in zip(a, b) if x > bad > y and x != bad)
        if l_3 > l_1 + l_5:
            print('No')
        else:
            good_part = b[:l_1] + b[l_1 + l_2 + l_3 + l_4:]
            bad_part = b[l_1 + l_2:l_1 + l_2 + l_3]
            b[l_1 + l_2:l_1 + l_2 + l_3] = good_part[:l_3]
            good_part[:l_3] = bad_part
            b[:l_1] = good_part[:l_1]
            b[l_1 + l_2 + l_3 + l_4:] = good_part[l_1:]
            assert all(x != y for x, y in zip(a, b))
            print('Yes')
            print(' '.join(map(str, b)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 42980
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<string>
#include<sstream>
#include<cmath>
#include<climits>
#include<algorithm>
#include<bitset>
#include<set>
#include<stack>
#include<queue>
#include<iomanip>
#include<memory.h>
#include<complex>
using namespace std;  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tuple<int,int> tii;
#define rep(i,n) for(ll i=0;i<(n);i++)  
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second  
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-5;
const double PI = M_PI;  
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define SHOWARRAY(ar,i,j) REP(a,i)REP(b,j)cerr<<ar[a][b]<<((b==j-1)?((a==i-1)?("\n\n"):("\n")):(" "))
#define DIV int(1e9+7)
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}

/* Coding Space*/
vector<ll> table;
ll a,b;

bool check(ll t){
  vector<ll> h = table;
  ll times = t;
  rep(i,h.size()){
    ll nowh = h[i] - t*b;
    if(nowh > 0){
      ll d = (nowh + (a-b-1))/(a-b);
      times -= d;
      if(times < 0) return 0;
    }
  }
  return 1;
}

int main(){
  ll n; cin >> n >> a >> b;
  rep(i,n){
    ll in; cin >> in;
    table.pb(in);
  }
  ll bottom = 0;
  ll top = INF;
  int times = 50;
  while(check(top)){
    ll middle = (bottom+top)/2;
    if(check(middle))
      top = middle;
    else
      bottom = middle;
    times--;
    if(times == 0)  top--;
  }
  cout << top+1 << endl;
  return 0;
}

Measured memory_bytes: 1908
const input = require('fs').readFileSync('/dev/stdin', 'UTF-8');

const watch = input => {
  const time = Number(input);
  const h = Math.floor(time / 3600);
  const m = Math.floor((time - h * 3600) / 60);
  const s = Math.floor(time - h * 3600 - m * 60);
  console.log([h, m, s].join(':'));
};

watch(input);



Measured memory_bytes: 15096
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <sstream>
#include <climits>
#include <cmath>
#include <map>
#include <stack>
using namespace std;
#define M_PI 3.141592
#define toRad 2.0*M_PI/360.0
#define inin(x) int x;cin>>x;
#define all(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" "<<x<<endl;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define EPS 1e-12
#define pri_max 60000
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

/*
bool memo[pri_max] = {};
vector<int> pri;
void calc()
{
	for (int i = 2; i < pri_max; i++)
	{
		if (memo[i] == false)
		{
			pri.push_back(i);
			for (int l = i; l < pri_max; l += i)
			{
				memo[l] = true;
			}
		}
	}
}*/

int n,m, p, d;
bool b[32][12];
int amida()
{
	int now = m;
	for (int i = 0; i <= d + 1; i++)
	{
		if (b[i][now])now = now + 1;
		else if (b[i][now - 1])now = now - 1;
	}
	return now;
}

int main()
{
	
	while (cin >> n&&n)
	{
		bool ok = true;
		memset(b, 0, sizeof b);
		cin >> m >> p >> d;
		for (int i = 1; i <= d; i++)
		{
			for (int l = 1; l < n; l++)
			{
				char c;
				cin >> c;
				b[i][l] = c == '1';
			}
		}

		if (amida()==p)
		{
			cout << 0 << endl;
			continue;
		}
		for (int i = 1; i <= d&&ok; i++)
		{
			for (int l = 1; l < n; l++)
			{
				if (b[i][l] == 0 && b[i][l - 1] == 0 && b[i][l + 1] == 0)
				{
					b[i][l] = true;
					if (amida() == p)
					{
						cout << i << " "<<l << endl;
						ok = false;
						break;
					}
					b[i][l] = false;
				}
			}
		}
		if (ok)
		{
			cout << 1 << endl;
		}
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <iomanip>
using namespace std;

int main(void){
    int n;
    int count = 0;
    int ans = 0;
    cin >> n;
    int a[n]; int b[n-1];
    for(int i = 0; i < n-1; i++)
        cin >> b[i];
    for(int i = 0; i < n-1; i++){
        if(i == 0)
            ans += (b[i] + min(b[i], b[i+1]));
        else if(i > 0 && i < n-2)
            ans += min(b[i], b[i+1]);
        else
            ans += b[i];
    }

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

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}

constexpr int size = 100001;
int visited[size] = {0};

int main() {
    fastio();
    int N, M, a, b;
    scanf("%d %d\n", &N, &M);
    vector<vector<int>> G(N + 1, vector<int>(0));
    REP(i, M) {
        scanf("%d %d\n", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int s = 1, t = G[1][0];
    list<int> ans = {s, t};
    visited[s] = visited[t] = 1;
    bool fs = true, ft = true;
    while(fs || ft) {
        if(fs) {
            fs = false;
            for(auto& x : G[s]) {
                if(!visited[x]) {
                    s = x; fs = true;
                    ans.push_front(s);
                    break;
                }
            }
            visited[s] = 1;
        }
        if(ft) {
            ft = false;
            for(auto& x : G[t]) {
                if(!visited[x]) {
                    t = x; ft = true;
                    ans.push_back(t);
                    break;
                }
            }
            visited[t] = 1;
        }
    }
    printf("%d\n", ans.size());
    for(auto it = ans.begin(); it != ans.end(); it++) printf("%d ", *it);
    printf("\n");
	return 0;
}


Measured memory_bytes: 9856
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
int main() {
  string a,b,c;
  cin >> a >> b >> c;
  cout << (char)toupper(a[0]) << (char)toupper(b[0]) << (char)toupper(c[0]) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  unsigned short *A, *B;
  int C[VMAX+1];
  int n, i, j;

  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  /* your code */
  for(i=0;i<=VMAX;i++) C[i]=0;
  for(i=0;i<n;i++){
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;
  }
  for(i=1;i<=VMAX;i++) C[i]=C[i]+C[i-1];

  for(j=1;j<=n;j++){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

  for(i=1;i<=n;i++){
    if(i>1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  
  return 0;
}



Measured memory_bytes: 9588
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using PL = pair<long long, long long>;
const int INF = 1001001007;

int main(){
    int n; cin >> n;
    vector<int> ar(n);
    rep(i,n){
        cin >> ar[i];
        ar[i]--;
    }
    vector<bool> ts(n, false);
    int ima = 0;
    ts[0] = true;
    bool t = true;
    int cnt = 0;
    while (ima != 1 && t){
        ima = ar[ima];
        if (ts[ima] == true) t = false;
        else ts[ima] = true;
        cnt++;
    }
    if (t) cout << cnt << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 640