akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as C8

type Pair = (Int, Int)

main :: IO ()
main = do
  [n,m] <- readInts
  ps <- replicateM n readPair
  print $ solve m $ sortOn fst ps
 
solve :: Int -> [Pair] -> Int
solve m = fst . foldl' f e
  where
    e = (0,0)
    f (!s,!n) (a,b)
      | n == m = (s,n)
      | n+b > m = until ((m==).snd) (\(!s,!n) -> (s+a,n+1)) (s,n)
      | otherwise = (s+a*b, n+b)

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

readPair :: IO Pair
readPair = do
  [x,y] <- readInts
  return (x,y)

Measured memory_bytes: 56700
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  long a, b, c;
  cin >> a >> b >> c;
  if (a == b and b == c) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import math
import pprint
import fractions
import collections
import itertools
from decimal import *
from collections import deque
from bisect import *
N=int(input())
A=list(map(int,input().split()))
cuml=[0]*N
p=10**9+7
for i in range(N-1):
    cuml[i+1]=(cuml[i]+A[i])%p
#print(cuml)
ans=0
for i in range(N):
    ans=(ans+A[i]*cuml[i])%p
print(ans)



Measured memory_bytes: 98684
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n = int(input())
    ans, m = "", 1
    while n != 0:
        m *= (-2)
        if abs(n) % abs(m) > 0:
            ans += "1"
            n -= m // (-2)
        else:
            ans += "0"
    print(ans[::-1] if ans else 0)

if __name__=="__main__":
    solve()

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

int main() {
    int a, b, m;
    cin >> a >> b >> m;
    
    vector<int> vec_a(a);
    vector<int> vec_b(b);
    
    rep(i, a) cin >> vec_a.at(i);
    rep(i, b) cin >> vec_b.at(i);
    
    int min_a = vec_a.at(0);
    int min_b = vec_b.at(0);
    rep(i, a) {
        if (min_a > vec_a.at(i)) min_a = vec_a.at(i);
    }
    rep(i, b) {
        if (min_b > vec_b.at(i)) min_b = vec_b.at(i);
    }
    int min_total = min_a + min_b;
    
    int x, y, c;
    rep(i, m) {
        cin >> x >> y >> c;
        if (min_total > vec_a.at(x - 1) + vec_b.at(y - 1) - c) min_total = vec_a.at(x - 1) + vec_b.at(y - 1) - c;
    }
    
    cout << min_total << endl;
}

Measured memory_bytes: 1024
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */

    int a = sc.nextInt();
    int b = sc.nextInt();

    int t = sc.nextInt();

    os.println(t/ a * b);
  }
}

Measured memory_bytes: 22740
#include <stdio.h>

int main(void){
    long a,b,c,d,tmp,ans;
    while(scanf("%ld%ld",&a,&b)!=EOF){
        c=a;
        d=b;
        while(1){
            tmp=a%b;
            if(tmp==0){
                ans=b;
                break;
            }
            a=b;
            b=tmp;
        }
        printf("%ld %ld\n",ans,c*d/ans);
    }
    return 0;
}

