akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

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

  CIN(N);
  int two, four, other;
  two = four = other = 0;
  REP(i, N) {
    CIN(a);
    if (a % 4 == 0)      four++;
    else if (a % 2 == 0) two++;
    else                 other++;
  }

  bool ok = false;
  if (two == 0) {
    if (four + 1 >= other) ok = true;
    else                   ok = false;
  } else {
    if (four >= other)     ok = true;
    else                   ok = false;
  }

  OK(ok);

  return 0;
}



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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        char[] n=reader.readLine().toCharArray();
        if (n[0]=='7' || n[1]=='7' || n[2]=='7')
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 32776
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin >> n;
  int b[n - 1];
  REP(i, n - 1)
  {
    cin >> b[i];
  }
  if (n == 2)
  {
    cout << b[0] * 2 << endl;
    return 0;
  }
  ll ans = b[0];
  for (int i = 0; i < n - 2; i++)
  {
    ans += min(b[i], b[i + 1]);
  }
  ans += b[n - 2];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
  int BA,BB;
  cin>> BA >> BB;
  int Bbest;
  Bbest = min(BA,BB);
  int TA,TB;
  cin >> TA >> TB;
  int Tbest;
  Tbest = min(TA,TB);
  cout << Bbest+Tbest << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll a, b, c, k, ans = 0;
  scanf("%lld%lld%lld%lld", &a, &b, &c, &k);
  if(a > k) ans = k, k = 0;
  else ans = a, k -= a;
  if(b > k) k = 0;
  else k -= b;
  ans -= k;
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 1736
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	int n, m, h, k;
	boolean[][] map;
	int score[];
	void run() {
		Scanner sc = new Scanner(System.in);

		for(;;) {
			n = sc.nextInt();
			m = sc.nextInt();
			h = sc.nextInt();
			k = sc.nextInt();
			if( (n|m|h|k) == 0 ) break;
			map = new boolean[n+1][h];
			score = new int[n];
			for(int i=0;i<n;i++) score[i] = sc.nextInt();
			for(int i=0;i<m;i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				map[a][b-1] = true;
			}
			int ret[] = new int[n];
			for(int i=0;i<n;i++) ret[i] = i+1;
			HashSet<Pair> rev = new HashSet<Pair>();
			for(int j=0;j<h;j++) for(int i=1;i<n;i++) {
				if(map[i][j]) {
					rev.add(new Pair(ret[i-1], ret[i]));
					swap(ret, i-1, i);
				}
			}
//			debug(ret);
//			for(Pair p: rev) debug(p.f, p.s);
			int min = 0;
			HashMap<Integer, Integer> link = new HashMap<Integer, Integer>();
			for(int i=0;i<n;i++) link.put(ret[i]-1, i);
			for(int i=0;i<k;i++) min += score[link.get(i)];
//			debug(min);
			int val = min;
			for(Pair p: rev) {
				if( ( p.f <= k && p.s <= k ) || ( k < p.f && k < p.s ) )
					continue;
//				debug(score[link.get(p.f-1)], score[link.get(p.s-1)], (p.f <= k)? -1:1 );
				min = min(min, val + ( score[link.get(p.f-1)]-score[link.get(p.s-1)] ) * ( (p.f <= k)? -1:1 ) );
			}
			System.out.println(min);
		}

	}
	void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	class Pair {
		int f, s;
		Pair (int f, int s) {
			this.f = f;
			this.s = s;
		}

		@Override
		public boolean equals(Object o) {
			if(o instanceof Pair) {
				Pair p = (Pair) o;
				return p.f == f && p.s == s;
			}
			return false;
		}
	}

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

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 21000
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 10000000000000000
#define mod 2019

ll mypow(ll a,ll b){
	ll num=1;
	while(b>0){
		num*=a;
		b--;
	}
	return num;
}

int main(){
	ll n,k,i;cin>>n>>k;//n:サイコロの目のmax　k:とりたい得点
	vector<ll> ans;

	ll MAX=-1;
	for(i=1;i<=n;i++){//i:サイコロの目
		ll num=0,ins=k;
		
		ins/=i;
		while(ins>0){
			ins/=2;
			num++;
		}

		for(ll j=0;j<=32;j++){
			if(k%i==0 && k/i==mypow(2,j)){
				num--;
				break;
			}
		}

		ans.push_back(mypow(2,num));
		MAX=max(MAX,mypow(2,num));//分母
	}

	
	ll sum=0;
	for(i=0;i<ans.size();i++){//分子
		sum+=MAX/ans[i];
	}

	double answer=(sum+.0)/(MAX*n+.0);//通分して計算

	printf("%.12f\n",answer);
	return 0;
}

