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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

const int CASES = 2;

struct Data{
    ll a;
    ll f;
    ll af;
    bool operator< (const Data& rhs) const{
        return af < rhs.af;
    };
};

bool check(ll N, ll K, const vector<Data>& vec, ll mb){
    for(ll i = 0; i < N; ++i) {
        ll a = vec[i].a;
        ll f = vec[i].f;
        ll af = vec[i].af;

        if(af > mb){
            ll tmp = mb / f;
            ll sub = vec[i].a - tmp;
            if(sub > K){
                return false;
            }
            else{
                K -= sub;
            }
        }
    }
    return true;
}


void solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    vector<ll> F(N);
    vector<Data> AF(N);

    for(ll i = 0; i < N; ++i){
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater<ll>());
    for(ll i = 0; i < N; ++i){
        cin >> F[i];
    }
    sort(F.begin(), F.end());

    ll tmp = 0;
    for(ll i = 0; i < N; ++i){
        tmp = max(tmp, A[i] * F[i]);
        AF[i] = {A[i], F[i], A[i] * F[i]};
    }

    ll lb = 0, ub = tmp;
    while(ub - lb > 1){
        ll mb = (lb + ub) / 2;
        if(check(N, K, AF, mb)){
            ub = mb;
        }else{
            lb = mb;
        }
    }

    if(ub == 1){
        if(check(N, K, AF, 0)){
            ub = 0;
        }
    }
    cout << ub << endl;
    return ;
}

int main() {
    #ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



Measured memory_bytes: 8064
def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]
 
	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])
 
solver()

Measured memory_bytes: 44912
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric>

using namespace std;

typedef long long ll;
const int INF = 1001001001;
const int mod = 1000000007;

// dpテーブル(何行目か, 何番目の縦棒か)
ll dp[110][10];

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    
    dp[0][1] = 1;
    
    for(int i = 0; i < H; ++i){
        
        // i+1行目のdpテーブルを埋めていく
        for(int j = 1; j <= W; ++j){
            // 横棒の並べ方に関するbit全探索
            for(int b = 0; b < (1 << (W - 1)); ++b){
                // 2つの横棒がつながっていればcontinue
                bool flag = true;
                for(int l = 0; l < W - 2; ++l){
                    if(((b >> l) & 1) && ((b >> (l + 1)) & 1)){
                        flag = false;
                        break;
                    }
                }
                if(!flag)       continue;
                
                // 左方向に縦線をたどる
                if(j >= 2 && ((b >> (W - j)) & 1)){
                    dp[i + 1][j - 1] += dp[i][j];
                    dp[i + 1][j - 1] %= mod;
                }
                // 右方向に縦棒をたどる
                else if(j <= W - 1 && ((b >> (W - 1 - j)) & 1)){
                    dp[i + 1][j + 1] += dp[i][j];
                    dp[i + 1][j + 1] %= mod;
                }
                // 横棒をたどらない
                else{
                    dp[i + 1][j] += dp[i][j];
                    dp[i + 1][j] %= mod;
                }
            }
        }
    }
    
    cout << dp[H][K] << 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 s = sc.nextInt();
		int a = s/100;
		int b = s-a*100;

		if(a>=1){
				if(b<=a*5){
					System.out.println(1);
				}else{
					System.out.println(0);
				}
		}else{
			System.out.println(0);
		}
	}

}


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

//temmplate------
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define INF 1e9
#define ZERO(a) memset(a, 0, sizeof(a))
typedef long long lint;
//------template