Measured memory_bytes: 596
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define res(i,n) for(int i=n;;i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REV(i,n) for(int i=n-1;i>0;i--)
#define req(i,n,m) for(int i=n;i<m;i++)
#define REQ(i,n,m,l) for(int i=n;i<m;i+=l) 
#define _GLIBCXX_DEBUG
int INF = 1e9 + 7;
long double PI = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998626034825342117;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
    unsigned day;
    if (dow < dow1) dow += 7;
    day = dow - dow1;
    day += 7 * n - 6;
    return day;
}
signed gcd(long long x, long long y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
signed lcm(long long x, long long y) {
    return x / gcd(x, y) * y;
}
unsigned DayToWeekNumber(unsigned day)
{
    return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
    return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
int main() {
    int A; cin >> A;
    int a = A / 1000;
    int b = A % 1000 / 100;
    int c = A % 100 / 10;
    int d = A % 10;
    if (a + b + c + d == 7) { cout << a << '+' << b << '+' << c << '+' << d << "=7" << endl; return 0; }
    if (a + b + c - d == 7) { cout << a << '+' << b << '+' << c << '-' << d << "=7" << endl; return 0; }
    if (a + b - c + d == 7) { cout << a << '+' << b << '-' << c << '+' << d << "=7" << endl; return 0; }
    if (a + b - c - d == 7) { cout << a << '+' << b << '-' << c << '-' << d << "=7" << endl; return 0; }
    if (a - b + c + d == 7) { cout << a << '-' << b << '+' << c << '+' << d << "=7" << endl; return 0; }
    if (a - b + c - d == 7) { cout << a << '-' << b << '+' << c << '-' << d << "=7" << endl; return 0; }
    if (a - b - c + d == 7) { cout << a << '-' << b << '-' << c << '+' << d << "=7" << endl; return 0; }
    if (a - b - c - d == 7) { cout << a << '-' << b << '-' << c << '-' << d << "=7" << endl; return 0; }
}

Measured memory_bytes: 3608
#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 int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define _GLIBCXX_DEBUG
const int INF=1e18;

signed main(){
  	char a,b,c,d,e,f;cin>>a>>b>>c>>d>>e>>f;
      if(a==f&&b==e&&c==d)cout<<"YES"<<endl;
      else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
# Input acceptance
import sys

file_input = sys.stdin

V, E, r = map(int, file_input.readline().split())

edges = []

for line in file_input:
    edges.append(tuple(map(int, line.split())))


# Bellman???Ford algorithm
distance = [float("inf")] * V
distance[r] = 0

for i in range(V):
    notUpdated = True
    for e in edges:
        t = e[1]
        temp_d = distance[e[0]] + e[2]
        if temp_d < distance[t]:
            distance[t] = temp_d
            notUpdated = False
    if notUpdated:
        break


# Output
if i == V - 1 and V != 1:
    print("NEGATIVE CYCLE")
else:
    print(*map(lambda x: str(x).upper(), distance), sep = '\n')

Measured memory_bytes: 8256
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long int
#define phi 1.6180339
#define rep(i,n) for(auto i=0;i<(n);i++)
#define endl "\n"
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define op1 cin.tie(NULL)
#define op2 cout.tie(NULL)
#define op3 std::ios_base::sync_with_stdio(false)
#define MAXX 200005
using namespace std;
vector<int> edges[MAXX];
bool visited[MAXX];
int cnt=0;
void dfs(int sv)
{
  visited[sv]=true;
  cnt++;
  for(auto i:edges[sv]) if(!visited[i]) dfs(i);
}
void trozen()
{
  int n,m;
  cin>>n>>m;
  rep(i,n+1) visited[i]=false;
  rep(i,m)
  {
    int u,v;
    cin>>u>>v;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  int ans=0;
  rep(i,n) if(!visited[i+1]){cnt=0; dfs(i+1);ans=max(ans,cnt);}
  cout<<ans<<endl;
}
int32_t main()
{
    op1;op2;op3;
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    trozen();
    return 0;
}


Measured memory_bytes: 21000
s = input()

first = int(s[0:2])
second = int(s[2:4])

if first >= 1 and first <= 12:
  if second >= 1 and second <= 12:
    print('AMBIGUOUS')
  else:
    print('MMYY')
elif second >= 1 and second <= 12:
  print('YYMM')
else:
  print('NA')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int ll;

const int N = 2e5 + 10;
vector<int> adjList[N];
int h[N];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n , m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> h[i];
	while (m--) {
		int x, y;
		cin >> x >> y;
		adjList[x].pb(y);
		adjList[y].pb(x);
	}
	int ct = 0;
	for (int i = 1; i <= n; ++i) {
		bool flag = true;
		for (auto x : adjList[i]) {
			if (h[i] <= h[x]) {
				flag = false;
			}
		}
		if (flag) ++ct;
	}
	cout << ct << "\n";
}



Measured memory_bytes: 11472
n = int(input())
dic = {}
for i in range(n):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1
    
tmp = sorted(dic.items(), key=lambda x:x[0])
tmp = sorted(tmp, key=lambda x:x[1], reverse=True)
for i in range(len(tmp)):
  if tmp[i][1] == tmp[0][1]:
    print(tmp[i][0])
  else:
    break

Measured memory_bytes: 46684
#include <iostream>

#define int long long
using namespace std;

int32_t main()
{
  int n; cin>>n;
  int arr[n];
  for(int i = 0; i < n; i++) cin>>arr[i];
  int flag = 1;
  int mn = 999999999999;//_MAX;
  for (int i = n - 1; i >= 0; i--)
  {
	  mn = min(mn,arr[i]);
	  if(arr[i] - mn > 1)
	  {
		  flag = 0;
		  break;
	  }
  }
  cout<<(flag == 0 ? "No": "Yes");
  return 0;
}


Measured memory_bytes: 1024
/**In the name of Allah, the Most Merciful, the Most Merciful.**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 9223372036854775806
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define PI 2*acos(0.0)
#define EPS 1e-9
ll max(ll a,ll b) {if(a>b) return a; else return b;}
ll min(ll a,ll b) {if(a<b) return a; else return b;}

int main()
{
    int n;
    cin>>n;
    int a[n+1],b[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    bool check=false;
    for(int i=1;i<=n-2;i++){
        if(a[i]==b[i] && a[i+1]==b[i+1] && a[i+2]==b[i+2]){
            check=true; break;
        }
    }
    if(check) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}




Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long
#define fs first
#define sec second
#define md 1000000007
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
using namespace std;
ll power(ll x, unsigned ll y, ll p)  
{  
    ll res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p  
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  

ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2, p); 
}
vector<ll> par(200001,0);
vector<ll> sz(200001,1);
void func(){
    for(ll i=0;i<200001;i++){
        par[i]=i;
    }
}
ll find(ll a){
    if(par[a]==a) return a;
    return par[a]=find(par[a]);
}
void union_(ll a,ll b){
    a=find(a);
    b=find(b);
    if(a==b) return;
    if(sz[a]<sz[b]){
        par[b]=par[a];
        sz[a]+=sz[b];
    }
    else{
        par[a]=par[b];
        sz[b]+=sz[a];
    }
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll T=1;
    // cin>>T;
    while(T--){
    	ll n,m;
        cin>>n>>m;
        // vector<ll> par(n+1,0);
        func();
        for(ll i=0;i<m;i++){
            ll a,b;
            cin>>a>>b;
            union_(a,b);
        }
        ll ans=0;
        for(ll i=1;i<=n;i++){
            ll x=find(i);
        }
        for(ll i=1;i<=n;i++){
            // cout<<sz[i]<<" ";
            ans=max(ans,sz[i]);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 9436
#include<bits/stdc++.h>
  using namespace std;
   
  #define ll long long
  #define pb push_back
  #define mp make_pair
  #define ff first
  #define ss second


   
void func(){

ll n,m;
cin>>n>>m;

ll ans = n*(n-1)/2 + m*(m-1)/2;
cout<<ans<<endl;

  }
   
   
  int main(){
          ios_base::sync_with_stdio(false);
          cin.tie(0);
          cout.tie(0);
   
       /* #ifndef ONLINE_JUDGE
        freopen("input.txt", "r" , stdin);
        freopen("output.txt", "w" , stdout);
        #endif*/
   
     ll t=1;
     //cin>>t;
     while(t--)
     func();
   }

Measured memory_bytes: 256
$n=<>;
$d[1]=1;
for$i(@n=2..$n){
	$p[$i]&&next;
	@p[map$i*$_,@n]=@n;
	$c=map{grep$'%$i**$_<1,//..9}@n;
	map$d[-$'*++$_]+=$d[-$'],//..$c for-75..-1
}
print$d[75]||0

Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <typeinfo>
#define _USE_MATH_DEFINES
#include <cmath>
#include <stack>

using namespace std;


int main(){

    stack<string> stk;
    string str;
    while(cin >> str){
        if(str=="+" || str=="-" || str=="*"){
            int b = stoi(stk.top()); stk.pop();
            int a = stoi(stk.top()); stk.pop();
            if(str == "+"){
                stk.push(to_string(a+b));
            }else if(str=="-"){
                stk.push(to_string(a-b));
            }else if(str=="*"){
                stk.push(to_string(a*b));
            }
        }else{
            stk.push(str);
        }
        if(getchar()=='\n'){
            cout << stk.top() << endl;
            return 0;
        }
    }

    return 0;
}



Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int a,b; cin >> a >> b;
    if((a == 1 && b == 2 )||(a == 2 && b == 1)) cout << 3 << endl;
    if((a == 1 && b == 3 )||(a == 3 && b == 1)) cout << 2 << endl;
    if((a == 2 && b == 3 )||(a == 3 && b == 2)) cout << 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define K 1000000007
//#define x first
//#define y second
using namespace std;
ll fact[2001];
ll invfact[2001];
ll power(ll x, ll y, ll m) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
  
    return (y%2 == 0)? p : (x * p) % m; 
} 
ll inverseMod(ll a)
{
    return power(a,K-2,K);
}
ll c(ll n, ll r)
{
    if(n<r)return 0;
    if(n<0||r<0)return 0;
    ll ans= ( ( fact[n]* invfact[n-r])%K *invfact[r] )%K;
    return ans;
}
int main() {
	/*ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    */
    fact[0]=1;
    invfact[0]=inverseMod(fact[0]);
    
    for(int i=1;i<2001;i++){
        fact[i]=(fact[i-1]*i)%K;
        invfact[i]=(invfact[i-1]*inverseMod(i))%K;
       // cout<<(fact[i]*invfact[i] )%K<<endl;
    }
    
    ll s;
    cin>>s;
    
    ll maxN=s/3LL;
    ll ans=0;
    for(ll i=1LL;i<=maxN;i++)
    {
        ll n=s-(3LL*i);
        ans= (ans+c(n+i-1LL,i-1LL))%K;
    }
    cout<<(ans+K)%K<<endl;
    
	return 0;
}


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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 人数
		int N = sc.nextInt();
		// ポイント
		int K = sc.nextInt();
		// 正解数
		int Q = sc.nextInt();
		// 正解した参加者
		int A[] = new int[Q];
		for (int i = 0; i < Q; i++) {
			A[i] = sc.nextInt();
		}

		// 参加者の得点
		int X[] = new int[N];
		Arrays.fill(X, K - Q);

		for (int i = 0; i < Q; i++) {
			X[A[i] - 1] = X[A[i] - 1] + 1;
		}


		for (int i = 0; i < N; i++) {
			if (X[i] <= 0) {
				System.out.println("No");
			} else {
				System.out.println("Yes");
			}
		}
	}
}


