akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, M;
  long long K;
  cin >> N >> M;
  cin >> K;
  vector<long long> a(N);
  vector<long long> aa(N+1);
  vector<long long> b(M);
  vector<long long> bb(M+1);
  
  aa[0] = 0;
  bb[0] = 0;
  
  for (long long i = 0; i < N; i++) {
    cin >> a.at(i);
    aa[i+1] = a.at(i) + aa.at(i);
  }
  
  for (long long i = 0; i < M; i++) {
    cin >> b.at(i);
    bb[i+1] = b.at(i) + bb.at(i);
  }

  // 読んだ本の回数
  long long count = 0;
  long long checkpoint_b = M;
  
  for (int i = 0; i < N + 1; i++) {
  	if (aa.at(i) > K) {
      break;
    }
    while (bb.at(checkpoint_b) > K - aa.at(i)) {
    	checkpoint_b--;
    }
    count = max(count, i + checkpoint_b);
  }
 
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 9576
#include<stdio.h>
int main(){
    int tate,yoko,menseki,syuu;
    scanf("%d %d",&tate,&yoko);
    menseki = tate * yoko;
    syuu = (tate *2) + (yoko * 2);
    printf("%d %d\n",menseki,syuu);
    return 0;
}


Measured memory_bytes: 2104
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979

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; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文

int main() {
	int a, b;
	cin >> a >> b;
	cout << (a * 3 + b) / 2 << endl;
}


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

ab.sort(key=lambda x: x[0])

cnt = 0
i = 0
while True:
    a, b = ab[i]
    cnt += b
    if cnt >= K:
        print(a)
        exit()
    i += 1

Measured memory_bytes: 18664
N, Y = map(int, input().split())

a = 0
for x in range(N+1): 
    for y in range(N-x+1):
        if (10000*x + 5000*y + 1000*(N-x-y)) == Y:
            print(str(x)+" "+str(y)+" "+str(N-x-y))
            a = 1
            break
    if a == 1:
        break

if a != 1:
    print("-1 -1 -1")

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool letter_occurence[26];

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

    for (int i = 0; i < s.length(); ++i)
    {
        letter_occurence[(int)(s[i] - 97)] = true;
    }
    
    for (int i = 0; i < 26; ++i)
        if (!letter_occurence[i])
        {
            cout << (char)(i + 97) << '\n';
            return 0;
        }

    cout << "None\n";
}

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

int gcd(int x, int y) {
    int t;

    if(x==0 || y==0)
        return max(x,y);
    
    if(x<y)
        swap(x,y);
    do {
        t = x%y;
        x = y;
        y = t;
    } while(y != 0);
    return x;
}

int main() {
    int N,i,m=1;
    cin >> N;
    vector<int> A(N),L(N+1),R(N+2);
    L.at(0)=0, R.at(N+1)=0;

    for(i=0; i<N; i++) {
        cin >> A.at(i);
        L.at(i+1) = gcd(L.at(i), A.at(i));
    }
    for(i=0; i<N; i++)
        R.at(N-i) = gcd(R.at(N+1-i), A.at(N-1-i));
    for(i=0; i<N; i++)
        m = max(m, gcd(L.at(i), R.at(i+2)));
        
    cout << m << endl;
}

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

int main() {
    int n;
    while (1) {
        cin >> n;
        if (!n) return 0;
        vector<int> v(n);
        
        for (int i = 0; i < n; i++) {
            cin >> v.at(i);
        }
        
        sort(v.begin(), v.end());
        
        int diff;
        for (int i = 1; i < n; i++) {
            if (i == 1) {
                diff = v.at(i) - v.at(i-1);
            } else {
                if (diff > (v.at(i) - v.at(i-1))) {
                    diff = v.at(i) - v.at(i-1);
                }
            }
        }
        
        cout << diff << endl;
    }
}


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

void solve(long long N)
{
    cout << (1 + N) * N / 2 - ((1 + (N / 3)) * (N / 3) / 2) * 3 - ((1 + (N / 5)) * (N / 5) / 2) * 5 + ((1 + (N / 15)) * (N / 15) / 2) * 15 << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    solve(N);
    return 0;
}


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

const int MAX = 1000001;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int X, Y;
    cin >> X >> Y;

    if ((X + Y) % 3 != 0) {
        cout << 0 << endl;
        return 0;
    } else {
        ll move = (X + Y) / 3;
        COMinit();
        cout << COM(move, move * 2 - X) << endl;
    }
}