int main(){
    int N;
    int P;
    cin >> N;
    P = (N+1)/2;
    cout << P << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    for (int i = 1; i <= 1000; i++) {
        if (a <= k*i && k*i <= b) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


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

void solve() {
	string s, t;
	cin >> s >> t;

	if (s.length() != t.length() - 1) {
		cout << "No";
	}
	else {
		bool check = true;
		for (int i = 0; i < s.length(); i++) {
			if (s[i] != t[i]) {
				check = false;
			}
		}
		if (!check) {
			cout << "No";
		}
		else {
			if (isalpha(t[t.length() - 1])) {
				cout << "Yes";
			}
			else {
				cout << "No";
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
# ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
# endif
	solve();
	return 0;
}

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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint=vector<int>;
using vvint=vector<vint>;
using pint=pair<int, int>;
using vpint=vector<pint>;
template<typename T> using priority_queue_rev=priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028L;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T1, typename T2> bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

string S;
signed main() {
    cin >> S;
    rep(i, S.length()) {
        for (int j = i; j <= S.length(); j++) {
            if (S.substr(0, i) + S.substr(j, S.length() - j) == "keyence") { fin("YES"); }
        }
    }
    cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,x,y,v[100005],p[100005];

vector <int> g[100005],q;

bool Find(int nod){
    if(v[nod]) return 0;
    q.push_back(nod);
    v[nod]=1;
    if(nod==n) return 1;
    for(int i : g[nod]){
        if(Find(i)) return 1;
    }
    q.pop_back();
    return 0;
}

void Spread(int nod,int v){
    p[nod]=v;
    for(int i : g[nod]){
        if(!p[i]) Spread(i,v);
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<n;i++){
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    Find(1);
    for(int i=0;i<(q.size()+1)/2;i++){
        p[q[i]]=1;
    }
    for(int i=(q.size()+1)/2;i<q.size();i++){
        p[q[i]]=2;
    }
    for(int i=1;i<=n;i++){
        if(p[i]) Spread(i,p[i]);
    }
    x=0,y=0;
    for(int i=1;i<=n;i++){
        if(p[i]==1) x++;
        else y++;
    }
    if(x>y) cout << "Fennec";
    else cout << "Snuke";
}


Measured memory_bytes: 11768
#include <stdio.h>

int ok_list[100010];

int main(void) {
	int n,i;
	int a,b;
	int max;
	scanf("%d",&n);
	for(i=0;i<n;i++) {
		scanf("%d%d",&a,&b);
		ok_list[a]++;
		ok_list[b+1]--;
	}
	for(i=1;i<100010;i++)ok_list[i]+=ok_list[i-1];
	max=1;
	for(i=1;i<100010;i++) {
		if(ok_list[i]>=i-1)max=i;
	}
	printf("%d\n",max-1);
	return 0;
}

Measured memory_bytes: 752
from math import factorial

n = int(input())
a = list(map(int,input().split()))
se = set()
mod = 10**9+7

for i,j in enumerate(a):
    if j in se:
        two = i
    else:
        se.add(j)

one = a.index(a[two])

def prepare(n, MOD):
    facts = [1]*(n+1)
    for i in range(1, n+1):
        facts[i] = facts[i-1]*i%MOD
    invs = [1]*(n+1)
    invs[n] = pow(facts[n], MOD-2, MOD)
    for i in range(0, n)[::-1]:
        invs[i] = invs[i+1] * (i+1) % MOD
    return facts, invs

facts,invs = prepare(n+1,mod)

def make_combi(facts,invs,n,r,mod):
    return facts[n] * invs[r] * invs[n - r] %mod

for i in range(1,n+2):
    point = make_combi(facts,invs,n+1,i,mod)
    if one+n-two >= i-1:
        point -= make_combi(facts,invs,one+n-two,i-1,mod)
    print(point%mod)

Measured memory_bytes: 20576
require 'pp'

# 入力値を数値で返却する
def gets_i()
  gets.chomp.to_i
end

# 空白区切の入力値を数値の配列で返却する
def gets_i_list()
  gets.chomp.split(" ").map(&:to_i)
end

N = gets_i
a_list = gets_i_list

nums = []
a_list.each do |a|
  nums.push(a - 1)
  nums.push(a)
  nums.push(a + 1)
end

puts nums.inject(Hash.new(0)){|h, e| h.tap{|h| h[e] += 1}}.values.max


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

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector <int> stones(n);
    vector <int> dp(max(n, k));
    for(int i = 0;i < n;i++)
    {
        cin >> stones[i];
    }
    dp[0] = 0;
    for(int i =1;i < k;i++)
    {
        dp[i] = abs(stones[0] - stones[i]);
        // cout << dp[i] << endl;
    }
    if(n >= k)
    {
        for(int i = k;i < n;i++)
        {
            int min = INT_MAX;
            for(int j = 1;j <= k;j++)
            {
                // cout<<i<<" "<<j<<" "<< stones[i]<< " " << stones[i - j] << " " << dp[i - j] << endl;
                int temp = abs(stones[i] - stones[i - j]) + dp[i - j];
                if(min > temp)
                {
                    // cout << min<< " "<< temp;
                    min = temp;
                }
            }
            dp[i] = min;
        }
    }
    cout << dp[n - 1] << endl;
    return 0;

}

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

vt=va=1
for _ in range(N):
  T,A=map(int,input().split())
  kt=-(-vt//T)
  ka=-(-va//A)
  
  k=max(kt,ka)
  vt=k*T
  va=k*A  
  #print(vt,va)
  
print(vt+va)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
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; }

int main()
{
	int n, k; cin >> n >> k;
	string s; cin >> s;
	s = "#" + s + "#";
	int h = 0;
	reps(i, n)
	{
		if (s[i] == 'L' && s[i - 1] == 'L')h++;
		if (s[i] == 'R' && s[i + 1] == 'R')h++;
	}
	h += 2 * k;
	int ans = min(h, n - 1);
	co(ans);
	return 0;
}

Measured memory_bytes: 512
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))

    l=0
    r=1
    ans=0
    now_xor=a[0]
    now_sum=a[0]
    while l<n:
        if r<n:
            now_xor^=a[r]
            now_sum+=a[r]
            while now_xor!=now_sum:
                ans+=1
                ans+=r-l-1
                now_xor^=a[l]
                now_sum-=a[l]
                l+=1
            r+=1
        else:
            l+=1
            ans+=1
            ans+=r-l

    print(ans)

if __name__=="__main__":
    main()

Measured memory_bytes: 23508
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
      int N = nextInt();
      if(N < 1200){
        myout("ABC");
      }else if(N < 2800){
        myout("ARC");
      }else{
        myout("AGC");
      }
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 32888
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
 
int N;
vector<int> v;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  //freopen("5.txt", "r", stdin);
  cin >> N;
  string S;
  cin >> S;
  N = S.length();
  int west = 0, east = 0;
  int cnt_west[N], cnt_east[N];
  for(int i=N-1; i>=0; --i){
    cnt_west[i] = west;
    if(S[i] == 'W')
      ++west;
  }
  for(int i=0; i<N; ++i){
    cnt_east[i] = east;
    if(S[i] == 'E')
      ++east;
  }
  int dp[N+1];
  for(int i=0; i<N; ++i){
    if(i == 0){
       dp[i] = (S[i] == 'W') ? west - 1 : west; 
    }
    else if(i == N-1){
      dp[i] = (S[i] == 'E') ? east - 1 : east; 
    }
    else{
      dp[i] = cnt_east[i] + cnt_west[i];
    }
  }
  int k = 0, res;
  for(int i=0; i<N; ++i){
     if(dp[i] > k){
         k = dp[i];
         res = N - dp[i] - 1;
       }
  }
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 4244
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Traveling
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String input;
            String[] splitted;
            List<Plan> plans = new List<Plan>();
            plans.Add(new Plan("0", "0", "0"));
            for(int i = 0; i < N; i++)
            {
                input = Console.ReadLine();
                splitted = input.Split(' ');
                plans.Add(new Plan(splitted[0], splitted[1], splitted[2]));
            }
            bool flag = true;

            for(int i = 0; i < N; i++)
            {
                if (!plans[i].CanGo(plans[i + 1]))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
    class Plan
    {
        public int t;
        public int x;
        public int y;
        public Plan(String T,String X,String Y)
        {
            t = int.Parse(T);
            x = int.Parse(X);
            y = int.Parse(Y);
        }
        public bool CanGo(Plan p)
        {
            int time = Math.Abs(t - p.t);
            int xMove = Math.Abs(x - p.x);
            int yMove = Math.Abs(y - p.y);
            if (xMove + yMove > time)
            {
                return false;
            }
            else if ((time - xMove - yMove) % 2 != 0)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    }
}


Measured memory_bytes: 19776
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC
{
    class Program
    {
        static void Main(string[] args)
        {
            ABC113_B();
        }

        static void ABC113_B()
        {
            var N = int.Parse(Console.ReadLine());
            var TA = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var T = TA[0];
            var A = TA[1];
            var H = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var min = double.MaxValue;
            var point = 1;
            for (var i = 0; i < N; i++)
            {
                if (min > Math.Abs(A - (T - (H[i] * 0.006))))
                {
                    min = Math.Abs(A - (T - (H[i] * 0.006)));
                    point = i+1;
                }
            }
            Console.WriteLine(point);
        }
    }
}

Measured memory_bytes: 13340
#include<string.h>
#include <iostream>
#include<cstdio>
#include <stack>
#include <vector>
// this is a comment
using namespace std;
#define INF 0x7ffffff
typedef long long ll;
const int maxn=1e5+10;
int pre[maxn];
int dis[maxn];
int findset(int x)
{
    if(x==pre[x])   return x;
    int root=findset(pre[x]);
    dis[x]=dis[pre[x]]+dis[x];
    return pre[x]=root;
}
bool unionset(int x,int y,int w)
{
    int fx=findset(x),fy=findset(y);
    if(fx==fy)
        return w==dis[y]-dis[x];
    pre[fy]=fx;
    dis[fy]=dis[x]+w-dis[y];
    return true;
}
int n,m;       //input members
int main()    //main body
{
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
    pre[i]=i;
   bool lose=true;
   for(int i=0;i<m;i++)
   {
       int x,y,w;
   scanf("%d%d%d",&x,&y,&w);
        if(lose)
       lose=unionset(x,y,w);
   }
   if(lose) printf("Yes\n");          //output
   else     printf("No\n");
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner s = new Scanner(System.in);
	int H = s.nextInt();
	int W = s.nextInt();

	while(H != 0 || W != 0){
	    for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
		    if(i == 0 || i == H-1) System.out.print("#");
		    else if(j == 0 || j == W-1) System.out.print("#");
		    else System.out.print(".");
		}
		System.out.println();
	    }
	    System.out.println();

	    H = s.nextInt();
	    W = s.nextInt();
	}
    }
}



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

int main()
{
  string s;
  cin >> s;
  int div = 0;
  for (int i = 0; i < s.size(); i++)
  {
    div += stoi(s.substr(i,1));
  }

  if(stoi(s) % div == 0)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
// Undone
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
#define MOD 1000000007
using namespace std;
int W[200], sum[200];
signed main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) cin >> W[i];
  
  sum[0] = 0;
  for (int i = 0; i < N; i++) sum[i+1] = sum[i] + W[i];
  
  int ans = INF;
  for (int i = 0; i < N-1; i++) {
    int l = sum[i+1];
    int r = sum[N]-l;
    ans = min(abs(l-r), ans);
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [abs(a) for a in A]
    t = min(B)
    fu = 0
    for a in A:
        if a < 0:
            fu += 1
    print(sum(B) - t*2 if fu % 2 else sum(B))


if __name__ == "__main__":
    main()

Measured memory_bytes: 20552
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n; ll a[100009], b[100009], s[100009], ret[100009];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
	sort(b, b + n + 1);
	for (int i = 0; i < n; i++) s[i + 1] = s[i] + (b[i + 1] - b[i]) * (n - i);
	vector<ll> l; l.push_back(0);
	for (int i = 1; i <= n; i++) {
		if (a[l.back()] < a[i]) l.push_back(i);
	}
	for (int i = 1; i < l.size(); i++) {
		int ptl = lower_bound(b, b + n, a[l[i - 1]]) - b;
		int ptr = lower_bound(b, b + n, a[l[i]]) - b;
		ret[l[i]] = s[ptr] - s[ptl];
	}
	for (int i = 1; i <= n; i++) printf("%lld\n", ret[i]);
	return 0;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);

/* -----  2019/06/22  Problem: ABC 131 D / Link: http://abc131.contest.atcoder.jp/tasks/abc131_d  ----- */


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

	LL N; cin >> N;
	vector<PLL>seg(N);
	FOR(i, 0, N) {
		LL a, b; cin >> a >> b;
		seg[i] = PLL(a, b);
	}

	sort(ALL(seg), [](const PLL& a, const PLL &b) {
		if (a.second == b.second) {
			return a.first > b.first;
		}
		else {
			return a.second < b.second;
		}
	});
	bool ok = 1;
	LL nowt = 0;
	FOR(i, 0, N) {
		if (seg[i].first + nowt > seg[i].second)ok=0;
		else {
			nowt += seg[i].first;
		}
	}

	cout << (ok ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 3456
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int fun (int a , int b)
{
	long long sum = 1;
	long long base = a;
	while (b != 0)
	{
		if (b & 1 == 1) sum = (sum * base) % 1000000007;
		base = (base * base) % 1000000007;
		b = b / 2;
	}
	return sum;
}

int w[100005];

int main()
{
	int n, e;
	while (~scanf("%d", &n))
	{
		memset(w, 0, sizeof(w));
		int i, a, e = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d", &a);
			w[a]++;
			if (w[a] > 2) e++;
			if (n % 2 == 0 && a % 2 == 0) e++;
			if (n % 2 != 0 && a % 2 != 0) e++;
		}
		if (n % 2 == 0 && w[0] != 0) e++;
		if (n % 2 != 0 && w[0] != 1) e++;
		if (e == 0)
		printf("%d\n", fun(2, n / 2));
		else
		printf("0\n");
	}
	return 0;
}


Measured memory_bytes: 512
a = list(input())
b = list(input())
c = list(input())

tmp = a[0]
a.pop(0)
while True:
    if tmp == "a":
        if len(a) == 0:
            print("A")
            break
        tmp = a[0]
        a.pop(0)
    if tmp == "b":
        if len(b) == 0:
            print("B")
            break
        tmp = b[0]
        b.pop(0)
    if tmp == "c":
        if len(c) == 0:
            print("C")
            break
        tmp = c[0]
        c.pop(0)


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

#define debug(a) cout << #a << " " << a << endl;
#define _debug(a, i) cout << #a << "[" << i << "]" \
						  << " = " << a[i] << endl;
#define fastio                        \
	ios_base::sync_with_stdio(false); \
	cin.tie(0);                       \
	cout.tie(0);
#define PI 3.141592654

using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 9;

ll powmod(ll base, ll exp, const ll MOD){ll ans = 1;while (exp){	if (exp & 1)	ans = (ans * base) % MOD;base = (base * base) % MOD;exp >>= 1;}return ans;}
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); }
ll modInverse(ll n, const ll p) { return powmod(n, p - 2, p); }
void add(ll &x, ll v)
{
	x = (x + v) % MOD;
	if (x < 0)
		x += MOD;
}
//ll f[500005];
//ll kCn(ll k, ll n) { return (f[n] * modInverse((f[n - k] * f[k]) % MOD, MOD)) % MOD; }


const int mxN = 2e5 + 100;

void test_case() {
	
}

int main()
{
	fastio;
	int h, w, k;
	cin >> h >> w >> k;
	char a[6][6];
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j)
			cin >> a[i][j];
	}

	char b[6][6];
	int ans = 0;
	for (int i = 0; i < (1 << h); ++i) {
		for (int j = 0; j < (1 << w); ++j) {
			memcpy(b, a, sizeof(b));
			for (int k = 0; k < h; ++k) {
				if ((i >> k) & 1)
					for (int k1 = 0; k1 < w; ++k1)
						b[h - 1 - k][k1] = '.';
			}
			for (int k = 0; k < w; ++k) {
				if ((j >> k) & 1)
					for (int k1 = 0; k1 < h; ++k1)
						b[k1][w - 1 - k] = '.';
			}

			int cnt = 0;
			for (int k1 = 0; k1 < h; ++k1) {
				for (int k2 = 0; k2 < w; ++k2)
					cnt += b[k1][k2] == '#';
			}
			ans += cnt == k;
		}
	}
	cout << ans;
	return 0;
}

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