Measured memory_bytes: 64780
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn=new Scanner(System.in);
		char ch = scn.next().charAt(0);
		if(ch>=65 && ch<=91){
			System.out.println("A");
		}else{
			System.out.println('a');
		}
				

	}

}

Measured memory_bytes: 35640
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n;
string s;
multiset<string> mst;
set<string> st;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		sort(s.begin(), s.end());
		mst.insert(s);
		st.insert(s);
	}
	long long ans = 0;
	for (auto x : st) {
		int tmp = mst.count(x);
		ans += tmp * 1LL * (tmp - 1) / 2;
	}
	cout << ans << E;
	//system("pause");
	return 0;
}

Measured memory_bytes: 19072
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using graph = vector<vector<int>>;
using wgraph = vector<vector<pair<int, lint>>>;
const lint INF = 1001001001001001LL;
const lint MOD = 1000000007LL;
int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

void yes(){ cout << "yes" << endl; }
void Yes(){ cout << "Yes" << endl; }
void YES(){ cout << "YES" << endl; }
void no(){ cout << "no" << endl; }
void No(){ cout << "No" << endl; }
void NO(){ cout << "NO" << endl; }
void possible(){ cout << "possible" << endl; }
void Possible(){ cout << "Possible" << endl; }
void POSSIBLE(){ cout << "POSSIBLE" << endl; }
void impossible(){ cout << "impossible" << endl; }
void Impossible(){ cout << "Impossible" << endl; }
void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define drep(i,n) for(int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(int i = s; i < t; i++)
#define all(a) a.begin(),a.end()

int main(){
  
  lint n; cin >> n;
  vector<double> a(n);
  rep(i, n) cin >> a[i];
  double u = 1.0;
  double s = 0.0;
  rep(i, n){
    s += 1.0 / a[i];
  }
  double ans = u / s;
  printf("%.10f\n", ans);
  return 0;
}


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

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;



int main(){
  ll n, k;
  cin >> n >> k;
  ll a[n];
  REP(i,n)cin >> a[i];

  bool dp1[n+1][k+1];
  // bool dp2[n+1][k+1];

  sort(a,a+n);

  int lb = -1, ub = lower_bound(a, a+n, k) - a;
  while(ub - lb > 1){
    int mid = (ub + lb) / 2;
    REP(i,n+1)REP(j,k+1){
      dp1[i][j] = false;
      // dp2[i][j] = true;
    }
    dp1[0][0] = true;
    // dp2[0][0] = true;

    REP(i,n){
      REP(j,k+1){
        if(i == mid){
          dp1[i+1][j] = dp1[i][j];
        }else{
          dp1[i+1][j] = dp1[i][j];
          if(j >= a[i] && dp1[i][j-a[i]]) dp1[i+1][j] = true;
        }
        // dp2[i+1][j] = dp1[i][j];
        // if(j >= a[n-1-i] || dp2[i][j - a[n-1-i]]) dp2[i+1][j] = true;
      }
    }

    // if(mid == 0){
    //   REP(i,n+1){
    //     REP(j,k+1){
    //       cout << "dp" << i << j << " : " << dp1[i][j] << ",";
    //     }
    //     cout << endl;
    //   }
    // }

    bool flag = false;
    REP(i,a[mid]){
      if(dp1[n][k-1-i])flag = true;
      // if(mid == 0)cout << "yes " <<  i << endl;
    }
    if(flag)ub = mid;
    else lb = mid;

    // cout << mid << endl;
  }

  cout << lb + 1 << endl;


  return 0;
}


Measured memory_bytes: 24704
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner stdin = new Scanner(System.in);
    int a = stdin.nextInt();
    int b = stdin.nextInt();
    if (a < b) {
      System.out.println("a < b");
    } else if (a > b) {
      System.out.println("a > b");
    } else {
      System.out.println("a == b");
    }
  }

}