Measured memory_bytes: 1400
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	struct Point
	{
		public int X, Y;
		public Point(int x, int y) { X = x; Y = y; }
		public T At<T>(T[,] a) => a[X, Y];
		public bool In(int x, int y) => 0 <= X && X < x && 0 <= Y && Y < y;
		public Point Add(Point d) => new Point(X + d.X, Y + d.Y);
		public void Add(int[,] a, int v) { a[X, Y] += v; }
		public static IEnumerable<Query> GetPoints(int X, int Y)
		{
			var d = new Point(0, 1);
			var n = new Point(1, 0);
			for (var p = new Point(0, 0); p.In(X, Y);)
			{
				for (var q = p.Add(d); q.In(X, Y); p = q, q = q.Add(d)) yield return new Query(p, q);
				if (p.X < X - 1) yield return new Query(p, p.Add(n));
				p = p.Add(n);
				d.Y *= -1;
			}
		}
	}
	struct Query
	{
		public readonly Point From, To;
		public Query(Point f, Point t) { From = f; To = t; }
		public override string ToString() => $"{From.Y + 1} {From.X + 1} {To.Y + 1} {To.X + 1}";
	}
	int[] G => ReadLine().Split().Select(int.Parse).ToArray();
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int X, Y;
	int[,] map;
	readonly List<Query> qs = new List<Query>();
	void Solve()
	{
		var I = G;
		Y = I[0]; X = I[1];
		map = new int[X, Y];
		for (var y = 0; y < Y; y++)
		{
			I = G;
			for (var x = 0; x < X; x++) map[x, y] = I[x];
		}
		foreach (var q in Point.GetPoints(X, Y))
			if (q.From.At(map) % 2 == 1)
			{
				q.From.Add(map, -1);
				q.To.Add(map, 1);
				qs.Add(q);
			}
		WriteLine(qs.Count);
		foreach (var mv in qs) WriteLine(mv);
	}
}


Measured memory_bytes: 26116
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for _ in range(n)]

while k!=0:
    B=[0 for _ in range(n+1)]
    for i,j in enumerate(A):
        B[max(0,i-j)] +=1
        B[min(n,i+j+1)] -=1
    for i in range(1,n):
        B[i] +=B[i-1]
    A=B[:n]
    k -=1
    if A==C:break
print(*A)

Measured memory_bytes: 219016
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define vint vector<int>
#define pint pair<int, int>
#define pb(a) push_back(a)
#define all(v) v.begin(), v.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl

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

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

	int X, Y;
	cin >> X >> Y;

	int ans = 0;

	if (X <= 3) {
		ans += (4 - X) * 100000;
	}

	if (Y <= 3) {
		ans += (4 - Y) * 100000;
	}

	if (X == 1 && Y == 1) {
		ans += 400000;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n=int(input())
s=input()
l=[[] for _ in range(3)]
for i in range(n):
    if s[i]=='R':
        l[0].append(i)
    elif s[i]=='G':
        l[1].append(i)
    else:
        l[2].append(i)
ans=len(l[0])*len(l[1])*len(l[2])
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<n:
            if s[i]!=s[j] and s[j]!=s[2*j-i] and s[i]!=s[2*j-i]:
                ans-=1
print(ans)

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string ret,s;
	for (int i=0; i<3; i++)
		cin>>s, ret+=toupper(s.front());
	cout<<ret<<endl;
	return 0;
}


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

#define rep(i, n) for(int i = 0; i < n; i++)

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int N, M; cin >> N >> M;
    int cnt_wa[N+1] = {};
    set<int> ac;
    rep(i, M){
        int p; string res;
        cin >> p >> res;
        if(res == "AC"){
            ac.insert(p);
        }
        else{
            if(!ac.count(p)) cnt_wa[p]++;
        }
    }
    int num_wa = 0;
    for(int i = 1; i <= N; i++){
        if(ac.count(i)){
            num_wa += cnt_wa[i];
        }
    }
    cout << ac.size() << " " << num_wa << endl;
    return 0;
}

Measured memory_bytes: 5376
#include<iostream>
#include<cmath>
#include<iomanip>

using namespace std;

int main(){
        int N;
        cin >> N;
        int x[10];
        int y[10];
        for(int i=0;i<N;i++) cin >> x[i] >>y[i];
        double sum_distance =0.0f;
        for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                        if(i==j)continue;
                         double deltax = x[j]-x[i];
                         double deltay = y[j]-y[i];
                         sum_distance += sqrt(deltax*deltax+deltay*deltay);
                }
        }
        double result = sum_distance / (double)N;
        cout << fixed <<result;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
typedef pair< int, int > ii;
typedef vector< ii > vii;

vector< int > G[100005];
int d, flag = 0;
int vis[100005];

void dfs(int node, int dis = 0){
	if(node == 2){
		flag = 1;
		d = dis;
	}
	vis[node] = 1;
	for(int i : G[node]) if(!vis[i]) dfs(i, dis + 1);
}