using namespace std;

int main(){
	
	string A,B,C;
	
	cin>>A>>B;
	
	int la = A.length();
	
	int lb = B.length();
	
	int dp[la+1][lb+1];
	
	A = "("+A;
	
	B = ")"+B;
	
	memset(dp,0,sizeof(dp));
	
	for(int i=1; i<=la; i+=1){
		
		for(int j=1; j<=lb; j+=1){
			
			if(A[i] == B[j]){
				
				dp[i][j] = 1 + dp[i-1][j-1];
			}
			
			else{
				
				dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
			}
		}
	}
	
	int r = la;
	
	int c = lb;
	
	while(r>0 && c>0){
		
		if(A[r] == B[c]){
			
			C += A[r];
			
			r -= 1;
			
			c -= 1;
		}
		
		else if(dp[r][c-1] < dp[r-1][c]){
			
			r -= 1;
		}
		
		else{
			
			c -= 1;
		}
	}
	
	reverse(C.begin(),C.end());
	
	cout<<C;
}

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

int main(){
  long n;
  cin >> n;
  long a=0;
  for(long i=1;i<round(sqrt(n))+1;i++){
    if(n%i==0) a=i;
  }
  long b=n/a;
  cout << a+b-2;
}

Measured memory_bytes: 256
h,w,d = map(int,input().split())
adr = [-1]*(h*w) #indexの数字は[i,j]に書かれている
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        adr[a[j]-1] = [i,j]
        