Measured memory_bytes: 17300
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    while (A > 0 and C > 0)
    {
        C -= B;
        if (C <= 0)
        {
            cout << "Yes";
            return 0;
        }
        A -= D;
        if (A <= 0)
        {
            cout << "No";
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

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

    int r = 0;
    for (int i = 0; i < b; i++) {
        if ((a * i) % b == c) r = 1;
    }

    cout << (r ? "YES" : "NO") << endl;

    return 0;
}

Measured memory_bytes: 256
N, M = [int(x) for x in input().split()]
KL = [[int(x) for x in input().split()] for _ in range(N)]


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


u = UnionFind(N + M)

for i, (kl) in enumerate(KL):
    for j, k in enumerate(kl):
        if j == 0:
            continue
        u.union(i, k + N - 1)

v = set()
for i in range(N):
    v.add(u.find(i))

if len(v) == 1:
    print("YES")
else:
    print("NO")












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

int main() {
  int N,M;
  cin >> N >> M;
  vector<int> a(M),b(M),count(N);
  for(int i=0;i<M;i++){
    cin >> a.at(i) >> b.at(i);
    count.at(a.at(i)-1)++;
    count.at(b.at(i)-1)++;
  }
  for(int i=0;i<N;i++){
    cout << count.at(i) << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int comb(int n, int r){
	int res = 1;
	for(int i = 1; i <= r; i++){
		res *= (n - i + 1);
		res /= i;
	}
	return res;
}
int main(){
	int N, P;
	int A;
	scanf("%d %d", &N, &P);
	int odd = 0, even = 0;
	for(int i = 0; i < N; i++){
		scanf("%d", &A);
		if(A % 2 == 0) even++;
		else if(A % 2 == 1) odd++;
	}
	long long int ans = 1;
	for(int i = 1; i <= even; i++) ans *= 2;
	long long  permutation_odd = 0;
	if(P == 0){
		for(int i = 0; i <= odd; i += 2){
			permutation_odd += comb(odd, i);
		}
	}else{
		for(int i = 1; i <= odd; i += 2){
			permutation_odd += comb(odd, i);
		}
	}
	printf("%lld\n", ans * permutation_odd);
	return 0;
}


Measured memory_bytes: 256
def is_two_equal s
  
  sl = s.length
  return false if sl % 2 == 1 
  k = sl/2
  s[0,k] == s[k,k]
end

s = gets.chomp

sl = s.length

while not sl.nil? do
  
  s.chop!
  break if is_two_equal s
end
  
puts s.length

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

#define ll long long
#define mod 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)


int main()
{
	float x,y;
	cin>>x>>y;
	cout<<(float)x/y<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	
	int i,n,k;
	double dice[200001];
	double sum =0, max = 0;
	int a;
	
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&a);
		dice[i] = (a+1.0)/2;
		sum = sum + dice[i];
		if(i>=k)
			sum = sum - dice[i-k];
		if(max<sum)
			max = sum;
			
		
	}
	printf("%.12f",max);
	return 0;
}


Measured memory_bytes: 1664
import math
N = int(input())
ans = [0] * (N+1)
search = int(math.sqrt(N))+1

for x in range(1 , search):
  for y in range(1 , search):
    for z in range(1 , search):
      con = x*(x + y + z) + y*y + z*z + y*z
      if con <= N:
        ans[con] += 1
      else:
        break

for a in range(1,N+1):
  print(ans[a])
        

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vll a(n);
    rep(i,n) cin>>a[i];
    ll l=-1e10,r=1e10;
    while(r-l>2){
        ll c1 = (l*2+r)/3;
        ll c2 = (l+r*2)/3;
        ll s1=0, s2=0;
        rep(i,n) s1+=abs(a[i]-(c1+i+1));
        rep(i,n) s2+=abs(a[i]-(c2+i+1));
        if (s1<s2){
            r = c2;
        }else{
            l = c1;
        }
    }
    ll b = (l+r)/2;
    ll ans=0;
    rep(i,n) ans+=abs(a[i]-(b+i+1));
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

s = input()
l = [ 'SUN','MON','TUE','WED','THU','FRI','SAT']
print(7 - l.index(s))



Measured memory_bytes: 74816
#include<bits/stdc++.h>
using namespace std;
int p[109];

int main() {
    int x, n;
    cin >> x >> n;

    set< int >st;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        st.insert(p[i]);
    }
    for (int d = 0; ; d++) {
        if (st.count(x-d)==0) {
            cout << x-d << endl;
            return 0;
        } else if (st.count(x+d)==0) {
            cout << x+d << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 3636
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)
def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]

def nck(n, k, mod=10**9+7):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod

N,K=zz()
ans = 0
modK = 0
if (K % 2 == 0):
    mod0 = N//K
    ans += mod0**3
    a = (N + K//2)//K
    # print(a)
    ans+=a**3
else:
    mod0 = N // K
    ans=mod0**3
print(ans)

Measured memory_bytes: 27080
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

//  https://atcoder.jp/contests/abc150/tasks/abc150_c

int factori(int a) {
    if (a < 2) {
        return 1;
    }
    return a * factori(a - 1);
}

int factorial(int a) {
    if (a == 0)
        return 0;
    if (a == 1)
        return 1;
    return factori(a);
}

int calcPos(int N, int* Array) {
    bool* used = new bool[N];
    for (int i = 0; i < N; ++i) {
        used[i] = 0;
    }
    int count = 1;
    int nextsmall = 1;
    for (int i = 0; i < N; ++i) {
        int numSmaller = 0;
        for (int j = 0; j < Array[i] - 1; ++j) {
            if (!used[j] ){
                ++numSmaller;
            }
        }
        count += factorial(N - i - 1) * numSmaller;
        used[Array[i] - 1] = 1;
        if (Array[i] == nextsmall) {
            nextsmall += 1;
        }
    }
    return count;
}

int main() {
    int N;
    cin >> N;
    int* A = new int[N];
    int* B = new int[N];
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }
    int Apos = calcPos(N, A);
    int Bpos = calcPos(N, B);
    cout << abs((Apos - Bpos));
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
 
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
 
 
 
ll n, m, k, q, l, r, x, y, z;
const ll template_array_size = 1e6 + 1389;
ll a[template_array_size];
ll b[template_array_size];
ll c[template_array_size];
string s, t;
ll ans = 0;
 

 
void solve(int tc = 0) {
	ll a, b, c, d; cin >> a >> b >> c >> d;
	
	cout << max({a * c, a * d, b * c, b * d}) << '\n';
}
 
int main() {
	#ifdef galen_colin_local
		auto begin = std::chrono::high_resolution_clock::now();
	#endif
	
	send help
 
	#ifndef galen_colin_local
		// usaco("moop");
	#endif
	
	// usaco("cowland");
	
	// freopen("tc.cpp", "r", stdin);
 
	int tc = 1;
	// cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
	
	#ifdef galen_colin_local
		auto end = std::chrono::high_resolution_clock::now();
		cout << setprecision(4) << fixed;
		// cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
	#endif
} 

Measured memory_bytes: 3672
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    cin >> n>> m;
    int x[3] = {}, y[3] = {}, z=0;
    for (int i = 0; i < m;++i) {
        int b, c;
        cin >> b >> c;
        if ((y[b - 1] != 0 && x[b - 1] != c) || (b == 1 && c == 0 && n!=1)) {
            z += 1;
            break;
        }
        else {
            x[b - 1] = c;
            y[b - 1] += 1;
        }
    }
    if (x[0] == 0 && n != 1) x[0] = 1;
    if (z == 0) {
        if (n == 3) cout << 100 * x[0] + 10 * x[1] + x[2] << endl;
        else if (n == 2) cout << 10 * x[0] + x[1] << endl;
        else if (n == 1) cout << x[0] << endl;
    }
    else cout << -1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;
using int32 = __uint32_t;

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

    vector<int> v(n);
    for(int i = 0; i  < n; i++)cin >> v[i];

    int ans = 0;
    for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n;j++){
        ans += v[i] * v[j];
    }
    cout << ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


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

using namespace std;

#define int long long
#define pii pair < ll, ll >
#define fr first
#define sc second

const int N = 2e5 + 7;
const double pi = 3.1415926535897932;
const int inf = (int)1e9 + 7;
int gr = (int)1e8 - 1;

struct point {
  int x, y;
  point() {}
  point(int a, int b) {
    x = a; y = b;
  }
};

void swap(point &a, point &b) {
  int temp = a.x;
  a.x = b.x;
  b.x = temp;
  temp = a.y;
  a.y = b.y;
  b.y = temp;
}

bool cmp (point a, point b) {
  return a.x < b.x;
}

double ans = 0;

void printans() {
  cout << fixed << setprecision(12) << ans << endl;
  exit(0);
}

point p1, p2;
point ar[N];
int dp[N];

main() {
  int a, b; scanf("%lld %lld", &a, &b);
  p1 = point(a, b);
  scanf("%lld %lld", &a, &b);
  p2 = point(a, b);
  int n; scanf("%lld", &n);
  if (p1.x > p2.x) swap(p1, p2);
  for (int i = 1; i <= n; i++) {
    scanf("%lld %lld", &a, &b);
    if (a < min(p1.x, p2.x) || a > max(p2.x, p1.x) || b < min(p1.y, p2.y) || b > max(p1.y, p2.y)) {
      n--;
      i--;
    } else
      ar[i] = point(a, b);
  }
  if (p1.y > p2.y) {
    for (int i = 1; i <= n; i++) {
      ar[i].x = gr - ar[i].x;
    }
    p1.x = gr - p1.x;
    p2.x = gr - p2.x;
    swap(p1, p2);
  }
  sort(ar + 1, ar + n + 1, cmp);
  for (int i = 0; i < N; i++)  {
    dp[i] = inf;
  }
  dp[0] = -inf;
  int val = 0;
  for (int i = 1; i <= n; i++) {
    int pos = lower_bound(dp, dp + N, ar[i].y) - dp;
    dp[pos] = ar[i].y;
  }
  val = N - 1;
  while (dp[val] == inf) val--;
  ans = 100 * (abs(p2.x - p1.x) + abs(p2.y - p1.y)) - 20 * val + val * pi * 5;
//  cout << 100 * (abs(p2.x - p1.x) + abs(p2.y - p1.y)) << endl;
  if (val == 0) {
    ans = 100 * (abs(p2.x - p1.x) + abs(p2.y - p1.y));
  }
  if (val == min(abs(p2.x - p1.x), abs(p2.y - p1.y)) + 1) {
    ans += pi * 5;
  }
  printans();
}


Measured memory_bytes: 4992
#include<stdio.h>

int main(){
  int n,k;
  char s[11];

  scanf("%d",&n);
  scanf("%s",s);
  scanf("%d",&k);
  
  char a=s[k-1];
  int i;
  for(i=0;i<n;i++){
    if(s[i]!=a)
      printf("*");
    else
      printf("%c",s[i]);
  }
}


Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

typedef unsigned long long ULL;
static ULL N;
static char s[100001];
static char o[100001];

void print() {
   for(ULL i = 1; i <= N; i++) {
       printf("%c", o[i]);
   }
}

int check(char *s, char x, char y) {
    o[1] = x;//first
    o[0] = y;//last
    
    for(ULL i = 1; i <= N; i++) {
        if(o[i] == 'S') {
            o[i+1] = (s[i-1] == 'o' ? o[i-1] : (o[i-1] == 'W' ? 'S' : 'W'));
        } else {
            o[i+1] = (s[i-1] == 'o' ? (o[i-1] == 'W' ? 'S' : 'W') : o[i-1]);
        }
    }
    //o[N] == o0, o1==oN+1
    return o[0] == o[N] && o[1] == o[N+1];
}

int main(int argc, const char * argv[]) {
    
    scanf("%llu%s", &N, s);
    if(N < 3 || N > 100000) {
        return 1;
    }
    
    if(check(s, 'S', 'S')) {
        print();
    } else if(check(s, 'S', 'W')) {
        print();
    } else if(check(s, 'W', 'W')) {
        print();
    } else if(check(s, 'W', 'S')) {
        print();
    } else {
        printf("-1");
    }

    printf("\n");
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}

template <class T>
void read(T &x) {
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        ;
    for (x = 0; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + (c & 15);
}
#define ll long long 
#define lll __int128_t
#define pb push_back
#define mp make_pair
typedef pair < int,int> ii;
typedef vector<ii> vii;
typedef vector<ll>vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll i, j, k, l, n, m;
    cin >> n;
    vector<ll> Data(n + 1);
    map<ll, ll> mp1;
    for (i = 1; i <= n;i++){
        cin >> Data[i];
    }
    ll ans = 0;
    for (i = 1; i <= n;i++){
        ans += (mp1[i - Data[i]]);
        mp1[i + Data[i]]++;
    }
    cout << ans << "\n";
    return 0;
}

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

void solve()
{
	ll n;
	cin>>n;
	ll a[n];
	ll sum = 0;
	map<ll,ll> m;
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
		sum += a[i];
		m[a[i]]++;
	}
	ll q;
	cin>>q;
	for (int i = 0; i < q; ++i)
	{
		ll b,c;
		cin>>b>>c;
		sum += (c-b)*m[b];
		m[c] += m[b];
		m[b] = 0;
		cout<<sum<<endl;
	}

}	