Measured memory_bytes: 27032
#include<bits/stdc++.h>
using namespace std;
long long n,i;
int main()
{
    cin>>n;
    long long  sum=1000000000000;
    for(i=1; i<=sqrt(n); i++)
	{
        if(n%i==0)
        {
            if(sum > i+(n/i)-2)
            {
             //   cout<<i<<" "<<n/i<<endl;
                sum = i+(n/i)-2;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define N 2002
using namespace std;
struct team{
  int tnum;
  int correct;
  int time;
};
int main(){
  int m,t,p,r,im[N],it[N],ip[N],ij[N],incorrect,i,j;
  struct team data[51];
  while(1){
    cin >> m >> t >> p >> r;
    if(m==0&&t==0&&p==0&&r==0) break;
    for(i=0;i<r;i++) cin >> im[i] >> it[i] >> ip[i] >> ij[i];
    for(i=1;i<=t;i++){
      data[i].tnum=i;
      data[i].correct=0;
      data[i].time=0;
    }
    for(i=0;i<r;i++){
      if(ij[i]==0){
	data[it[i]].correct++;
      	incorrect=0;
	for(j=0;j<i;j++){
	  if(it[i]==it[j]&&ip[i]==ip[j]) incorrect++;
	}
	data[it[i]].time=data[it[i]].time+incorrect*20+im[i];
      }
    }
    for(i=0;i<=t;i++){
      for(j=2;j<=t;j++){
	if(data[j].tnum>data[j-1].tnum) swap(data[j],data[j-1]);
      }
    }
    for(i=0;i<=t;i++){
      for(j=2;j<=t;j++){
	if(data[j].time<data[j-1].time) swap(data[j],data[j-1]);
      }
    }
    for(i=0;i<=t;i++){
      for(j=2;j<=t;j++){
	if(data[j].correct>data[j-1].correct) swap(data[j],data[j-1]);
      }
    }
    for(i=1;i<t;i++){
      cout << data[i].tnum;
      if(data[i].correct==data[i+1].correct&&data[i].time==data[i+1].time)
	cout << '=';
      else cout << ',';
    }
    cout << data[t].tnum;
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1192
import sys

def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    dist = [sys.maxsize] * (N + 1)

    dist[1] = 0
    for _ in range(N):
        for j in range(M):
            weight = -(C[j] - P)
            if dist[B[j]] > dist[A[j]] + weight:
                dist[B[j]] = dist[A[j]] + weight

    result = -dist[N]

    for _ in range(N + 1):
        for j in range(M):
            weight = -(C[j] - P)
            if dist[B[j]] > dist[A[j]] + weight:
                dist[B[j]] = dist[A[j]] + weight

    if result != -dist[N]:
        print(-1)
    else:
        print(max(-dist[N], 0))


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, P, A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 43996
<?php
  
list($b) = fscanf(STDIN, '%s');
switch ($b) {
    case 'T':
        echo 'A';
        break;
    case 'A':
        echo 'T';
        break;
    case 'G':
        echo 'C';
        break;
    case 'C':
        echo 'G';
        break;
    
    default:
        echo 'error';
        break;
}

Measured memory_bytes: 4728
#include <iostream>
#include <bitset>

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

  uint32_t N, M;
  std::cin >> N >> M;
  uint32_t SS[11];
  uint32_t S[11][11] = {{0}};

  for (uint32_t i = 0; i < M; i++) {
    uint32_t x;
    std::cin >> x;
    SS[i] = x;
    for (uint32_t j = 0; j < x; j++) {
      std::cin >> S[i][j];
      S[i][j]--;
    }
  }

  std::bitset<10> C(0);
  for (uint32_t i = 0; i < M; i++) {
    uint32_t s;
    std::cin >> s;
    if (s != 0) {
      C.set(i, true);
    }
  }

  uint32_t ret = 0;
  for (uint32_t bit = 0; bit < (1 << N); bit++) {
    uint8_t o[11] = {0};
    for (uint32_t i = 0; i < N; i++) {
      if (bit & (1 << i)) {
        o[i] = 1;
      }
    }

    bool found = true;
    for (uint32_t i = 0; i < M; i++) {
      uint32_t x = 0;
      for (uint32_t j = 0; j < SS[i]; j++) {
        if (o[S[i][j]]) {
          x++;
        }
      }

      if (C[i] && x % 2 == 0) {
        found = false;
      } else if (!C[i] && x % 2 != 0) {
        found = false;
      }
    }
    if (found) {
      ret++;
    }
  }

  std::cout << ret << std::endl;
}


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

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

    vector<pair<int, int>> x(n);
    vector<pair<int, int>> y(n);

    rep(i, n){
        cin  >> x[i].first >> x[i].second;
    }
    rep(i, n){
        cin  >> y[i].first >> y[i].second;
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    int count = 0;

    rep(i, n){
        int ma = -10000000;
        int max_id = -1;
        rep(j, n){
            if(y[i].first > x[j].first && y[i].second > x[j].second){
                if(ma < x[j].second){
                    max_id = j;
                    ma = x[j].second;
                }
            }
        }

        if(max_id != -1){
            count++;
            x[max_id] = {1000000000000, 100000000000};
        }
    }

    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
n = input()
l = len(n)
a = [0 for _ in range(2019)]
a[0] = 1
now = 0
ten = [1]
for i in range(l-1):
  ten.append(ten[-1]*10%2019)
ten.reverse()
for i in range(l)[::-1]:
  now += ten[i]*int(n[i])
  now %= 2019
  a[now] += 1
  #print(now)
ans = 0
for d in range(2019):
  ans += a[d] * (a[d]-1) // 2
print(ans)

Measured memory_bytes: 81208
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100001];
int s;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=n;i>n-k;i--)
	s+=a[i];
	cout<<s<<endl;
	return 0;
}


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

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

  if(n.at(0) == '9' || n.at(1) == '9')
    cout << "Yes";
  else
  {
    cout << "No";
  }
  
}


Measured memory_bytes: 3580
#include <iostream>
using namespace std;
int main (){
    string s;cin>>s;
    if(s=="SAT"){
    cout<<"1";}
    else if(s=="SUN"){
    cout<<"7";}
    else if(s=="MON"){
    cout<<"6";}
    else if(s=="TUE"){
    cout<<"5";}
    else if(s=="WED"){
    cout<<"4";}
    else if(s=="THU"){
    cout<<"3";}
    else if(s=="FRI"){
    cout<<"2";}
    }





















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

typedef long long ll;
typedef long double ld;

using namespace std;

const ll INF = 1e18;
const ll maxn = 620;
const ll mod = 1e9+7;

ll n , m , k;
ll dp[maxn][maxn], a[maxn], sum[maxn][maxn];

int main()
{
    cin>> n;
    for(ll i = 1; i <= n; i++) cin>>  a[i];

    for(ll t = 1; t <= n; t++)
        for(ll l = 1; l+t-1 <= n; l++)
        {
            ll r = l+t-1;
            if(t == 1){
                dp[l][r] = 0;
                sum[l][r] = a[l];
                continue;
            }

            sum[l][r] = sum[l][r-1] + a[r];

            dp[l][r] = INF;
            for(ll ii = l; ii < r; ii++)
                dp[l][r] = min(dp[l][r], dp[l][ii] + dp[ii+1][r] + sum[l][ii] + sum[ii+1][r]);
        }

    cout<< dp[1][n];
}










Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    //int main(){
    cout << fixed << setprecision(10);
    int a, b, d, r;
    double f;
    cin >> a >> b;
    d = a/b;
    r = a%b;
    f = (double)a/b;
    cout << d << " " << r << " " << f << endl;
}


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

int main()
{
 int N; cin >> N;
  int A[N]; rep(i,N) cin >> A[i];
  
  bool check = false;
  int count = 0;
  //奇数カウンター
  rep(i,N)
  {
    if(A[i] % 2 == 1) count++;
  }
  rep(i,N)
  {
    if(A[i] % 2 == 1 && count % 2 == 0)
    {
      check = true;
    }
  }
  
  if(check) cout << "YES" << endl;
  else cout << "NO" << endl;
}
    

Measured memory_bytes: 640
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ZYCSwing
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int h = in.nextInt(), w = in.nextInt();

            int[][] cost = new int[10][10];

            for (int i = 0; i < 10; ++i) {
                for (int j = 0; j < 10; ++j) {
                    cost[i][j] = in.nextInt();
                }
            }

            Set<Integer> s = new HashSet<>();
            for (int i = 0; i < 10; ++i) s.add(i);
            int[] dist = new int[10];
            Arrays.fill(dist, Integer.MAX_VALUE);
            dist[1] = 0;

            for (int i = 0; i < 10; ++i) {
                int min = Integer.MAX_VALUE;
                int ind = -1;
                for (int j : s) {
                    if (dist[j] < min) {
                        min = dist[j];
                        ind = j;
                    }
                }

                s.remove(ind);
                for (int j : s) {
                    if (dist[j] > dist[ind] + cost[j][ind]) {
                        dist[j] = dist[ind] + cost[j][ind];
                    }
                }
            }

            int res = 0;
            int num;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    num = in.nextInt();
                    if (num == -1) continue;
                    res += dist[num];
                }
            }

            out.println(res);
        }

    }
}