cost = [0]*(h*w)
for i in range(d,h*w):
    cost[i] = cost[i-d] + abs(adr[i][0]-adr[i-d][0]) + abs(adr[i][1]-adr[i-d][1])
        
q = int(input())
ans = []
for i in range(q):
    l,r = map(int,input().split())
    ans.append(cost[r-1]-cost[l-1])

for i in ans:
    print(i)

Measured memory_bytes: 112136
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            String[] S = new String[N];
            for (int i = 0; i < N; i++) {
                S[i] = in.next();
            }

            HashSet<String> set = new HashSet<String>();
            for (int i = 0; i < N; i++) {
                set.add(S[i]);
            }

            System.out.println(set.size() == 3 ? "Three" : "Four");
        }
    }
}


Measured memory_bytes: 26988
n = int(input())
a = list(map(int, input().split()))

cnt = [0 for _ in range(n)]
for i in range(n):
  cnt[a[i]-1] += 1

s = 0
for i in range(n):
  s += cnt[i] * (cnt[i] - 1) // 2

for i in range(n):
  print(s-cnt[a[i]-1]+1, end="")
  if i != n-1:
    print(" ")
  else:
    print("\n")


Measured memory_bytes: 91088
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  for (int i=0; i<N; i++) cin >> S[i];
  map<string, int> memo; // 登場した文字を記録
  for (int i=0; i<N; i++) {
    if (!memo.count(S[i])) memo[S[i]] = 0;
  }
  cout << memo.size() << endl;
}

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