int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}

Measured memory_bytes: 10204
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n;
  cin >> n;
  int m;
  cin >> m;
  rep(i,m){
    int y;
    cin >> y;
    n-=y;
    //cout << n << endl;
  }
  if(n<0)cout << -1 << endl;
  else cout << n << endl;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
ll x,ans;
int main(){
	ios::sync_with_stdio(0);
	cin>>x;
	ans=x/500*1000;
	x%=500;
	x-=x%5;
	cout<<ans+x;
	re 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const ll INF = 1 << 30;//10^9
//ll MOD = 1000000007;
ll MOD = 998244353;

vector<ll> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};

void pres(double A, ll x = 20){cout << fixed << setprecision(x) << A << endl;}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
//ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

ll lcm(ll x, ll y){
  ll res = x / gcd(x, y);
  res *= y;
  return res;
};


string S;
ll K;
ll dp[110][2][4];
void solve(){
  cin >> S >> K;
  dp[0][0][0] = 1;
  rep(i, S.size())rep(j ,2)rep(k, 4){
    //0が出る
    if(S[i] - '0' == 0) dp[i+1][j][k] += dp[i][j][k];
    else dp[i+1][1][k] += dp[i][j][k];
    //0以外が出る
    for(ll l = 1; l <= 9; l++){
      if(l > S[i] - '0'){
        if(j == 0) continue;
        if(k == 3) continue;
        dp[i+1][j][k+1] += dp[i][j][k];
      }else if(l == S[i] - '0'){
        if(k == 3) continue;
        dp[i+1][j][k+1] += dp[i][j][k];
      }else{
        if(k == 3) continue;
        dp[i+1][1][k+1] += dp[i][j][k];
      }
    }
  }
  cout << dp[S.size()][0][K] + dp[S.size()][1][K] << endl;
}

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