Measured memory_bytes: 44700
import java.util.Scanner;
public class Main {
  int count = 0;
  public static void main(String[] args) {
    new Main().run();
  }
  void run() {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    for(int i = 0; i < 3; i++) {
      char c = s.charAt(i);
      if(c == '1') count++;
    }
    System.out.println(count);
  }
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

int main(){
	int N;
	cin >> N;
	vector<ll> a(N);
	REP(i, N) cin >> a[i];
	vector<pii> res;

	int tmp=0;
	int tmp_i = 0;
	REP(i, N){
		if(abs(a[i])>abs(tmp)){
			tmp = a[i];
			tmp_i = i;
		}
	}
	REP(i, N){
		res.push_back(make_pair(tmp_i, i));
	}
	if(tmp>=0){
		REP(i, N-1){
			res.push_back(make_pair(i, i+1));
		}
	}else{
		REP(i, N-1){
			res.push_back(make_pair(N-1-i, N-2-i));
		}
	}
	cout << res.size() << endl;
	REP(i, res.size()) cout << res[i].first+1 << " " << res[i].second+1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

map<ll, ll> prime_factor(ll n){
	map<ll, ll> res;
	for(ll i = 2; i*i <= n; i++){
		while(n%i == 0){
			res[i]++;
			n /= i;
		}
	}
	if(n != 1) res[n] = 1;
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    int ans = 0;
    for(auto p : prime_factor(n)){
        int cnt = 1;
        ll x = p.first;
        while(n%x == 0){
            n /= x;
            x *= p.first;
            ++ans;
        }
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
n, m, c = map(int, input().split())
B = list(map(int, input().split()))
ans = 0
for _ in range(n):
    A = list(map(int, input().split()))
    temp = 0
    for a, b in zip(A, B):
        temp += a*b
    if temp + c > 0:
        ans += 1
print(ans)

Measured memory_bytes: 3060
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    int mn = INT_MAX;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(i == 1){
            mn = x;
            ans++;
        }else{
            mn = min(mn, x);
            if(mn >= x){
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 384
n,m = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
s,t = map(int, input().split())

from collections import deque
Q = deque()
Q.append([s-1,0,0])
visited = [[] for _ in range(n)]
visited[s-1]=[0]

while Q:
    now,kkp,cnt = Q.popleft()
    nxt_kkp = (kkp+1)%3
    for nxt in link[now]:
        if nxt == (t-1) and nxt_kkp == 0:
            print((cnt+1)//3)
            exit()
        if nxt_kkp in visited[nxt]:
            continue
        visited[nxt].append(nxt_kkp)
        Q.append([nxt,nxt_kkp,cnt+1])

print(-1)

Measured memory_bytes: 70816
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<vector<int> > Graph;
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; }

int main(){
    int n;
    cin >> n;
    vector<ll>a(n);
    vector<ll>b(n);
    rep(i,n){
        cin >> a[i];
        b[i]=a[i]-i-1;
    }
    int m=n/2;
    sort(b.begin(),b.end());
    int x = b[m];
    ll ans = 0;
    rep(i,n){
        ans+=abs(b[i]-x);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
package main

import "fmt"

var S, T [100000]int
var n, q int

func main() {
	var m int
	fmt.Scan(&n)
	for i := 0; i < n; i++ {
		fmt.Scan(&S[i])
	}
	fmt.Scan(&q)
	for i := 0; i < q; i++ {
		fmt.Scan(&m)
		if solve(0, m) == true {
			fmt.Println("yes")
		} else {
			fmt.Println("no")
		}
	}
}
func solve(i, m int) bool {
	if m == 0 {
		return true
	}
	if i >= n {
		return false
	}
	if solve(i+1, m) == true {
		res := solve(i+1, m)
		return res
	} else if solve(i+1, m-S[i]) == true {
		res := solve(i+1, m-S[i])
		return res
	}
	return false
}



Measured memory_bytes: 1148
#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;
typedef pair<string, int> psi;

int n, v;
map<string, int> m;
string s;

int main(){
    cin >> n;
    for (int i = 0; i < n; ++i){
        cin >> s;
        if (m.find(s) == m.end()) m.emplace(s, 1);
        else m[s]++;
    }
    v = 0;
    for (auto iter=m.begin(); iter != m.end(); ++iter){
        if (v < iter->second) v = iter->second;
    }
    for (auto iter=m.begin(); iter != m.end(); ++iter){
        if (iter->second == v) cout << iter->first << endl;
    }
}

Measured memory_bytes: 25216
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>

using namespace std;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define INF 11111111111111111
#define MOD 1000000007
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;

ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, temp = 0;
string s;
bool flag;

//-------------------------------------------------------------------------------

#define MAX 10000

int main(void) {
  ll a, b;

  cin >> n >> a >> b;

  ans = max(0LL, (n - 2)*(b - a) + 1);

  cout << ans << endl;

  return 0;
}

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

#define MAX 2000

int main(){
  int n, i, j, A[20], B[MAX+1], x;

  memset(B,0,sizeof(B));

  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,A + i);
  }

  B[0] = 1;
  for(i = 0 ; i < n ; i++){
    for(j = MAX ; j >= 0 ; j--){
      if(B[j] && j + A[i] <= MAX){
        B[j + A[i]] = 1;
      }
    }
  }
  
  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,&x);
    if(B[x]){
      printf("yes\n");
    }else{
      printf("no\n");
    }
  }

  return 0;
}



Measured memory_bytes: 2120
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb(x) (x&-(x))
const int N = 101010;

int main(){

	char a,b;
	cin>>a>>b;
	if(a>b)
	cout<<">"<<endl;
	else if(a<b)
	cout<<"<"<<endl;
	else 
	cout<<"="<<endl; 



    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

static class ACCount400AndRPS70000Congrats
{
  static void Main()
  {
    int rating = int.Parse(Console.ReadLine());
    if (rating < 1200) Console.WriteLine("ABC");
    else if (rating < 2800) Console.WriteLine("ARC");
    else Console.WriteLine("AGC");
  }
}

Measured memory_bytes: 27384
using System;

namespace Project
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			string s = Console.ReadLine();
			string[] sar = s.Split(' ');
			int a = int.Parse(sar[0]);
			int b = int.Parse(sar[1]);
			int d = a / b;
			int r = a % b;
			double f = (double)a / (double)b;
			Console.WriteLine("{0} {1} {2}", d, r, f.ToString("F8"));

		}
	}
}

Measured memory_bytes: 9212
#include<cstdio>
#include<algorithm>
int N;
struct item{int i,x;bool operator<(item&it){return x<it.x;}}a[400010];
int cnt[200010],c2;
void cmin(long long&a,long long b){b<a?a=b:1;}
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d%d",&a[i*2].x,&a[i*2+1].x);
		a[i*2].i=a[i*2+1].i=i;
	}
	std::sort(a,a+N*2);
	for(int i=0;i<N;i++)cnt[i]=2;
	c2=N;
	long long ans=1ll<<62;
	for(int i=0,j=0;i<N*2;i++){
		while(c2&&j<N*2)--cnt[a[j++].i]==1?--c2:1;
		if(!c2)cmin(ans,1ll*(a[N*2-1].x-a[0].x)*(a[j-1].x-a[i].x));
		if(++cnt[a[i].i]==2)++c2;
	}
	int l=0,r=N*2;
	for(int i=0;i<N;i++)cnt[i]=0;
	while(++cnt[a[l].i]<2)l++;
	for(int i=0;i<N;i++)cnt[i]=0;
	while(++cnt[a[r-1].i]<2)r--;
	cmin(ans,1ll*(a[r-1].x-a[0].x)*(a[N*2-1].x-a[l].x));
	printf("%lld\n",ans);
}