using namespace std;

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MAX = 1000000;
static const ll INFTY = 1e12;

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;


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

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
//vector<pair<int, int>> gx, gy;
deque<pair<int, int>> que;

typedef vector<vector<int> > Matrix;

const int INF = 100000000;




int main() {

    int N, X, Y;
    cin >> N >> X >> Y;
    Graph g(N);
    REP(i, N-1){
        g[i].push_back(i+1);
        g[i+1].push_back(i);
        // d[i][i+1] = 1;
        // d[i+1][i] = 1;
    }
    X--; Y--;
    g[X].push_back(Y);
    g[Y].push_back(X);
    // d[X][Y] = 1;
    // d[Y][X] = 1;

    vector<ll> ans(N);

    REP(i, N){
        // BFS のためのデータ構造
        vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
        queue<int> que;

        // 初期条件 (頂点 0 を初期ノードとする)
        dist[i] = 0;
        que.push(i); // 0 を橙色頂点にする

        // BFS 開始 (キューが空になるまで探索を行う)
        while (!que.empty()) {
            int v = que.front(); // キューから先頭頂点を取り出す
            que.pop();

            // v から辿れる頂点をすべて調べる
            for (int nv : g[v]) {
                if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

                // 新たな白色頂点 nv について距離情報を更新してキューに追加する
                dist[nv] = dist[v] + 1;
                // cout << "AA" << endl;
                ans[dist[nv]]++;
                que.push(nv);
            }
        }
        
    }

    REP1(i, N){
        cout << ans[i]/2 << endl;
    }
}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <iomanip>
using namespace std;