Measured memory_bytes: 256
N, M = map(int, input().split())
LN, RN = 0, N
for _ in range(M):
    L, R = map(int, input().split())
    LN = max(LN, L)
    RN = min(RN, R)
ans = RN - LN + 1
if ans < 0:
    ans = 0
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';


template<typename V>
V compress(V v){
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  return v;
}
template<typename T>
map<T, Int> dict(const vector<T> &v){
  map<T, Int> res;
  for(Int i=0;i<(Int)v.size();i++)
    res[v[i]]=i;
  return res;
}
map<char, Int> dict(const string &v){
  return dict(vector<char>(v.begin(),v.end()));
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n;
  cin>>n;

  vector<Int> cand;
  for(Int i=1;i*i<=n;i++){
    if(n%i==0){
      cand.emplace_back(i);
      cand.emplace_back(n/i);
    }
    if((n-1)%i==0){
      cand.emplace_back(i);
      cand.emplace_back((n-1)/i);
    }
  }

  cand=compress(cand);
  Int ans=0;
  for(Int k:cand){
    if(k<2 or k>n) continue;
    Int tmp=n;
    while(tmp%k==0) tmp/=k;
    tmp%=k;
    ans+=tmp==1;
  }

  cout<<ans<<newl;
  return 0;
}


Measured memory_bytes: 384
def mxciToDegit(s):
  dict = {'m': 1000, 'c': 100, 'x': 10, 'i': 1}
  sum = 0
  for c in dict:
    if c in s:
      if "2" <= s[s.index(c)-1] <= "9":
        sum += int(s[s.index(c)-1])*dict[c]
      else:
        sum += dict[c]
  return sum