Measured memory_bytes: 4096
#include<iostream>
using namespace std;
int c=0;
void merge(int A[], int left, int mid, int right){
	int n1=mid-left;
	int n2=right-mid;
	int L[n1+1];
	int R[n2+1];
	for(int i=0; i<n1; i++)
		L[i]=A[left+i];
	for(int i=0; i<n2; i++)
		R[i]=A[mid+i];
	L[n1]=1000000000;
	R[n2]=1000000000;
	int i=0, j=0;
	for(int k=left; k<right; k++){
		c++;
		if(L[i]<=R[j]){
			A[k]=L[i];
			i++;
		}
		else{
			A[k]=R[j];
			j++;
		}
	}
}
void mergeSort(int A[], int left, int right){
	if(left+1<right){
		int mid=(left+right)/2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}
int main(){
	int n;
	cin>>n;
	int A[n];
	for(int i=0; i<n; i++)
		cin>>A[i];
	mergeSort(A, 0, n);
	for(int i=0; i<n-1; i++)
		cout<<A[i]<<" ";
	cout<<A[n-1]<<endl<<c<<endl;
	return 0;
}


Measured memory_bytes: 6888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int i, j;
    int n;
    cin >> n;
    ll g = 0;
    ll a[n];
    set<ll> s;
    bool f = 1;
    for (i = 0; i < n; i++) {
        cin >> a[i];
        g = gcd(g, a[i]);
        for (j = 2; j * j <= a[i]; j++) {
            if (a[i] % j == 0) {
                if (s.count(j)) f = 0;
                s.insert(j);
                while (a[i] % j == 0) a[i] /= j;
            }
        }
        if (a[i] > 1) {
            if (s.count(a[i])) f = 0;
            s.insert(a[i]);
        }
    }
    if (f)
        cout << "pairwise coprime" << endl;
    else if (g == 1)
        cout << "setwise coprime" << endl;
    else
        cout << "not coprime" << endl;
}