int main(){
    long long int n,sum=0,k;
    cin>>n;
    vector<int>a(1000001);
    for(int i=0;i<=1000000;i++){
        a[i]=0;
    }
    k=n;
    a[k]++;
    for(int i=0;;i++){
        if(k%2==0){
            k=k/2;
        }
        else{
            k=3*k+1;
        }
        a[k]++;
        if(a[k]==2){
            cout<<i+2<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 4096
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n,a,b=map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()

print(sum(lst[-a:])/a)

pin=lst[-a]
ans=0

l=lst[:-a].count(pin)
r=lst[-a:].count(pin)


if pin*a==sum(lst[-a:]):
    cnt=0
    for i in range(a,min(b,l+r)+1):
        cnt+=cmb(l+r,i)
    
    print(cnt)
    exit()


print(cmb(l+r,r))


Measured memory_bytes: 67516
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <queue>
using namespace std;

int inf = (1 << 30);
int mod = 1e9 + 7;
int64_t inf64 = (1LL << 60);

template <typename T>
T gcd(T a, T b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

template <typename T>
T lcm(T a, T b) {
    T g = gcd(a, b);
    return a / g * b;
}

bool check(vector<int> a, int index, int key){
    if(a[index] >= key) return true;
    else return false;
}

int lower_bound(vector<int> a, int key){
    int left = -1, right = a.size();
    while(right - left > 1){
        int mid = left + (left + right) / 2;
        if(check(a, mid, key)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){

    int a, b, c;
    cin >> a >> b >> c;

    if(a == (b + c) || b == (c + a) || c == (a + b)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

count = 0

while sum(H) != 0:
    temp = 0
    H_max = max(H)
    H_no_max = [h for h in H if h != H_max]
    if len(H_no_max) == 0:
        count += H_max
        break
    H_second_max = max(H_no_max)
    dif = H_max - H_second_max
    
    temp += H.count(H_max)
    for n in range(N-1):
        if H[n] == H[n+1] == H_max:
            temp -= 1
    for n in range(N):
        if H[n] == H_max:
            H[n] = H[n] - dif
    count += dif * temp

print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include<stdio.h>
#include <functional>
#include<algorithm>
#define PI 3.14159265
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define SZ(x) ((int)(x).size())

using namespace std;



int main() {
	int a,b;
	int h=0;
	cin >> a >> b;
	REP(i, b - a) {
		h += i + 1;
	}
	cout << h - b << endl;
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
A = list(map(int, input().split()))
import fractions
a = A[0]
for i in range(1, n):
  a = fractions.gcd(a, A[i])
if max(A) < k:
  print('IMPOSSIBLE')
elif k%a == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Measured memory_bytes: 14252
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		if (n%2==0){
			System.out.println(n);
		}else {
			System.out.println(2*n);
		}
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
const int N=4e5+5,A=26;
string ss[N];
struct node{
    int32_t go[A];
    int32_t up,cnt,te,kak,sko;//<--
    node(){
        memset(go,0,sizeof go);
        up=1;cnt=0;te=0;kak=0;
    }
}t[N];
int f=2;
void add(string&s,int i){
    int v=1;
    for(int c:s){
        t[v].cnt++;
        c-='a';//<-- MIN CHAR
        if(!t[v].go[c]){
            t[v].go[c]=f;
            t[f].up=v;
            t[f].kak=c;
            t[f].sko=1;
            f++;
        }
        v=t[v].go[c];
    }
    t[v].cnt++;
    t[v].te=i;
}
void zk(int v){
    int ku=-1,cu=0;
    forn(x,A){
        int to=t[v].go[x];
        if(to){
            cu++;
            ku=x;
            zk(to);
        }
    }
    if(v!=1&&cu==1&&!t[v].te){
        // dbg(v);
        // assert(ku!=-1);
        t[t[v].go[ku]].sko++;
        t[t[v].up].go[t[v].kak]=t[v].go[ku];
    }
}
int32_t main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>ss[i];
        add(ss[i],i);
    }
    zk(1);
    int q;
    cin>>q;
    while(q--){
        int num;
        string ord;
        cin>>num>>ord;
        int v=1,i=0,ans=0;
        while(1){
            if(t[v].te)ans++;
            if(i==sz(ss[num]))break;
            char tar=ss[num][i];
            forn(x,A){
                char c=ord[x];
                int to=t[v].go[c-'a'];
                if(c==tar){
                    v=to;
                    i+=t[v].sko;
                    break;
                }else if(to){
                    ans+=t[to].cnt;
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int lreval(string s) {
    int val = s[0] - '0';
    for (int i = 1; i < s.length(); i += 2) {
        if (s[i] == '+') {
            val = val + (s[i + 1] - '0');
        } else {
            val = val * (s[i + 1] - '0');
        }
    }
    return val;
}

int creval(string s) {
    int ttl = 0, cur = s[0] - '0';
    for (int i = 1; i < s.length(); i += 2) {
        if (s[i] == '*') {
            cur *= (s[i + 1] - '0');
        } else {
            ttl += cur;
            cur = s[i + 1] - '0';
        }
    }
    ttl += cur;
    return ttl;
}

int main() {
    char mask[] = {'I', 'L', 'M', 'U'};
    string s; cin >> s;
    int m = 0, v; cin >> v;
    // cout << lreval(s) << " " << creval(s) << endl;
    if (lreval(s) == v) m |= 1;
    if (creval(s) == v) m |= 2;
    cout << mask[m] << endl;
}


Measured memory_bytes: 3232
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    NL = len(L)
    NR = len(R)
    i = 0
    j = 0
    ret = 0
    for k in range(left, right):
        if i == NL:
            A[k] = R[j]
            j += 1
        elif j == NR:
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
            ret += NL - i
    return ret


def mergesort(A, left, right):
    ans = 0
    if right - left > 1:
        mid = (left + right) // 2
        ans += mergesort(A, left, mid)
        ans += mergesort(A, mid, right)
        ans += merge(A, left, mid, right)
    return ans


def main():
    N, *S = map(int, open(0).read().split())
    ret = mergesort(S, 0, len(S))
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 27684
#include <bits/stdc++.h>
using namespace std;
int main (){
    int n,c,b,a;
    cin>>n;
    
        c=n;
        b=n/10;
        a=n/100;
        
        if(a==7||b-a*10==7||c-b*10==7){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }

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

const int N = 3e5 + 10;
int n, v, u, c, ce = -1, r = -1, le = 1e9, cnt[N];
long long ans;
vector<pair<int, int> > g[N];

void dfs(int v, int p){
	cnt[v]++;
	bool f = true;
	for (auto q : g[v]){
		int u = q.first, 
			c = q.second;
		if(u != p){
			dfs(u, v);
			ans += (1LL * 2 * min(cnt[u], n - cnt[u]) * c);
			if(2 * min(cnt[u], n - cnt[u]) == n)
				ce = c;
			f &= ((2 * cnt[u]) <= n);
			cnt[v] += cnt[u];
		}
	}
	f &= ((2 * (n - cnt[v])) <= n);
	if(f)
		r = v;	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> n;
	for (int i = 0; i + 1 < n; i++){
		cin >> v >> u >> c;
		v--;u--;
		
		g[v].push_back({u, c});
		g[u].push_back({v, c});
	}
	
	dfs(0, 0);
	
	if(r != -1)
		for (auto u : g[r])
			le = min(le, u.second);
					
	if(ce != -1)
		cout << ans - ce;
	else
		cout << ans - le;
}

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

using namespace std;

bool solve(string s, string t) {
    vector<int> v[26];
    for (int i = 0; i < (int)s.size(); ++i) {
        v[s[i] - 'a'].push_back(i);
    }
    int table[200001] = {0};
    for (int i = 0; i < (int)t.size(); ++i) {
        table[i] = t[i] - 'a';
    }
    for (int i = 0; i < 26; ++i) {
        if ((int)v[i].size() == 0) continue;
        int c = table[v[i][0]];
        for (int j = 1; j < (int)v[i].size(); ++j) {
            if (table[v[i][j]] != c) {
                return 0;
            }
        }
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    if (solve(s, t) + solve(t, s) == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
}
/*
 sの同じ文字のindex列とtのそれが一致すればいい
 
 */


Measured memory_bytes: 3528
#include <stdio.h>
#define N 20
int main(){
  int i,j,x,y,n,step,gems,xy[N+1][N+1],rx,ry,count;
  char dir;
  while(1){
    for(i=0;i<N+1;i++){
      for(j=0;j<N+1;j++){
	xy[i][j] = 0;
      }
    }
    rx = 10;
    ry = 10;
    count = 0;

    scanf("%d",&n);
    if( n==0 ) break;
    gems = n;
    for(i=0;i<n;i++){
      scanf("%d %d",&x,&y);
      xy[y][x] = 1;
    }

    scanf("%d",&n);
    for(j=0;j<n;j++){
      scanf(" %c %d",&dir,&step);
      if( dir == 'E'){
	for(i=rx;i<=rx+step;i++){
	  if( xy[ry][i] == 1 ){
	    count++;
	    xy[ry][i] = 0;
	  }
	}
	rx = i-1;
      }
      else if( dir == 'W'){
	for(i=rx;i>=rx-step;i--){
	  if( xy[ry][i] == 1 ){
	    count++;
	    xy[ry][i] = 0;
	  }
	}
	rx = i+1;
      }
      else if( dir == 'N' ){
	for(i=ry;i<=ry+step;i++){
	  if( xy[i][rx] == 1 ) {
	    count++;
	    xy[i][rx] = 0;
	  }
	}
	ry = i-1;
      }
      else if( dir == 'S' ){
	for(i=ry;i>=ry-step;i--){
	  if( xy[i][rx] == 1 ) {
	    count++;
	    xy[i][rx] = 0;
	  }
	}
	ry = i+1;
      }
    }
    if( count == gems ){
      printf("Yes\n");
    }
    else{
      printf("No\n");

    }
  }
  return 0;
}

Measured memory_bytes: 1012
#include<stdio.h>
int sosuu(int);
int main(){
int n,i,cnt=0,j,x,z;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
z=sosuu(x);
if(z==1)cnt++;

  }
printf("%d\n",cnt);
 

  return 0;
}

int sosuu(int x){
int j,s;
if(x==2||x==3)return 1;
if(x>2&&x%2==0)return 0;
if(x>3&&x%2!=0){
for(j=3;j*j<=x;j+=2){
if(x%j==0){
return 0;


}

}
return 1;
}

}



Measured memory_bytes: 2128
#include <stdio.h>
#include <string.h>
#define Long 1000000
#define L 14

char hi[Long][L];
int change (char p);
long long getkey (char str[]);
long long m1(long long key);
long long m2(long long key);
int find (char str[]);
int insert(char str[]);

int main()
{
  int i,n;
  char str[L],nara[9];
  for(i=0;i<Long;i++)
    hi[i][0]='\0';
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s %s",nara,str);

    if(nara[0]=='i'){
      insert(str);
    }else{
      if ( find(str) ){
        printf("yes\n");
      }else{
        printf("no\n");
      }
    }
  }

  return 0;
}
int change (char p){   /*文字から数値*/
  if (p=='A')
    return 1;
  else if
    (p=='C')
    return 2;
  else if
    (p=='G')
    return 3;
  else if
    (p=='T')
    return 4;
  else return 0;
}

long long getkey (char str[]){
  long long i,q=1,gou=0;
  for(i=0;i<strlen(str);i++){
    gou += q*(change(str[i]));
    q *=5;
  }
   
  return gou;
}

long long m1(long long key){
  return key%Long;
}

long long m2(long long key){
  return 1 + (key%(Long-1));
}
  

int find (char str[]){
  long long i,m,cord;

  cord=getkey(str);//文字列から数値
  for(i=0;;i++){
    m=(m1(cord) +i*m2(cord))%Long;
    if(strcmp(hi[m],str)==0)
      return 1;
    else if (strlen(hi[m])==0)
      return 0;
  }
    
  return 0;
}

int insert(char str[]){
  long long key=getkey(str);
  long long i=1,hash=m1(key);

  while(1){
    if(hi[hash][0]=='\0'){
      strcpy(hi[hash],str);
      return hash;
    }
    if (strcmp(hi[hash], str) == 0)
      return hash;
    else{
      hash=m1(key)+i*m2(key);
      i++;
      hash%=Long;
    }
  }
}



Measured memory_bytes: 15464
#include<bits/stdc++.h>
  using namespace std;
const int N   = (int) 2e5 + 5;
int solve(int *a,int n){
        int mn = 1e9;
        int ans = 0;
        for(int i = 1; i<=n; i++){
            mn = min(mn,a[i]);
            if(a[i]<=mn) ans++;
        }
        return ans;

}
int  main()
{
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

     int t=1, n;
     //cin >> t;
     while(t--)
     {
         int a[N]; cin >> n;
        for(int i  = 1; i<=n; i++){
            cin >> a[i];
        }
        cout<<solve(a,n)<<'\n';
     }



    return 0;
}


Measured memory_bytes: 1024