n = int(raw_input())
for i in range(n):
  a, b = raw_input().split()
  sum = mxciToDegit(a) + mxciToDegit(b)

  st = ""
  list =((1000, "m"), (100, "c"), (10, "x"), (1, "i"))
  for d, c in list:
    val = sum/d
    if val >= 2:
      st += str(val) + c
    elif val == 1:
      st += c
    sum = sum%d
  print st

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

int main(){
  int a;
  cin >> a;
  int b[a];
  for(int i=0;i<a ;i++ ){
    cin >> b[i];
  }
  
  int min=b[0],max=b[1];
  for(int i=0;i<a; i++){
   if(b[i] < min){
     min = b[i];
   }
    if(b[i] > max){
     max = b[i];
   }
  }
  
  int dif = abs(max - min);
  cout << dif << endl;
  
}

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

using namespace std;

const int N = 450;

long long int dp[N][N], a[N], pr[N][N];

int main () {
    memset(dp,63,sizeof(dp));
    long long int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++ ) cin >> a[i], dp[i][i]=0;
    for(int i = 0 ; i < n ; i++ ) {
        for(int j = i ; j < n ; j++ ) {
            for(int k = i ; k <= j ; k++ ) {
                pr[i][j]+=a[k];
            }
        }
    }
    for(int d = 1 ; d < n ; d++ ) {
        for(int i = 0 ; i + d < n ; i ++ ) {
            int j = i + d;
            for(int k = i ; k < j ; k++ ) {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+pr[i][k]+pr[k+1][j]);
            }
        }
    }
    cout << dp[0][n-1];
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
#define allsort(X) sort(X.begin(),X.end())

typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;





ll i,j,k;


int main(){
    ll N;
    cin>>N;
    V A(N);
    rep(i,N)cin>>A[i];
    ll ans=0;

    rep(i,N)if(i%2==0&&A[i]%2==1)ans++;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 3584