Measured memory_bytes: 15056
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define BOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
typedef long long ll;


int main(){

    int N;
    cin>>N;
    vector<int> a(N);
    REP(i,N)cin>>a[i];
    
    ll ans=0;
    REP(i,N){
        if(i==0||i==N-1){
            ans+=a[i]/2;
            a[i]=a[i]%2;
        }else{
            ans+=min(a[i-1],a[i]);
            a[i]-=min(a[i-1],a[i]);
            ans+=a[i]/2;
            a[i]=a[i]%2;
            ans+=min(a[i],a[i+1]);
            int t=min(a[i],a[i+1]);
            a[i]-=t;
            a[i+1]-=t;
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    int h, w, k, s = 1, f = 0;;
    cin >> h >> w >> k;
    vector<vector<char>> a(h, vector<char>(w));
    vector<vector<int>> b(h, vector<int>(w, 0));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            if (a[i][j] == '#') {
                b[i][j] = s;
                s += 1;
                f += 1;
            }
        }
    }

    while (true) {
        int f_b = f;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (b[i][j] == 0) continue;
                if (j > 0 && b[i][j - 1] == 0) {
                    b[i][j - 1] = b[i][j];
                    f += 1;
                }
                if (j < w - 1 && b[i][j + 1] == 0) {
                    b[i][j + 1] = b[i][j];
                    f += 1;
                }
            }
        }
        if (f_b == f) break;
    }

    while (true) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (b[i][j] != 0) continue;
                if (i > 0 && b[i - 1][j]) {
                    b[i][j] = b[i - 1][j];
                    f += 1;
                }else if (i < h - 1 && b[i + 1][j]) {
                    b[i][j] = b[i + 1][j];
                    f += 1;
                }
            }
        }
        if (f == h * w) break;
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) cout << b[i][j] << " ";
        cout << endl;
    }
}