void solve(){
	int n; cin>>n;
	for(int i = 1; i<=n; i++){
		int a; cin>>a;
		G[i].push_back(a);
	}
	dfs(1, 0);
	if(flag){
		cout<<d<<endl;
	}else{
		cout<<-1<<endl;
	}
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;// cin>>t;
	while(t--){
		solve();
	}
	return 0;
}



Measured memory_bytes: 14140
n=int(input())
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)

import collections
A=collections.Counter(prime_factorize(n-1))
ans=1
cnt=0
for a,b in A.items():
    ans*=(b+1)

import math
li=[]
for i in range(2,math.floor(n**0.5)+1):
    if n%i==0:
        li.append(i)
        if i!=n//i:
            li.append(n//i)
li.append(n)
for i in li:
    x = n
    while x % i == 0:
        x //= i
    if x % i == 1:
        cnt += 1
print(ans - 1 + cnt)

        

Measured memory_bytes: 3564
#include<stdio.h>
#include<string.h>
int main()
{
        int k;
        char s[101];
        scanf("%d",&k);
        scanf("%s",s);
        int store=strlen(s);
        if(store<=k)
                printf("%s\n",s);
        else
        {
                char str[105];
                int i;
                for(i=0;i<k;i++)
                {
                        str[i]=s[i];
                }
                int j=0;
                while(j<3)
                {
                        str[i]='.';
                        i++;j++;
                }
                printf("%s\n",str);
        }
}

Measured memory_bytes: 1648
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i < b; i++)
typedef long long ll;
using namespace std;