Measured memory_bytes: 1280
N = int(input())


inin = []
for i in range(N):
    inin.append(str(input()))
    
dic = {}
for i in inin:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] = dic[i]+1

l = dic.items()
max = 0
for i in l:
    if i[1] > max:
        max = i[1]

result = []
for i in l:
    if i[1] == max:
        result.append(i[0])

result.sort()

for i in result:
    print(i)

Measured memory_bytes: 35208
N = int(input())
S = []

dic = {}
mx = 0

for i in range(N):
  s = input()
  if s in dic:
    dic[s] = dic[s] + 1
  else:
    dic[s] = 1
  
  if mx < dic[s]:
    mx = dic[s]


for s in sorted({k for k,v in dic.items() if v==mx}):
  print(s)


Measured memory_bytes: 42332
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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


	int A, B, C, D, M;
	string S, T,N;
	cin >> S >> T >> A >> B >> N;
	if (N == S)A--;
	else B--;
	cout << A << " " << B << endl;


	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
Scanner sc  = new Scanner(System.in);
for(int i=1;;i++) {
	int x= sc.nextInt();
	if(x==0) break;
	System.out.printf("Case %d: %d\n",i,x);
}
sc.close();
	}
	
}


Measured memory_bytes: 64816
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>

using namespace std;
using ll = long long int;

int main(){
    ll N, A, B;
    cin >> N >> A >> B;
    auto X = A * N;
    if(X < B) cout << X << endl;
    else cout << B << endl;
}


Measured memory_bytes: 256
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
N,K = map(int,input().split())

if(K%2==0):
    cnt1=0
    cnt2=0
    for a in range(1,N+1):
        if(a%K==0):
            cnt1+=1
        elif(a%K==K/2):
            cnt2+=1

    print(cnt1**3+cnt2**3)

else:
    cnt=0
    for a in range(1,N+1):
        if(a%K==0):
            cnt+=1
    print(cnt**3)




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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int N,W,w,v,dp[100][100001],ans;

main() {
    cin >> N >> W >> w >> v;
    dp[0][w] = v;
    rep1(i,N-1) {
        cin >> w >> v;
        rep(j,W+1) {
            if (j<w) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v);
        }
    }
    rep1(i,W) ans = max(ans,dp[N-1][i]);
    ct(ans)
}


Measured memory_bytes: 77568
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt();
		Integer l[] = new Integer[N];
		for (int i = 0; i < N; i++) {
			l[i] = sc.nextInt();
		}
		Arrays.sort(l, Collections.reverseOrder());
		int ans = 0;
		for (int i = 0; i < K; i++) {
			ans += l[i];
		}
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 22996
#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 fore(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; --i)
#define ford1(i, n) for(int i = (int)(n); i>=1; --i)
#define fored(i, a, b) for(int i = (int)(b); i >= (int)(a); --i)
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define clr(v) memset(v, 0, sizeof(v))
#define clr1(v) memset(v, 0xFF, sizeof(v))
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long i64;
typedef unsigned long long u64;
typedef long double ld;
typedef vector<ld> vld;

typedef vector<i64> vi64;

template<class T> bool uax(T&a, const T& b) { if( a < b ) { a = b; return true; } return false; }
template<class T> bool uin(T&a, const T& b) { if( a > b ) { a = b; return true; } return false; }

void solve() {
  int x,y,z;
  cin >>x>>y>>z;
  vvi v(x+y+z,vi(3, 0));
  forn(i, v.size()) forn(j, 3) cin >> v[i][j];
  vpi u(x+y+z);
  i64 s_base = 0;
  forn(i, u.size()) {
    s_base += v[i][0];
    u[i] = mp(v[i][1] - v[i][0], v[i][2] - v[i][0]);
  }
  sort(rall(u));
  multiset<int> ML, MZ1, MZ2, MR;
  i64 sl = 0, sz1 = 0, sz2 = 0;
  // [0 .. i) -> y + z'
  // [i .. sz) -> z''
  forn(i, x+y+z) if(i < y) {
    sl += u[i].fi;
    ML.insert(u[i].se-u[i].fi);
  } else {
    MR.insert(u[i].se);
  }
  while(MZ2.size() < z) {
    auto it = MR.end(); --it;
    sz2 += *it;
    MZ2.insert(*it); MR.erase(it);
  }
  // cerr << s_base << '\n';
  // forn(i, u.size()) cerr << u[i].fi << ' ' << u[i].se << '\n';

  i64 ans = sl + sz1 + sz2;
  // cerr << sl << ' ' << sz1 << ' ' << sz2 << '\n';
  forn(j, z) {
    auto e = u[y + j];
    // remove
    {
      auto it = MR.find(e.se);
      if (it == MR.end()) {
        sz2 -= e.se;
        MZ2.erase(MZ2.find(e.se));
      } else {
        MR.erase(MR.find(e.se));
        auto it = MZ2.begin();
        sz2 -= *it;
        MR.insert(*it);
        MZ2.erase(it);
      }
    }
    // insert
    sl += e.fi;
    ML.insert(e.se - e.fi);
    {
      auto it = ML.end(); --it;
      sz1 += *it;
      MZ1.insert(*it); //debug only
      ML.erase(it);
    }

    // cerr << sl << ' ' << sz1 << ' ' << sz2 << '\n';
    uax(ans, sl + sz1 + sz2);
  }
  cout << s_base + ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed; cout.precision(15);
  cerr << fixed; cerr.precision(15);
#ifdef HOME
  freopen("input.txt", "r", stdin);
#endif
  solve();
  return 0;
}


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

int cost[100010][3];
long long happy[100010][3];

long long dp(int day, int prev) {
    if (day < 0) {
        return 0;
    }
    if (prev >= 0 && happy[day][prev] != 0) {
        return happy[day][prev];
    }
    if (prev == 0) {
        happy[day][prev] = max(dp(day - 1, 1) + cost[day][1],
                         dp(day - 1, 2) + cost[day][2]);
    } else if (prev == 1) {
        happy[day][prev] = max(dp(day - 1, 0) + cost[day][0],
                         dp(day - 1, 2) + cost[day][2]);
    } else if (prev == 2) {
        happy[day][prev] = max(dp(day - 1, 0) + cost[day][0],
                         dp(day - 1, 1) + cost[day][1]);
    } else {
        return max({dp(day - 1, 0) + cost[day][0],
                    dp(day - 1, 1) + cost[day][1],
                    dp(day - 1, 2) + cost[day][2]});
    }
    // cout << day << " day : " << happy[day][prev] << endl;
    return happy[day][prev];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x,y,z;
        cin >> x >> y >> z;
        cost[i][0] = x;
        cost[i][1] = y;
        cost[i][2] = z;
    }
    cout << dp(n-1, -1) << endl;
}