int main(){
  string s;
  cin >> s;
  int count = 0;
  rep(i, s.size() / 2){
    if(s[i] != s[s.size() - 1 - i]){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cctype>
#include <numeric>
using namespace std;

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int R, C, B[12][10002];

void main2() {
  int ans = 0;
  for (int v = 0; v < (1<<R); ++v) {
    int cnt = 0;
    for (int x = 0; x < C; ++x) {
      int up = 0;
      for (int y = 0; y < R; ++y) {
        bool is_rev = v >> y & 1;
        if ((is_rev && !B[y][x]) || (!is_rev && B[y][x])) ++up;
      }
      cnt += max(up, R - up);
    }
    ans = max(ans, cnt);
  }
  printf("%d\n", ans);
}

int main() {
  while (scanf("%d%d", &R, &C), R | C) {
    rep(i,R) rep(j,C) scanf("%d", B[i]+j);
    main2();
  }
  return 0;
}

Measured memory_bytes: 1272
import java.util.*;
import java.io.*;

class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int x=sc.nextInt();
    int[] l=new int[n];
    for(int i=0;i<n;i++)
      l[i]=sc.nextInt();
    int point=0,cnt=1;
    
    for(int i=0;i<n;i++){
      point+=l[i];
      if(point<=x)
      	cnt++;
      else
        break;
    }
    System.out.println(cnt);
  }
}


Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define repa(X,A,Y) for (int (X) = A;(X) <= (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;

const int MAX_N = 100000;
int N;
int A[MAX_N];

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

  cin >> N;
  rep(i, N) cin >> A[i];

  int ans = 0;
  int state = 0;
  for (int i = 1; i < N; ++i) {
    if (state == 0) {
      if (A[i]-A[i-1] < 0) state = -1;
      if (A[i]-A[i-1] > 0) state = 1;
    } else {
      if ((A[i]-A[i-1])*state < 0) {
        ++ans; state = 0;
      }
    }
  }
  ++ans;

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


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,x); REP(i,sizeof(a)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}

int main(){
  while(1){
    string s; cin>>s;
    if(s=="-"){ break; }
    int N = s.size();
    int M; cin>>M;
    int num = 0;
    REP(count,M){
        int h; cin>>h;
        num += h;
    }
    num %= N;
    cout << s.substr(num,N-num) << s.substr(0,num) << "\n";
  }
}


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

#include <algorithm>

using namespace std;

#define sqr(x) ((x) * (x))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef long long ll;

const int MOD = 1000000007;
const int INF = 1000000007;
const ll INFLL = 1000000000000000007LL;

void solve() {
  string S;
  cin >> S;
  vector<int> cnt(3, 0);
  for (int i = 0; i < S.size(); i++) {
    if (S[i] == 'a') cnt[0]++;
    if (S[i] == 'b') cnt[1]++;
    if (S[i] == 'c') cnt[2]++;
  }
  sort(all(cnt));
  string ans = "YES";
  if (cnt[2] - cnt[0] > 1) ans = "NO";
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // cout << fixed << setprecision(12);

  solve();

  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef vector<int> vec;
bool isp(int n){
  if(n==1) return false;
  for(int i=2;i<=int(sqrt(n));i++){
    if(n%i==0)return false;
  }
  return true;
}

int factp(int n,int p){
  int ans=0;
  int memo=p;
  if(p==1)return 0;
  while(n/p>=1){
    ans+=n/p;
    p=p*memo;
  }
  return ans;
}

int main(){
  long n,mod=1000000007,ans=1;
  cin>>n;
  int c[1000]; rep(i,1000)c[i]=1;

  for(int i=1;i<n+1;i++){
    if(isp(i)) c[i]+=factp(n,i);
  }
  
  for(int i=0;i<1000;i++){
    ans=ans*c[i]%mod;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		int cnt1 = A/C;
		int cnt2 = B/D;

		if(A%C != 0)cnt1++;
		if(B%D != 0)cnt2++;

		if(cnt1 >= cnt2)System.out.println(L-cnt1);
		else System.out.println(L-cnt2);

	}

}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 2010

// 加減乗算で MOD を自動で取ってくれる型
// 割り算はやらないので逆元を適宜求めること
struct mint {
    ll x;
    mint(ll x = 0) : x(x % MOD) {}
    mint& operator += (const mint a) {
        if ( (x += a.x) >= MOD) { x -= MOD; }
        return *this;
    }
    mint& operator -= (const mint a) {
        if ( (x += MOD - a.x) >= MOD) { x -= MOD; }
        return *this;
    }
    mint& operator *= (const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator + (const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator - (const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator * (const mint a) const {
        mint res(*this);
        return res *= a;
    }
};

ll N, M;
vector<ll> S, T;

// Sを [0, i), Tを [0, j) までみたときに
// 一致している共通部分列の数
// [2] の部分は以下を表す
//  0: i がまだ動く可能性がある。 j はまだ動かさない
//  1: i はもう動かない、 j を動かす
mint dp[2][MAX_N][MAX_N];

signed main()
{
    cin >> N >> M;
    S.resize(N+1); T.resize(M+1);
    REP(i, N) { cin >> S[i]; }
    REP(i, M) { cin >> T[i]; }

    // 「何もない」部分列があるため 0, 0 のときは 1
    dp[0][0][0] = 1;

    // 配る DP
    for(int i = 0; i <= N; ++i) {
        for(int j = 0; j <= M; ++j) {
            // 斜め移動が起きるまでの経路を 1 通りにするる
            dp[0][i+1][j] += dp[0][i][j];   // i が動くモード
            dp[1][i][j] += dp[0][i][j];     // ここで i は停止する場合（j が動くモードへ切り替え）
            dp[1][i][j+1] += dp[1][i][j];   // j が動くモード
            if(S[i] == T[j]) {
                // 斜め移動が発生したら、リセット
                dp[0][i+1][j+1] += dp[1][i][j];
                // S[i] と T[j] が同じ
                // → これ以降に見つかる共通部分列がここまでの数ぶん増える
                // この値はここから先の i 方向、 j 方向へ伝搬する
            }
        }
    }
    mint ans = dp[1][N][M];

    printf("%lld\n", ans.x);
    return 0;
}


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

// Maximum Profit

int main(){
    int N;
    cin >> N;
    int R[N], S[N];
    REP(i,N){
        cin >> R[i];
    }
    int t = 1e+9;
    REP(i,N){
        if(R[i]<t){
            t = R[i];
        }
        S[i] = t;
    }
    int ans = -1e+9;
    REP(i,N-1){
        ans = max(ans,R[i+1]-S[i]);
    }
    cout << ans << endl;
    return 0;
}

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

signed main(){
    int x[5];
    REP(i,5){
        cin>>x[i];
        if(x[i] == 0)cout<<i+1<<endl;
    }
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  string s;
  cin>>s;
  ll x=0,y=0;
  for(int i=0;i<n;i++){
    if('A'<=s[i]&&s[i]<='M'){
      x++;
    }else if('N'<=s[i]&&s[i]<='Z'){
      x--;
    }else if('a'<=s[i]&&s[i]<='m'){
      y++;
    }else{
      y--;
    }
  }
  cout<<abs(x)+abs(y)<<endl;
  if(x<0){
    for(int i=0;i<abs(x);i++)
      cout<<'N';
  }else if(x>0){
    for(int i=0;i<x;i++)
      cout<<'A';
  }
  if(y<0){
    for(int i=0;i<abs(y);i++)
      cout<<'n';
  }else if(y>0){
    for(int i=0;i<y;i++)
      cout<<'a';
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 3324
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<deque>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vpii=vector<pii>;


void solve(vi&r, vvi&e)
{
	deque<int> q;

	q.push_back(1);
	while(!q.empty())
	{
		int c=q[0];
		q.pop_front();
		for(int me:e[c])
		{
			if(r[me]>=0) continue;
			r[me]=c;
			q.push_back(me);
		}
	}
}


int main(void)
{
	int n, m;

	while(scanf("%d%d", &n, &m)==2)
	{
		vvi e(n+1);
		vi r(n+1, -1);

		for(int i=0;i<m;i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			e[a].push_back(b);
			e[b].push_back(a);
		}

		r[1]=0;
		solve(r, e);

		bool is_ok=true;
		for(int i=1;i<=n;i++)
		{
			if(r[i]<0) is_ok=false;
		}

		if(is_ok)
		{
			printf("Yes\n");
			for(int i=2;i<=n;i++) printf("%d\n", r[i]);
		}
		else
		{
			printf("No\n");
		}
	}
	return 0;
}


Measured memory_bytes: 9708
import java.util.Scanner

object Main {
  def solve(sc: => Scanner): Unit = {
    val A, B, C = sc.nextInt
    println(if (A == B) (C) else (if (A == C) (B) else (A)))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)

    solve(sc)
  }
}


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

typedef long long ll;
typedef unsigned long long ull;

bool is_prime(ll p) {
  if (p < 2) return false;
  if (p == 2) return true;
  if (p % 2 == 0) return false;
  for (ll i = 3; i <= sqrt(p); i+=2) {
    if (p % i == 0) {
      return false;
    }
  }
  return true;
}

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

  for (;; ++x) {
    if (is_prime(x)) break;
  }

  cout << x << endl;
  
  return 0;
}

Measured memory_bytes: 384
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np

N, M, C = map(int, input().split())
B = np.array([int(x) for x in input().split()])
A = np.array([
        [int(x) for x in input().split()]
        for _ in range(N)])

print(((A.dot(B) + C) > 0).sum())

Measured memory_bytes: 12452
//
//  main.cpp
//  counting_sort
//
//  Created by ???????????? on 2017/10/09.
//  Copyright ?? 2017 ????????????. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <climits>

using namespace std;

void counting_sort(int A[], int B[], int k, int n){
    int i, j, C[k+1];
    
    for (i = 0; i < k; i++){
        C[i] = 0;
    }
    
    for (j = 0; j < n; j++){
        C[A[j]]++;
    }
    
    for(i = 1; i <= k ; i++){
        C[i] = C[i] + C[i-1];
    }
    
    for(j = n - 1; j >= 0; j--){
        B[C[A[j]]-1] = A[j];
        C[A[j]]-- ;
    }
    
}

int main(int argc, const char * argv[]) {
    int n, i, max_int;
    scanf("%d", &n);
    int A[n], B[n];
    max_int = INT_MIN;
    for (i = 0; i < n ; i++){
        scanf("%d", &A[i]);
        if(A[i] > max_int) max_int = A[i];
    }
    
    
    counting_sort(A, B, max_int + 1, n);
    for (i = 0; i < n ; i++){
        if(i) cout << " ";
        cout<<B[i];
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 18836
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heapify, heappush 
def main():
    N, M = map(int, readline().split())
    tasks = [[] for _ in range(M)]
    for _ in range(N):
        a, b = map(int, readline().split())
        if M-a<0:
            continue
        tasks[M-a].append(b)
    s = 0
    h = []
    for i in reversed(range(M)):
        for b in tasks[i]:
            heappush(h, -b)
        if len(h)>0:
            s+=-heappop(h)
    print(s)
if __name__ == '__main__':
    main()


Measured memory_bytes: 19660
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main()
{
	for(int n;cin>>n;)
		printf("3C%02d\n",(n-1)%39+1);
	
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<bitset>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
typedef long long int ll;
#define int long long
typedef pair<int,int> P;
struct edge{int to,cost;};
#define REP(i,n) for(int i=0;i<(n);i++)
const int INF=100000000000000000;

signed main(){
	int A,B,C;
	cin>>A>>B>>C;
	cout<<A*B/2<<endl;
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

mx = max(A)
mn = min(A)

R = -1
for i in range(mn, mx + 1):
    s = 0
    for a in A:
        s += (i - a)** 2
    R = s if R < 0 or s < R else R

print(R)



Measured memory_bytes: 3060
def main():
    N, M = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(M)]
    S = sorted(A, key=lambda x: x[1])
    count = 0
    last = 0
    for s in S:
        if last < s[0]:
            count += 1
            last = s[1] - 1
    print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 62168
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		while(true){
			int tripCost = stdIn.nextInt();
			if(tripCost == 0){break;}

			int savingMoney = 0;
			int necessaryMonth = -1;
			boolean checkFlag = false;

			for(int i=1;i<=12;i++){
				int income = stdIn.nextInt();
				int payOut = stdIn.nextInt();

				savingMoney = savingMoney + income - payOut;
				if(checkFlag == false & savingMoney >= tripCost){
					necessaryMonth = i;
					checkFlag = true;
				}
			}
			if(necessaryMonth == -1){
				System.out.println("NA");
			}else{
				System.out.println(necessaryMonth);
			}
		}
	}
}

Measured memory_bytes: 12000
import numpy as np
from collections import defaultdict
from heapq import heappush, heappop


def djkstra_adj_list(adj_list, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = adj_list[u]
        for v, weight in vs:
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def djkstra_adj_mat(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def main():

    r = int(input())
    print(3 * (r ** 2))


if __name__ == '__main__':
    main()


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

int main(){
  int A, B, C;
  cin >> A >> B >> C;
  if(B <= A && C <= A) {
    cout << A*10+B+C << endl;
  }else if(A <= B && C <= B) {
    cout << B*10+A+C << endl;
  } else {
    cout << C*10+A+B << endl;
  }
  return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
    ll h,w,ans=INF,a,b,c,d; cin>>h>>w;
    rep(i,h-1){
        a=w*(i+1);
        b=w*((h-i)/2);
        c=w*((h-i-1)/2);
        d=max(max(a,b),c)-min(min(a,b),c);
        ans=min(ans,d);
        b=(h-i-1)*((w+1)/2);
        c=(h-i-1)*(w/2);
        d=max(max(a,b),c)-min(min(a,b),c);
        ans=min(ans,d);
    }
    rep(i,w-1){
        a=h*(i+1);
        b=h*((w-i)/2);
        c=h*((w-i-1)/2);
        d=max(max(a,b),c)-min(min(a,b),c);
        ans=min(ans,d);
        b=(w-i-1)*((h+1)/2);
        c=(w-i-1)*(h/2);
        d=max(max(a,b),c)-min(min(a,b),c);
        ans=min(ans,d);
    }
    cout<<ans<<endl;
}

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

using namespace std;

const int MAX_N = 1e7 + 200, mod = 998244353;

int fac[MAX_N], inv[MAX_N], fac_inv[MAX_N], n, pow2[MAX_N];

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int comb(int n_, int k_) { return 1LL * fac[n_] * fac_inv[n_ - k_] % mod * fac_inv[k_] % mod; }

int main()
{
    scanf("%d", &n);
    for (int i = fac[0] = pow2[0] = 1; i <= n; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod, pow2[i] = 1LL * pow2[i - 1] * 2 % mod;
    fac_inv[n] = quick_pow(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--)
    {
        inv[i] = 1LL * fac_inv[i + 1] * fac[i] % mod;
        fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod;
    }
    int ans = quick_pow(3, n);
    for (int i = (n >> 1) + 1; i <= n; i++)
        ans = (1LL * ans - 2LL * comb(n, i) * pow2[n - i] % mod + mod) % mod;
    printf("%d", ans);
    return 0;
}

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

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<ll> x(n);
    for(int i = 0; i < n; ++i){
        cin >> x.at(i);
    }
    vector<ll> y = x;
    sort(y.begin(), y.end());
    for(int i = 0; i < n; ++i){
        const ll index = n / 2 - 1;
        const ll index2 = lower_bound(y.begin(), y.end(), x.at(i)) - y.begin();
        if(index2 > index){
            cout << y.at(index) << endl;
        }else{
            cout << y.at(index + 1) << endl;
        }
    }
    return 0;
}


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

int main(){
    string S, T;
    cin >> S >> T;
    int N;
    N = S.size();

    int cnt = 0;
    rep(i,N) {
        if (S[i] != T[i]) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3912
#include <cstdio>

double dp[3000];
int N;

int main(){
  dp[0]=1;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    double P;
    scanf("%lf",&P);
    for(int j=i;j>=0;j--){
      dp[j+1]+=dp[j]*P;
      dp[j]*=(1-P);
    }
  }
  double ans=0;
  for(int i=N/2+1;i<=N;i++){
    ans+=dp[i];
  }
  printf("%.10lf\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>

using namespace std;


int main() {
	map<int, int> mp;
	long long int n, m=0,tmp=0,ax=0,k=0,t[500000],x,y,res[5000],a,b,c,GCD,two=1,kisuu=0,p,q,r;
	string str, str2[5000];
	cin>>a>>b>>c;
	if (a == b && b == c&&a%2==0) { cout << -1; }
	if (a % 2 == 1 ||b % 2 == 1 ||c% 2 == 1) { cout << 0; return 0; }
	p =abs( b - a);
	q = abs(c - b);
	r = abs(c - a);

	for (int i =0; i <= 100; i++) {
		if (p % 2 == 1 || q % 2 == 1 || r % 2 == 1) { cout << i; return 0; }
		p /= 2;
		q /= 2;
		r /= 2;
	}

}

Measured memory_bytes: 256
import java.util.*;
import java.io.PrintWriter;
public class Main{
  public static long mod=1000000007;
  public static long Hoku(long a, long b){
    if(b==0){return 1;}
    else if(b%2==0){
      long k =Hoku(a,b/2);
      return k*k%mod;}
    else{long t=Hoku(a,b-1);
         return t*a%mod;}
  }
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    long N=sc.nextLong();
    int K =sc.nextInt();
    sc.close();
    long P[]=new long[K+1];
    long x=0;
    for(int i=K;i>0;i--){
      long j=K/i;
       P[i]=Hoku(j,N);
      for(int l=2;l<=j;l++){
        P[i]=P[i]-P[i*l];}
      x=(x+i*P[i])%mod;}
    while(x<0){x=x+mod;}
    System.out.println(x);
  }
}

Measured memory_bytes: 37392
#include <iostream>
#include <cmath>
#include <vector> 
#include <limits>
using namespace std;
int N;
int int_inf = numeric_limits<int>::max();

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

int jump(int history, int h_destination, int h_departure){
  return history + abs(h_destination-h_departure);
}

int main(){
  cin >> N;
  vector<int> footing(N);
  vector<int> dp(N,int_inf);
  for(int i=0; i<N; i++) cin >> footing[i];
  
  for(int i=0; i<N; i++){
    if(i==0){chmin(dp[i], 0); continue;}
    if(i==1){chmin(dp[i], jump(dp[i-1], footing[i], footing[i-1])); continue;}
    chmin(dp[i], jump(dp[i-1], footing[i], footing[i-1]));
    chmin(dp[i], jump(dp[i-2], footing[i], footing[i-2]));
  }
  cout << dp[N-1] << "\n";
}

Measured memory_bytes: 1024
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		for(int a = 1;a>0;a++){
			int m = scan.nextInt();
			int f = scan.nextInt();
			int r = scan.nextInt();
			if(m == -1 && f == -1 && r == -1){
				break;
			}
			if(m != -1 && f != -1){
				if(m+f >= 80){
					System.out.println("A");
				}else if(m+f >=65){
					System.out.println("B");
				}else if(m+f >= 50){
					System.out.println("C");
				}else if(m+f >= 30){
					if(r >=50){
						System.out.println("C");
					}else{
						System.out.println("D");
					}
				}else{
					System.out.println("F");
				}
			}else{
				System.out.println("F");
			}
		}
	}
}

Measured memory_bytes: 19236
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = n*n;
        int[][] v = new int[n][n];
        int[] in = new int[m];
        int[] out = new int[m];
        int[][] next = new int[m][2];
        int[] d = new int[m];

        for(int i=0; i<n; i++) {
            for(int j=0; j<n-1; j++) {
                int b  = sc.nextInt() - 1;
                int key = key(i, b, n);
                v[i][j] = key;
                if(j>0) {
                    int pkey = v[i][j-1];
                    int ind = key < pkey ? 0 : 1;
                    next[pkey][out[pkey]] = key;
                    out[pkey]++;
                    in[key]++;
                }
            }
        }

        Queue<Integer> q = new LinkedList<Integer>();
        int res = 0;
        for(int i=0; i<m; i++) {
            if(in[i] == 0) {
                q.add(i);
                d[i] = 1;
                res = 1;
            }
        }
        while(!q.isEmpty()) {
            int p = q.poll();
            for(int i=0; i<out[p]; i++) {
                int np = next[p][i];
                d[np] = Math.max(d[np], d[p] + 1);
                res = Math.max(res, d[np]);
                in[np]--;
                if(in[np] == 0) {
                    q.offer(np);
                }
            }
        }

        for(int i=0; i<m; i++) {
            if(in[i] > 0) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(res);

    }

    static int key(int a, int b, int n) {
        return Math.max(a, b) * n + Math.min(a, b);
    }

}


Measured memory_bytes: 197788
from collections import defaultdict
n,m=map(int,input().split())

price_list=[0]*n
num_dic=defaultdict(int)

def mergesort(a):
    def _merge_sort(a, left: int, right: int):
        if left < right:
            center = (left+right)//2

            _merge_sort(a,left,center)
            _merge_sort(a,center+1,right)

            #pは前半部をbuffにコピーする際のインデックス、jで取り出す
            p=j=0
            i=k=left

            #配列の前半部をbuffにコピー
            while i <= center:
                buff[p]=a[i]
                p+=1
                i+=1

            #後半部をコピーされた前半部と比較、小さい方をaに格納していく
            while i<= right and j < p:
                if buff[j] <= a[i]:
                    a[k]=buff[j]
                    j+=1
                else:
                    a[k]=a[i]
                    i+=1
                k+=1

            while j < p:
                a[k] =buff[j]
                k+=1
                j+=1

    n=len(a)
    #merge結果を一時的に格納
    buff=[None]*n
    _merge_sort(a,0,n-1)
    del buff

for i in range(n):
    a,b=map(int,input().split())
    price_list[i]=a
    if num_dic[price_list[i]] is None:
        num_dic[price_list[i]]=b
    else:
        num_dic[price_list[i]]+=b

mergesort(price_list)
#同じ値段と違う値段で場合分け
price_sum=0
drink_count=0
for i in range(n):
    if i!=0 and price_list[i-1]==price_list[i]:
        continue
    else:
        #i番目のドリンクを買い占め
        drink_count+=num_dic[price_list[i]]
        if drink_count>m:
            drink_count-=num_dic[price_list[i]]
            stop=i
            break
        p=price_list[i]*num_dic[price_list[i]]
        price_sum+=p

k=m-drink_count
price_sum+=price_list[i]*k

print(price_sum)

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

void swap(int *nx, int *ny)
{
    int temp = *nx;
    *nx = *ny;
    *ny = temp;
}


void sort3(int *n1, int *n2, int *n3)
{
    if (*n1 > *n2) swap(n1, n2);
    if (*n2 > *n3) swap(n2, n3);
    if (*n1 > *n2) swap(n1, n2);
}


int main()
{
    int R, G, B, N;
    scanf("%d%d%d%d", &R, &G, &B, &N);
    sort3(&R, &G, &B);

    int r, g;
    int ans = 0;
    for (int i = 0; i < N/R + 1; ++i)
    {
        r = i;
        if (r*R > N) break;
        for (int j = 0; j < (N-r*R)/G + 1; ++j)
        {
            g = j;
            if (r*R + g*G > N) break;
            int rem = N - r*R - g*G;
            if (rem % B == 0) ans++;
        }
    }

    printf("%d\n", ans);

}

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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;

typedef long long ll;



int main(){

    int a,b,m;
    cin >> a >> b >> m;

    vector<int> av;
    vector<int> bv;

    int mina = INT_MAX;
    int minb = INT_MAX;
    int tmp;

    rep(i, a){
        cin >> tmp;

        av.pback(tmp);
        mina = min(mina, tmp);
    }

    rep(i, b){
        cin >> tmp;

        bv.pback(tmp);
        minb = min(minb, tmp);
    }

    int ans = mina + minb;

    rep(i, m){
        int x, y, c;
        cin >> x >> y >> c;

        //0indexにもどす
        x--;
        y--;

        ans = min(ans, av[x] + bv[y] - c);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 3100;
ll dp[maxn][maxn][2];
ll arr[maxn], n;

ll recursion(int l, int r, bool turn) {
    if(l > r) return dp[l][r][turn] = 0;
    if(dp[l][r][turn] != -1) return dp[l][r][turn];

    if(!turn) {
        // X's turn (First player)
        if(l == r) {
            return dp[l][r][turn] = arr[l];
        }
        else {
            return dp[l][r][turn] = max(recursion(l+1, r, !turn) + arr[l], recursion(l, r-1, !turn) + arr[r]);
        }
    }
    else {
        //Y's turn (Second Player)
        if(l == r) {
            return dp[l][r][turn] = -arr[l];
        }
        else {
            return dp[l][r][turn] = min(recursion(l+1, r, !turn) - arr[l], recursion(l, r-1, !turn) - arr[r]);
        }
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>arr[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<recursion(1, n, 0)<<"\n";
    return 0;
}


Measured memory_bytes: 150528
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
using namespace std;

int main() {
    int n, m, a;
    cin >> n >> m;
    priority_queue<int> p;
    for(int i = 0; i < n; i++){
        cin >> a;
        p.push(a);
    }
    while(m > 0){
        a = p.top();
        p.pop();
        while(m > 0 && a >= p.top()){
            a >>= 1;
            m--;
        }
        p.push(a);
    }
    long long r = 0;
    while(p.size()){
        r += p.top();
        p.pop();
    }
    cout << r << '\n';
}


Measured memory_bytes: 892
N = int(input())
order = list(map(int, input().split()))
total = sum(list(map(int, input().split())))  #合計点
point_added = list(map(int, input().split()))

for i in range(N-1):
  if order[i + 1] == order[i] + 1:
    total += point_added[order[i] - 1]
    
print(total)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
	int k = 0;
	cin >> k;
	std::string s;
	cin >> s;

	if (s.size() <= k)
	{
		cout << s;
		return 0;
	}

	cout << s.substr(0, k) + "...";
}



Measured memory_bytes: 3104
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n;
ll z, w;
vector<ll> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>z>>w;

    for (int i = 0; i < n; i++)
    {
        ll tempa;
        cin >>tempa;
        a.push_back(tempa);
    }
    if(n==1){
        return cout << abs(a[n-1]-w)<< "\n",0;
    }
    cout << max(abs(a[n-1]-w),abs(a[n-2]-a[n-1])) << "\n";
}



Measured memory_bytes: 256