Measured memory_bytes: 9984
//DFSテンプレート
fun main(args: Array<String>) {
    var (N, K) = listOfInt()
    var (R, S, P) = listOfInt()
    var T = next()
    var G = Array<Char>(N) { ' ' }
    fun g(n: Int): Char {
        return if (n - K >= 0) G[n - K] else ' '
    }
    var ans = 0
    for (n in 0 until N) {
        G[n] = ' '
        when (T[n]) {
            'r' -> {
                if(g(n) != 'p') {
                    ans += P
                    G[n] = 'p'
                }
            }
            's' -> {
                if(g(n) != 'r') {
                    ans += R
                    G[n] = 'r'
                }
            }
            'p' -> {
                if(g(n) != 's') {
                    ans += S
                    G[n] = 's'
                }
            }
        }
    }
    println(ans)
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }

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

int main() {
    ll N;
    string c;
    cin >> N;
    cin >> c;
    ll red = 0;
    ll ans = 0;

    for(ll i = 0; i <= N; i++){
        if(c[i] == 'R'){
            red += 1;
        }
    }

    for(ll i=0; i < red; i++){
        if(c[i] == 'W'){
            ans += 1;
        }
    }

    cout << ans << endl;

    return 0;
}

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

constexpr int max_h = 300, max_w = 300, none_value = -1, inf = 1e9;

int h, w, grid[max_h + 1][max_w + 1];

int solve(const int v)
{
    int dp[max_h + 1][max_h + 1];
    int cost[max_h + 1][max_h + 1];

    for (int i = 0; i <= h; ++i)
        for (int j = 0; j <= h; ++j)
            dp[i][j] = cost[i][j] = none_value;

    for (int dif = -h; dif <= h; ++dif)
        for (int i = max(0, -dif); i + dif <= h and i <= h; ++i)
        {
            if (min(i, i + dif) == 0)
                cost[i][i + dif] = 0;
            else
            {
                assert(cost[i - 1][i + dif - 1] != none_value);
                int precalc = cost[i - 1][i + dif - 1];
                int new_pair = (grid[h - i + 1][v] == grid[h - (i + dif) + 1][v + 1]);
                cost[i][i + dif] = precalc + new_pair;
            }
        }

    for (int i = 0; i <= h; ++i)
        for (int j = 0; j <= h; ++j)
        {
            dp[i][j] = inf;
            if (i == 0 and j == 0)
                dp[i][j] = 0;
            if (i > 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + cost[i][j]);
            if (j > 0)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + cost[i][j]);
        }

    return dp[h][h];
}

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

    cin >> h >> w;

    for (int i = h; i >= 1; --i)
    {
        string s; cin >> s;
        for (int j = 1; j <= w; ++j)
            grid[i][j] = (s[j - 1] - 'a');
    }

    int res = 0;
    for (int j = 1; j + 1 <= w; ++j)
        res += solve(j);

    cout << res << '\n';
}


Measured memory_bytes: 4648
//?????¢??¢?´¢
#include <stdio.h>

int Linear(int A[],int n,int key){
    int i=0;
    A[n]=key;
    while(A[i] != key) i++;
    return i != n;
}

int main(void){
    int i=0,n,A[10001],key;
    int q,sum=0;
    scanf("%d",&n);

    for(i=0;i<n;i++) scanf("%d",&A[i]);
    scanf("%d",&q);

    for(i=0;i<q;i++){
        scanf("%d",&key);
        if(Linear(A, n, key)) sum++;
    }
    printf("%d\n",sum);
}

Measured memory_bytes: 1888
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int x, y;
        cin >> x >> y;
        if(x == 0)
            return 0;
        if(x < y)
            swap(x, y);

        int ret = 0;
        do{
            ++ ret;
            x %= y;
            swap(x, y);
        }while(y != 0);

        cout << x << ' ' << ret << endl;
    }
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;


int main() {
	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e;
	cin >> k;
	if (e - a > k) {
		cout << ":(";
	}
	else {
		cout << "Yay!";
	}
}

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

int main(){
  string s;
  cin>>s;
  string t=s;
  reverse(t.begin(),t.end());
  rep(i,t.size()){
    if(s[i]=='b')s[i]='d';
    else if(s[i]=='d')s[i]='b';
    else if(s[i]=='p')s[i]='q';
    else if(s[i]=='q')s[i]='p';
  }
  cout<<(s==t?"Yes":"No")<<endl;
}

Measured memory_bytes: 3808
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        String op = sc.next();
        int b = sc.nextInt();
        while(op.equals("?") == false){
            System.out.println(Calculate(a,op,b));
            a = sc.nextInt();
            op = sc.next();
            b = sc.nextInt();
        }
        sc.close();
    }

    public static int Calculate(int a, String op, int b){
        int result = 0;
        switch(op){
            case "+":
                result = a + b;
                break;
            case "-":
                result = a - b;
                break;
            case "/":
                result = a / b;
                break;
            case "*":
                result = a * b;
                break;
        } 
        return result;   
    }
}


Measured memory_bytes: 26420