akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

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

    int n;
    P a[112345];

    cin >> n;
    REP(i, n)
    {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a, a + n);

    int cnt = 0;
    REP(i, n)
    cnt += abs(i - a[i].second) % 2;

    cout << (cnt + 1) / 2 << endl;

    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

int main() {
    ll x, k, d; cin >> x >> k >> d;
    // 0をまたげない
    if ((double)abs(x) / d > k) {
        cout << abs(x) - k * d << endl;
        return 0;
    }
    // 0をまたげる
    ll used_times = floor((double)abs(x) / d);
    ll close_zero;
    if (x < 0) close_zero = x + used_times * d;
    else close_zero = x - used_times * d;
    ll remain_times = k - used_times;
    // cout << used_times << " " << close_zero << " " << remain_times << endl;
    if (remain_times % 2 == 0) {
        cout << abs(close_zero) << endl;
    }
    else {
        if (close_zero < 0) 
            cout << abs(close_zero + d) << endl;
        else 
            cout << abs(close_zero - d) << endl;
    }
}

Measured memory_bytes: 3724
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll n; cin >> n; ll x = (sqrt(n)+1)/1; ll ans = 0;
  
  for(ll i=x; i > 0; i--){
    if(n % i == 0){
      ans = i;
      break;
    }
  }
  
  cout << ans + (n/ans) - 2 << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main(void) {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int ans = 0;
  rep(i, n) { ans += a[i] - 1; }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3588
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
ans = "Yes"
tpre, xpre, ypre = 0, 0, 0
for _ in range(n):
    t, x, y = na()
    move = abs(x - xpre) + abs(y - ypre) 
    time = (t - tpre)
    if move <= time and move % 2 == time % 2:
        continue
    else:
        ans = "No"

    tpre, xpre, ypre = t, x, y
print(ans)

Measured memory_bytes: 3188
#include <iostream>
using namespace std;
int main(void){
  int K;
  cin >> K;
  int count = 0;
  for(int i = 1; i <= K; i += 2){
    for(int j = 2; j <= K; j += 2, count++){
    // NOP  
    }
  }
  cout << count << endl;
  
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  
  int ans = 0;
  while(true){
    for(int i = 0; i < n; i++){
      if(a[i] % 2 != 0){
        cout << ans << endl;
        return 0;
      }
    }
    for(int i = 0; i < n; i++){
      a[i] /= 2;
    }
    ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import scala.io.{StdIn => in}
import scala.collection.{mutable => mu}

object Main extends App {
  val INF = 2L << 40
  val Array(a, b, q) = in.readLine.split(" ").map(_.toInt)
  val sb = Iterator.continually(in.readLong)
    .take(a)
    .to[mu.ArrayBuffer]
  -INF +=: sb
  sb += INF
  val s = sb.toArray

  val tb = Iterator.continually(in.readLong)
    .take(b)
    .to[mu.ArrayBuffer]
  -INF +=: tb
  tb += INF
  val t = tb.toArray

  val maxS = s.size-1
  val maxT = t.size-1
  val out = new java.io.PrintWriter(System.out)
  Iterator.continually(in.readLong)
    .take(q)
    .foreach(x => {
      var dist = Long.MaxValue
      for {
        k <- 0 until 2
        arrA = if(k == 0) s else t
        arrB = if(k == 0) t else s
        i <- 0 until 2
        posA = math.min(binarySearch(arrA, x) + i, arrA.size-1)
        ax = arrA(posA)
        j <- 0 until 2
        posB = math.min(binarySearch(arrB, ax) + j, arrB.size-1)
        bx = arrB(posB)
      } {
        val a = ( x - ax).abs
        val b = (ax - bx).abs
        dist = math.min(dist, a + b)
      }
      out.println(dist)
    })
  out.flush

    def binarySearch(arr:Array[Long], x:Long):Int = {
    var left = 0
    var right = arr.size

    def loop(left:Int, right:Int):Int = {
      if(right - left < 2) left
      else {
        val mid = (left + right) / 2
        if(arr(mid) <= x) loop(mid,right)
        else loop(left, mid)
      }
    }
    loop(left, right)
  }
}

Measured memory_bytes: 125096
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,cnt=0,flag=0;
    double sum=0;
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    double chk=sum*((double)1/(4*m));
    for(int i=0;i<n;i++){
        if(a[i]>=chk){
            cnt++;
            if(cnt==m){
                flag=1;
                break;}
        }
    }
    //cout<<chk;
    if(flag)
        cout<<"Yes\n";
    else
        cout<<"No\n";
}

Measured memory_bytes: 3580
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define mod 1000000007 //1e9+7
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100000

int main(){
  int n,h;
  int d[SIZE],u[SIZE];
  
  scanf("%d%d",&n,&h);

  for(int i=0;i<n-1;i++){
    scanf("%d%d",d+i,u+i);

  }

  ll ans = 0;
  int l = 0;
  int power = h;
  ll powermemo[SIZE] = {};
  ll sum[SIZE] = {};
  ll now_sum = 0;
  
  priority_queue<pair<int,int> > pq;
  
  for(int i=0;i<n-1;i++){
    //cerr << i << " : " << power << endl;
    
    pq.push({u[i],i});
    powermemo[i] = power;

    while(power-d[i] <= 0){

      //cerr << "power" << " : " << power << endl;
      
      int max_add = 0;
      int max_l = 0;
      int add_ans = 0;
      bool back = false;
      pair<int,int> p,max_p;
      
      while(1){
	if(pq.empty()) break;
	
	p = pq.top();
	pq.pop();

	//cerr << "p = {" << p.first << " : " << p.second << "} " << pq.size() << endl;
	
	if(p.second < l) continue;
	
	if(h - (powermemo[p.second]+(now_sum + sum[p.second])) <= p.first){
	  
	  ll add = h - (powermemo[p.second]+(now_sum + sum[p.second]));

	  //cerr << h << "-(" << powermemo[p.second] << " + " << now_sum << " + " << sum[p.second] << ")" <<endl;
	  //cerr << "a = " << add << endl;
	  
	  if(max_add < add || (max_add == add && max_l < p.second)){
	    max_l = p.second;
	    max_add = add;
	    max_p = p;
	    add_ans = 1;
	    back = false;
	  }
	  
	}else{
	  
	  if(max_add > p.first){
	    pq.push(p);
	    break;
	  }
	  
	  ll t = h - (powermemo[p.second]+(now_sum + sum[p.second]));
	  
	  ll add = min(t/p.first * p.first,
		       (ll)((d[i]-power)/p.first + 1) * p.first);
	  
	  if(max_add < add ||  (max_add == add && max_l < p.second)){
	    max_l = p.second;
	    max_add = add;
	    max_p = p;
	    add_ans = add/p.first;
	    back = true;
	  }
	  
	  break;
	}
	
      } //while
      
      l = max_l;
      power += max_add;
      now_sum += max_add;
      sum[i] -= max_add;
      ans += add_ans;
      
      if(back) pq.push(max_p);
      
      //cerr << "add : " <<  max_add << " (" << add_ans << ")" << max_l << endl;
      assert(max_add>0);
      
      powermemo[i] = power;
    }
    
    
    sum[i+1] += sum[i];
    powermemo[i] = power;
    power -= d[i];
  }
  
  printf("%lld\n",ans);
  
  return 0;
}

Measured memory_bytes: 5568
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long ll;

int main()
{
	long double a,b;
	cin>>a>>b;
	cout<<(long long)(a*b)<<endl;
	return 0;
}



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

using namespace std;

int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int sum = 0;
    for (int i = 1; ; i++) {
        sum += i;
        if (sum >= n) {
            cout << i << "\n";
            return 0;
        }
    }
}


Measured memory_bytes: 256
import sys
import itertools

def get_ch_cnt(line):
    d = {}
    for ch in line:
        if ch in d:
            d[ch] += 1
        else:
            d[ch] = 1

    return d

def main():
    n = int(sys.stdin.readline())
    line = sys.stdin.readline().rstrip()

    ans_dic = get_ch_cnt(line)

    for line in sys.stdin:
        line = line.rstrip()

        ch_cnt = get_ch_cnt(line)

        for ch, cnt in ans_dic.items():
            if ch in ch_cnt:
                ans_dic[ch] = min(cnt, ch_cnt[ch])
            else:
                ans_dic[ch] = 0

    ans_ch_lst = []
    for ch,cnt in ans_dic.items():
        ans_ch_lst.extend(list(itertools.repeat(ch, cnt)))

    print("".join(sorted(ans_ch_lst)))
    return 0

if __name__ == '__main__':
    sys.exit(main())


Measured memory_bytes: 3064
/*
    author: Salam_35
    Created at :

*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define pb push_back
#define sc(n) scanf("%d",&n)
#define Max 100005
#define scan(n) scanf("%lld",&n)
#define pi acos(-1.0)
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ALL(x) x.begin(),x.end()
#define sci(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define load(array,size)  for(ll i=0 ; i<size ; i++) cin>>array[i] ;
#define load1(array,size)  for(ll i=1 ; i<=size ; i++) cin>>array[i] ;
#define INF	1LL<<19
#define pll pair<ll,ll>
#define mst(arr,value) memset(arr,value,sizeof(arr));


const ll MOD = 1e9+7;

typedef vector<ll>vec;
typedef pair<ll,ll> pii;
typedef map<ll,ll>mpll;
typedef set<ll>seet;
vec primes;


int main()
{
    int h,n;
    cin >> h >> n;
    if(h%n==0)cout<<h/n<<endl;
    else cout<<(h/n)+1<<endl;

}





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

using namespace std;

int main() {
    string s;
    cin >> s;
    vector<long> ch(s.size(), 0);
    bool now_r = true;
    long now_ch = 0;
    long old_cross_point_r;
    for (long i = 0; i < s.size(); ++i) {
        if (now_r) {
            ++now_ch;
            if (s[i+1] == 'L') {
                old_cross_point_r = i;
                if (now_ch%2==0) {
                    ch[i] += now_ch/2;
                    ch[i+1] += now_ch/2;
                } else {
                    ch[i] += now_ch/2+1;
                    ch[i+1] += now_ch/2;
                }
                now_ch = 0;
                now_r = false;
            }
        } else {
            ++now_ch;
            if (i == s.size()-1) {
                if (s[s.size()-2] == 'R') {
                    ++ch[s.size()-1];
                } else {
                    if (now_ch%2==0) {
                        ch[old_cross_point_r] += now_ch/2;
                        ch[old_cross_point_r+1] += now_ch/2;
                    } else {
                        ch[old_cross_point_r] += now_ch/2;
                        ch[old_cross_point_r+1] += now_ch/2+1;
                    }
                }
                break;
            }
            if (s[i+1] == 'R') {
                if (now_ch%2==0) {
                    ch[old_cross_point_r] += now_ch/2;
                    ch[old_cross_point_r+1] += now_ch/2;
                } else {
                    ch[old_cross_point_r] += now_ch/2;
                    ch[old_cross_point_r+1] += now_ch/2+1;
                }
                now_ch = 0;
                now_r = true;
            }
        }

    }

    for (long i = 0; i < s.size()-1; ++i) {
        cout << ch[i] << ' ';
    }
    cout << ch[s.size()-1] << endl;
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;


int main(){

    int A,B,C;

    cin >> A >> B >> C;

    int temp =0;

    if(A==B)temp++;
    if(A==C)temp++;
    if(B==C)temp++;

    if(temp==1){
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int isprime(int x);

int main(void)
{
    int n, cnt, x;
    
    cnt=0;
    
    scanf("%d", &n);
    
    for(int i=0; i<n; i++)
    {
        scanf("%d" , &x);
        if(isprime(x) == 0)
        {
            cnt++;
        }
    }
    
  printf("%d\n", cnt);
  
    return 0;
}

int isprime(int x)
{
    
    if(x < 2)
    {
        return 1;
    }
    else if(x == 2)
    {
        return 0;
    }
    else if(x%2 == 0)
    {
        return 1;
    }
    for(int i=3; i*i <= x; i+=2)
    {
        if(x%i==0)
        {
            return 1;
        }
    }
    return 0;
}


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

const int mod = 1e9 + 7;

int main()
{
    int N;
    string S;
    cin >> N >> S;
    vector<vector<int>> dp(N + 1, vector<int>(N));
    for(int i = 0;i < N;i++) dp[1][i] = 1;
    for(int i = 1;i < N;i++){
        if(S[i - 1] == '<'){
            int tmp = 0;
            for(int j = 0;j < N - i;j++){
                (tmp += dp[i][j]) %= mod;
                (dp[i + 1][j] = tmp) %= mod;
            }
        }
        else{
            int tmp = dp[i][N - i];
            for(int j = N - i - 1;j >= 0;j--){
                (dp[i + 1][j] += tmp) %= mod;
                (tmp += dp[i][j]) %= mod;
            }
        }
    }
    cout << dp[N][0] << endl;
    return 0;
}


Measured memory_bytes: 35584
S = input()

for i in range(2 ** 3):
  op = ['+','+','+','+']
  ans = int(S[0])
  bit = bin(i)
  bit = bit[2:len(bit)].zfill(3)
  for j in range(len(S)-1):
    if bit[j] == "0":
      ans += int(S[j+1])
      op[j] = '+'
      #S.insert(j+1,'+')
    else:
      ans -= int(S[j+1])
      op[j] = '-'
      #S.insert(j+1,'-')
  if ans == 7:
    print(S[0]+op[0]+S[1]+op[1]+S[2]+op[2]+S[3]+"=7")
    break
  

Measured memory_bytes: 3064
import java.util.Scanner;
import java.lang.String;
 
public class Main {
  
  public static void main (String[] arg) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    sc.close();
    long result = K;
    for (int i = 1; i < N; i++) {
      result *= (K - 1);
    }
    System.out.println(result);
  }
}

Measured memory_bytes: 23124
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>

using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	if (a == b)
	{
		cout << a + b << endl;
	}
	else
	{


		int h = max(a, b);
		cout << h * 2 - 1 << endl;
	}

	

}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=1e5+10;
char s[maxn];
bool f=false;
bool ab[30];
int main(){
	scanf("%s",s);
	int len=strlen(s);
	memset(ab,0,sizeof(ab));
	for(int i=0;i<len;i++){
		if(!ab[s[i]-'a']) {
			ab[s[i]-'a']=true;
		}
	} 
	for(int i=0;i<26;i++){
		if(!ab[i]){
			 printf("%c\n",i+'a');
			 f=true;
			 break;
		} 
	}
	if(!f) printf("None\n");
	return 0;
}


/*
A
int main(){
	int x,a,b;
	scanf("%d%d%d",&x,&a,&b);
	if(abs(a-x)<abs(b-x)) printf("A\n");
	else printf("B\n");
	return 0;
} 
*/


Measured memory_bytes: 384
#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

int n, m;
int a[52], b[52], c[52];
int dp[52][52][10][10];

void solve(){
  for(int i = 0; i < 52; i++){
    for(int j = 0; j < 52; j++){
      for(int k = 0; k < 10; k++){
	for(int l = 0; l < 10; l++){
	  dp[i][j][k][l] = INT_MIN;
	}
      }
    }
  }

  for(int j = 0; j <= min(m, 8); j++){
    dp[0][m - j][j][0] = 0;
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j <= m; j++){
      for(int k = 0; k <= 8; k++){
	for(int l = 0; l <= 8; l++){
	  if(j + k + l > m) break;
	  if(dp[i][j][k][l] == INT_MIN) continue;

	  int cost = c[i];
	  int shake = INT_MIN;

	  for(int A = 0; A <= k; A++){
	    for(int B = 0; B <= l; B++){
	      if(A + B == 0) continue;
	      if(A + B > 8) break;

	      shake = max(shake, a[i] * A + b[i] * B);
	    }
	  }

	  cost = max(cost, shake);

	  for(int up = 0; up <= 8; up++){
	    if(j < up) break;
	    dp[i + 1][j - up][up][k] = max(dp[i + 1][j - up][up][k], dp[i][j][k][l] + cost);
	  }
	}
      }
    }
  }

  int ans = INT_MIN;

  for(int j = 0; j <= m; j++){
    for(int k = 0; k <= 8; k++){
      for(int l = 0; l <= 8; l++){
	ans = max(ans, dp[n][j][k][l]);
      }
    }
  }

  cout << ans << endl;
}

int main(){
  while(cin >> n >> m){
    for(int i = 0; i < n; i++){
      cin >> a[i] >> b[i] >> c[i];
    }
    solve();
  }
}

Measured memory_bytes: 2220
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007


long double f(long double a, long double b, long double theta) {
    long double ret;
    if(a * tan(theta) <= b) {
        ret = a * a * b - a * a * a * tan(theta) / 2.0;
    } else {
        ret = b * b / tan(theta) * a / 2.0;
    }
    return ret;
}


int main()
{
	long double a, b, x;
	cin >> a >> b >> x;
	a += 0.0;
	b += 0.0;
	x += 0.0;
	long double pi = atan(1) * 4;
	long double l = 0.0, r = pi / 2;
	for(int i = 0; i < 100; i++){
		double mid = (l + r) / 2.0;
		if(f(a, b, mid) > x) l = mid;
		else r = mid;
	}
	long double ans = (180.0 * l) / pi;
	printf("%.10Lf\n", ans);
}



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

int main() {
  int n, k;
  cin >> n >> k;
  
  ll ans = 0;
  if (k % 2 == 1) {
    ll a = n / k;
    ans += a*a*a;
  }
  else {
    ll b = n / k;
    ans += b*b*b;
    ll c = 2 * n / k;
    c -= b;
    ans += c*c*c;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#pragma optimize("O3")
#define sync                    \
ios_base::sync_with_stdio(0); \
cin.tie(0);                   \
cout.tie(0)
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (a - 1); i >= (b); i--)
#define all(a) (a).begin(), (a).end()
#define endl "\n"
#define ll long long
#define pb push_back
#define PII pair<int, int>
#define PLL pair<long long, long long>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vll vector<long long>
#define mii map<int, int>
#define mll map<long long, long long>
#define MOD 1000000007
#define MAX 1000000007
#define MOD2 1234567891
#define SZ(a) (int) a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define TIE(l, r) Node *l, *r; tie(l, r)
#define EPS 0.00000001
#define PI 3.14159265359
void dout() { cerr << endl; }
#define MAXN 100001

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

/*,--. ,--.
  |  .'   /  ,--,--.  ,---.   ,---.   ,--,--.
  |  .   '  ' ,-.  | | .-. | | .-. | ' ,-.  |
  |  |\   \ \ '-'  | | '-' ' | '-' ' \ '-'  |
  `--' '--'  `--`--' |  |-'  |  |-'   `--`--'
                     `--'    `--'             */



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

    }
}

int main() {
    solve();


    cerr << "Time elapsed: " << clock() / (double) CLOCKS_PER_SEC << endl;
    return 0;
}



Measured memory_bytes: 8464
#include<stdio.h>

int main(void){
  int a;
  char b[11];
  
  scanf("%d", &a);
  scanf("%s", &b);
  
  if(a < 3200){
    printf("red\n");
  }
  else{
    printf("%s\n", b);
  }
  
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cmath>
int is_square(int x)
{
	int t = sqrt(x);
	if (x == t * t)
		return 1;
	return 0;
}

int main()
{
	int n, d;
	scanf("%d%d", &n, &d);
	int x[15][15];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < d; j++) {
			scanf("%d", &x[i][j]);
		}
	}
	
	int ans = 0; 
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int sum = 0;
			for (int k = 0; k < d; k++) {
				sum += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
			}
			if (is_square(sum))
				ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

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


const int N = 2005, M = 4e6 + 5;



int n, x, sum, a[N];
vector < int > q;
bitset < M > dp;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x;
        sum += x;
        a[x] += 1;
    }
    for(int i = 1; i <= 2000; i++){
        int cur = a[i];
        for(int j = 1; cur > 0; cur -= j, j <<= 1){
            if(j > cur){
                q.push_back(i * cur);
            }
            else{
                q.push_back(i * j);
            }
        }
    }
    dp[0] = 1;
    for(auto it : q){
        dp |= dp << it;
    }
    int i = (sum + 1) / 2;
    while(!dp[i]){
        i += 1;
    }
    cout << i;
}


Measured memory_bytes: 1792
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)

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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T, class S> inline bool minup(T& m, S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, S x){ return m<(T)x ? (m=(T)x, true) : false; }

const int    INF = 1000000000;
const ll     MOD = 1000000007LL;
const double EPS = 1E-12;

const int MAX_M = 100;
const int MAX_N = 10;
const int MAX_S = 1000;
const int M = MAX_M;
const int N = MAX_N;
const int S = MAX_S;
ll dp[MAX_N+1][MAX_S+1];
int n, s;

int main()
{
  dp[0][0] = 1LL;
  rep(i, M+1) rev(j, N) rep(k, S-i+1) dp[j+1][k+i] += dp[j][k];

  while((cin >> n >> s) && n){
    cout << dp[n][s] << endl;
  }


  return 0;
}

Measured memory_bytes: 1236
//This is getting accepted!
#include<bits/stdc++.h>
#define ll long long
#define oo 1000000009
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define INARR(a,n) for (int i = 1; i <= (n); ++i) cin >> a[i];
#define ITE(x) for(auto it = (x).begin(); it != (x).end(); ++it)
#define isset(x, i) (((x)>>(i))&1)
#define setbit(x, i) ((x)^(1ll<<(i)))
#define clearbit(x, i) ((x)&(~(1ll<<(i))))
#define twoexp(i) (1ll<<(i))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define FI first
#define SE second
#define son1 (id*2)
#define son2 (id*2+1)

using namespace std;

const int MOD = 1000000007;
const double EPS = 1e-8;
const double PI = 2 * acos(0);
const int MAXN = 1e6 + 6;

int n, m;
int a[MAXN], b[MAXN];
set<int> rem;
multiset< pair<int, int> > bag;

void input() {
	int u, v, w, x, y, qtype;
	
	cin >> n >> m;
	
	FOR(i, 1, n)
		cin >> a[i] >> b[i];
	
}


void preprocess() {
	
	FOR (i, 1, m)
		rem.insert(i);
	
	FOR (i, 1, n)
		bag.insert({-b[i], a[i]});
	
	ll res = 0;
	
	while(bag.size()) {
		int val = -bag.begin()->first;
		int days = bag.begin()->second;
		bag.erase(bag.begin());
		
		auto it = rem.lower_bound(days);
		
		if (it != rem.end()) {
			res += val;
			rem.erase(it);
		}
		
	}
	
	cout << res << endl;
	
}

void process(int itest) {
	int u, v, w, x, y, qtype;
	
	
	
}

void oneTest() {
	
	input();
	preprocess();
	process(0);
	
}

void multiTest() {
	
	int t;
	cin >> t;
	
	for (int it = 1; it <= t; ++it) {
		input();
		preprocess();
		process(it);
	}
}

int main(){
    #ifndef ONLINE_JUDGE
//    freopen("../out.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	oneTest();
//	multiTest();

    return 0;

}


Measured memory_bytes: 14080
import sys
import numpy as np
# from numba import njit#,i8

def addBIT(itemCount, items, i, value):
	while i <= itemCount:
		items[i] += value
		i += (i & (-i))

def sumFromStart(items, end):
	summary = 0
	i = end
	while i > 0:
		summary += items[i]
		i -= (i & (-i))
	return summary

def sumBIT(items, start,end):
	summary = sumFromStart(items, end) - sumFromStart(items, start-1)
	return summary

#@njit(cache=True)
# @jit(返り値の型(引数1の型,引数2の型,．．．,引数nの型))
#@jit(i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:]))
def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	# 答え配列
	ans=np.zeros(Q, dtype=np.int64)
	#ans=[0]*Q
	# 左からBITと現在色の更新をしながら、クエリのrightに到達したときにBITにクエリ発行する
	qindex = 0

	for n in range(N):
		# 外側のループでは、全部の色をループ

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			# ループ中の場所の色のindexが既にある場合(=過去に、同じ色が登録されていた場合)
			# 今回で、同じ色の一番右側の要素はループ中の要素になる
			# 前登録したこの色の一番右のindexを一度BITから抜く(↓で再度登録される)
			addBIT(N,bitArray,mostRightColorIndex[C[n]], -1 )

		# この要素の色の一番右のindexを、BITに登録
		mostRightColorIndex[C[n]] = n+1
		addBIT(N,bitArray,n+1, 1)

		# while qindex < Q and n+1 == queries[qindex][2]:
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			# 今のBITが次のクエリ発行するための状態(n==query.right)だったら、クエリ発行
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sumBIT(bitArray,start,end)
			# print(tmpIndex,start,end,ans[tmpIndex])
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba import njit
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('addBIT','(i8,i8[:],i8,i8)')(addBIT)
	addBIT=njit(addBIT)
	cc.export('sumFromStart','(i8[:],i8)')(sumFromStart)
	sumFromStart=njit(sumFromStart)
	cc.export('sumBIT','(i8[:],i8,i8)')(sumBIT)
	sumBIT=njit(sumBIT)
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	#main=njit(main, cache=True)
	cc.compile()
	exit(0)
from my_module import main,addBIT,sumBIT
#from numba import njit
#main=njit('i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])', cache=True)(main)



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

N,Q = map(int,input().split())

C=np.array(input().split(), int)

# Query取得-rightでソート
# dtypeQuery = [("index", int), ("start", int), ("end", int)]
queries=np.empty((Q,2),int)
# #rights=[[] for _ in range(N+1)]

for q in range(Q):
	l,r=map(int,input().split())
	#queries[q] = (q,l,r)
	queries[q][0] = l
	queries[q][1] = r
	#queries=np.sort(queries,order="end")

#queries=np.array(sys.stdin.buffer.read().split(),int).reshape(Q,2)

orderByR=np.argsort(queries[:,1])

# 各色の現在の一番右のindex
mostRightColorIndex = np.zeros(N+1, int)
# bit indexed tree
bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 2e18 * 2;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };


int main() {
	int a, b;
	cin >> a >> b;
	if ((a + b) % 2) {
		cout << (a + b) / 2 + 1 << endl;
	}
	else {
		cout << (a + b) / 2 << endl;
	}
}

Measured memory_bytes: 764
n=int(input())
a=input()
con=0
ans=n
for i in range(n):
  if i==ans:
      break
  if a[i]=="W":
    con+=1
    while ans>=0:
      ans-=1
      if i==ans:
        print(con-1)
        exit()
      if a[ans]=="R":
        break  
print(con) 

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

int main() {
  string text;
  cin >> text;
  
  if (text=="A") {
    cout << "T" << endl;
  }
  if(text=="T"){
    cout<<"A"<<endl;
  }
  if(text=="G"){
    cout<<"C"<<endl;
  }
  if(text=="C"){
    cout<<"G"<<endl;
  }
}

Measured memory_bytes: 256
def adj(g,s)
  3.times.map{|i|(g[i]-s[i]).abs}.inject(:+)
end

n,*g=gets.split.map(&:to_i)
g.sort!
l=n.times.map{gets.to_i}

min=1_000_000_000

(4**n).times{|k|
  s=[0]*4
  i=0
  cost=0
  while k>0
    q=k%4
    cost+=10 if q<3&&s[q]>0
    s[q]+=l[i]
    k/=4
    i+=1
  end
  s.pop
  if s.all?(&:positive?)
    cost+=adj(g,s.sort)
    min=cost if cost<min
  end
}
puts min

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

using ll = long long;
#define int ll

int32_t main()
{
	int n;
	scanf("%lld",&n);
	vector<double> dp(n+1);
	dp[0] = 1;
	for(int coin=0;coin<n;coin++)
	{
		double p_heads;
		scanf("%lf",&p_heads);
		for(int i=coin+1;i>=0;i--)
		{
			dp[i] = (i == 0 ? 0 : dp[i-1] * p_heads) + dp[i] * (1 - p_heads);
		}
	}
	double answer = 0;
	for(int heads=0;heads<=n;heads++)
	{
		int tails = n - heads;
		if(heads > tails)
		{
			answer += dp[heads];
		}
	}
	printf("%.10lf\n",answer);
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0)
    {
        if(b&1)
            res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==n-1)
            return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)
        return false;
    if(n<=3)
        return true;
    ll d=n-1;
    while(d%2==0)
        d/=2;
    for(int i=0; i<k; i++)
    {
        if(!miller_rabin(d,n))
            return false;
    }
    return true;
}
int n;
string s;
ll ans = 0;

void solve(ll x,ll y)
{
    if(x==n+1)
    {
        ans += y;
        return;
    }
    ll cur = 0;
    for(ll i=x; i<=n; i++)
    {
        cur = (10*cur) + (s[i]-'0');
        solve(i+1,y+cur);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,l,r;
    cin>>n>>l>>r;
    ll sum=0;
    for(int i=l;i<=n;i++){
        ll x=i;
        string s=to_string(x);
        int cnt=accumulate(s.begin(),s.end(),0,[&](int k,char ch){return k=k+(ch-'0');});
        if(l<=cnt && cnt<=r)sum+=x;
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3748
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
ans = []
score = N * (N - 1) // 2
for i in range(M - 1, -1, -1):
    ans.append(score)
    a, b = ab.pop()
    a -= 1
    b -= 1
    pa, pb = uf.find(a), uf.find(b)
    if not uf.same(pa, pb):
        score -= uf.size[pa] * uf.size[pb]
    uf.unite(a, b)
ans.reverse()
[print(ans[i]) for i in range(M)]

Measured memory_bytes: 33328
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define int long long
#define INF 1000000000000000007ll
using namespace __gnu_pbds;
using namespace std;

int n,m,s,c[60],d[60];
int dist[60][2510];
vector<pair<int,pair<int,int> > > v[60];

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,a,b;
		cin>>x>>y>>a>>b;
		v[x].push_back(make_pair(y,make_pair(a,b)));
		v[y].push_back(make_pair(x,make_pair(a,b)));
	}
	for(int i=1;i<=n;i++) cin>>c[i]>>d[i];
	priority_queue<pair<int,pair<int,int> > > q;
	s=min(s,2500ll);
	for(int i=1;i<=n;i++) for(int j=0;j<=2500;j++) dist[i][j]=INF;
	dist[1][s]=0ll;
	q.push(make_pair(0ll,make_pair(1,s)));
	while(!q.empty())
	{
		pair<int,pair<int,int> > t=q.top();q.pop();
		int num=-t.first,idx=t.second.first,cost=t.second.second;
		if(dist[idx][cost]!=num) continue;
		int now=min(cost+c[idx],2500ll);
		if(dist[idx][now]>dist[idx][cost]+d[idx]){
			dist[idx][now]=dist[idx][cost]+d[idx];
			q.push(make_pair(-dist[idx][now],make_pair(idx,now)));
		}
		for(int i=0;i<v[idx].size();i++){
			int u=v[idx][i].first,dis=v[idx][i].second.first,tim=v[idx][i].second.second;
			int now=cost-dis;
			if(now<0ll) continue;
			if(dist[u][now]>dist[idx][cost]+tim){
				dist[u][now]=dist[idx][cost]+tim;
				q.push(make_pair(-dist[u][now],make_pair(u,now)));
			}
		}
	}
	for(int i=2;i<=n;i++){
		int minv=INF;
		for(int j=0;j<=2500;j++) minv=min(minv,dist[i][j]);
		cout<<minv<<endl;
	}
	return 0;
}

Measured memory_bytes: 7232
pub struct Scanner{
     line : Vec<String> ,
     idx : usize
}

impl  Scanner{
    #[allow(dead_code)]
    fn new() -> Scanner{
        return Scanner{ line: vec![], idx : 0}
    }
    #[allow(dead_code)]
    fn next<T: std::str::FromStr> (&mut self) -> T{
        if self.idx == self.line.len() {
            let mut buffer = String::new();
            std::io::stdin().read_line(&mut buffer).ok();

            let a : Vec<&str>  = buffer.trim().split(' ').collect();
            self.line = a.iter().map(|&s| String::from(s)).collect();
            self.idx = 0;
        }
        let ret : T = self.line[self.idx].parse::<T>().ok().expect("Parse error.");
        self.idx += 1;
        ret
    }
    #[allow(dead_code)]
    fn read_vec<T: std::str::FromStr>  (&mut self, n: usize) -> Vec<T>{
        let mut v : Vec<T>= Vec::with_capacity(n);
        for _i in 0..n {
            v.push(self.next());
        }
        v
    }
}


fn main() {
    let mut scan = Scanner::new();
    let k:i32  = scan.next();
    let x:i32  = scan.next();

    let mut f = true;
    for i in (x - k + 1)..(k+x) {
        if !f {
            print!(" ");  
        }
        f = false;
        print!("{}", i);
    }

    println!("");
}

Measured memory_bytes: 4352
import itertools, math

N = int(input())
d = []
for _ in range(N):
  x, y = map(int, input().split())
  d.append([x, y])

sum = 0
cnt = 0

for v in itertools.permutations(d, N):
  cnt += 1
  for i in range(N - 1):
    x1 = v[i][0]
    y1 = v[i][1]
    x2 = v[i + 1][0]
    y2 = v[i + 1][1]
    sum += math.sqrt((abs(x1 - x2)**2) + (abs(y1 - y2)**2))
print(sum / cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define N 2009
#define M 10009
using namespace std;
 
int n,m,len,cnt,a[N],q[M],f[M<<1];
char s[N][M],ch[M],s0[M<<1]; bool bo[N][M],ok[M],vis[M];
struct node{ int x,y; }b[M];
int sig(node u,node v){
	if (!u.y && !v.y) return 0;
	if (!u.y) return -sig(v,u);
	if (!v.y){
		if (v.x<=u.x) return 0;
		int t=f[u.x+u.y+1];
		if (u.x+t>=v.x) return 0; else
		return s0[t+1]<s0[u.x+u.y+t+1]?-1:1;
	}
	if (u.x==v.x) return 0;
	if (u.x>v.x) return -sig(v,u);
	int t=f[u.x+u.y+1];
	if (u.x+t>=v.x){
		t=v.x-u.x;
		if (f[t+1]>=u.y-t) return 0;
		else return s0[f[t+1]+t+1]<s0[f[t+1]+1]?-1:1;
	} else return s0[t+1]<s0[u.x+u.y+t+1]?-1:1;
}
bool operator <(node u,node v){ return sig(u,v)<0; }
bool operator ==(node u,node v){ return !sig(u,v); }
void work(char *s,int n){
	int i,k; f[1]=0;
	for (i=2,k=1; i<=n; i++){
		f[i]=min(k+f[k]-i,f[i-k+1]);
		if (f[i]<0) f[i]=0;
		for (; s[f[i]+1]==s[i+f[i]] && i+f[i]<=n; f[i]++);
		if (i+f[i]>k+f[k]) k=i;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int i,j,k;
	for (i=1; i<=n; i++){
		scanf("%s",s[i]+1); a[i]=strlen(s[i]+1);
	}
	bo[n+1][0]=1;
	for (i=n; i; i--){
		for (j=m; j>=0; j--){
			bo[i][j]=bo[i+1][j];
			if (j>=a[i]) bo[i][j]|=bo[i+1][j-a[i]];
		}
	}
	ok[0]=1; len=0;
	for (i=1; i<=n; i++){
		if (!len){
			if (bo[i+1][m-a[i]]){
				len=a[i];
				for (j=1; j<=len; j++) ch[j]=s[i][j];
			}
			ok[len]=1; continue;
		}
		for (j=1; j<=a[i]; j++) s0[j]=s[i][j];
		for (j=1,cnt=a[i]; j<=len; j++) s0[++cnt]=ch[j];
		work(s0,cnt);
		memset(vis,0,sizeof(vis));
		for (j=0; j<=m; j++) if (bo[i+1][m-j]){
			if (ok[j]){
				vis[j]=1; b[j]=(node){j,0};
			}
			if (j>=a[i] && ok[j-a[i]])
				if (vis[j]) b[j]=min(b[j],(node){j-a[i],a[i]}); else{
					vis[j]=1;
					b[j]=(node){j-a[i],a[i]};
				}
		}
		q[1]=0;
		for (j=k=1; j<=m; j++) if (vis[j]){
			while (k>1 && b[j]<b[q[k]]) k--;
			if (b[j]==b[q[k]]) q[++k]=j;
		}
		len=q[k];
		if (b[len].y)
			for (j=1; j<=a[i]; j++) ch[b[len].x+j]=s[i][j];
		ch[len+1]=0;
		memset(ok,0,sizeof(ok));
		while (k) ok[q[k--]]=1;
	}
	printf("%s\n",ch+1);
	return 0;
}

Measured memory_bytes: 39424
# -*- coding:utf-8 -*-
import math
from decimal import *
N = int(input())
A, B = (1, 1)
for tmp in range (N):
    t, a = map(int,input().split())
    n = Decimal(max([math.ceil(A/t),math.ceil(B/a)]))
    A = n*t
    B = n*a
print(A+B)

Measured memory_bytes: 5204
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int w = sc.nextInt();
    int h = sc.nextInt();
    int x = sc.nextInt();
    int y = sc.nextInt();
    int count = 0;

    if((double)x==(double)w/2 && (double)y==(double)h/2){
      count += 1;
    }
    System.out.println((double)w*(double)h/2+" "+count);
  }
}

Measured memory_bytes: 24020
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>

using namespace std;
long long mod = 1e9 + 7;
const int N = 5e5 + 500;

long long n, m, u, v, k, t, q, a, h;

string str;



int main() {
   ios::sync_with_stdio(false);cin.tie(0);
   
   k--;
   cin >> str;
   
   bool y = true;
   bool z = true;
   
   if (str[0] == '0') {
      if (str[1] == '0') y = false;
   } else if (str[0] == '1') {
      if (str[1] != '0' and str[1] != '1' and str[1] != '2') y = false;
   } else {
      y = false;
   }
   
   if (str[2] == '0') {
      if (str[3] == '0') z = false;
   } else if (str[2] == '1') {
      if (str[3] != '0' and str[3] != '1' and str[3] != '2') z = false;
   } else {
      z = false;
   }
   
   if (y and z) {
      cout << "AMBIGUOUS" << endl;
   } else if (!y and z) {
      cout << "YYMM" << endl;
   } else if (y and !z) {
      cout << "MMYY" << endl;
   } else cout << "NA" << endl;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N;
ll A[100004];
bool flag = true;

int main(){
  cin.sync_with_stdio(false);

  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  sort(A, A + N);
  int c = 0;
  if(N % 2 == 0){
    for(int j = 1; j < N; j += 2){
      for(int i = -1; i < 1; i++){
        if(A[j+i] == j) c++;
      }
      if(c == 2){
        c = 0;
        continue;
      }else{
        cout << 0 << endl;
        flag = false;
        break;
      }
    }
  }else{
    for(int j = 0; j < N; j+=2){
      if(j == 0){
        if(A[0] !=0){
          cout << 0 << endl;
          flag = false;
          break;
        }
        if( N > 1 && A[1] != 0){
          continue;
        }else if(N == 1){
          continue;
        }else{
          cout << 0 << endl;
          flag = false;
          break;
        }
      }
      for(int i = -1; i <= 0; i++){
        if(A[j+i] == j) c++;
      }
      if(c == 2){
        c = 0;
        continue;
      }else{
        cout << 0 << endl;
        flag = false;
        break;
      }
    }
  }

  if(flag){
    ll ans = 1;
    for(int i = 1; i <= N / 2; i++){
      ans *= 2;
      ans %= ((ll)(1e9+7));
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 1024
import collections

def A_sum(A):
  s = 0
  for i in A.items():
    s+=i[0]*i[1]
  return s

def A_rep(A,f,t):
  f_num = A.get(f)
  if f_num != None:
      A[t]=A.get(t,0) + f_num
      diff = f_num*(t-f)
      A.pop(f)
      return diff
  return 0

N = int(input())
A = collections.Counter(map(int,input().split()))
Q = int(input())
ans = A_sum(A)
for i in range(Q):
  b,c = map(int,input().split())
  diff = A_rep(A,b,c)
  if diff !=0:
    ans+=diff
  print(ans)


Measured memory_bytes: 84620
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10 ** 7)


def solve(P: int, Q: int, R: int):
    lst = [P, Q, R]
    lst.sort()
    print(lst[0] + lst[1])
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    P = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(P, Q, R)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#define _for(i,n) for(int i = 0; i < n; i++)

using namespace std;



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

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

using namespace std;

long long int N,M,K,L,R,H,W;

const long long int MOD=1000000007;



int main(){
	
	while(cin>>N,N){
		vector<int>v(86401);
		for(int i=0;i<N;i++){
			string s,t;
			cin>>s>>t;
			int a=((s[0]-'0')*10+(s[1]-'0'))*3600+((s[3]-'0')*10+s[4]-'0')*60+((s[6]-'0')*10+s[7]-'0');
			int b=((t[0]-'0')*10+(t[1]-'0'))*3600+((t[3]-'0')*10+t[4]-'0')*60+((t[6]-'0')*10+t[7]-'0');
			v[a]++;
			v[b]--;
		}
		for(int i=1;i<=86400;i++)v[i]+=v[i-1];
		cout<<*max_element(v.begin(),v.end())<<endl;
	}
	return 0;
}


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

int main() {
  list<int> lt;
  int n;
  cin >> n;
  list<int>::iterator it = lt.begin();
  while (n--) {
    
    int op;
    cin >> op;
    if (op == 0) {
      int x;
      cin >> x;
      it = lt.insert(it, x);
    } else if (op == 1) {
      int d;
      cin >> d;
      if (d > 0) {
        while (d--) {
          it++;
        }
      } else {
        while (d++) {
          it--;
        }
      }
    } else {
      it = lt.erase(it);
    }
  }
  for (it = lt.begin(); it != lt.end(); it++) {
    cout << *it << endl;
  }
}


Measured memory_bytes: 18608
def isprime(N):
    for i in range(2, int(N**0.5)+1):
        if N % i == 0:
            return False
    return True
    
def prime_number(N):
    pn = []
    flg = [0] * (N+1)
    for i in range(2, N+1):
        if flg[i] > 0:
            continue
        for j in range(i, N+1, i):
            flg[j] = 1
        pn.append(i)
    return pn

N = int(input())
cnt = 0
for _ in range(N):
    num = int(input())
    cnt += isprime(num)
print(cnt)


Measured memory_bytes: 5708
import copy

shuffle_data = []
copy_data = []

while True:
  data = input()

  if data == "-":
    break

  copy_data.clear()

  for i in data:
    copy_data.append(i)
  
  Number = int(input())

  for i in range(Number):
    shuffle_data.clear()
    shuffle_number = int(input())

    for j in range(shuffle_number, len(data)):
      shuffle_data.append(copy_data[j])

    for j in range(0, shuffle_number):
      shuffle_data.append(copy_data[j])

    copy_data.clear()

    for j in shuffle_data:
      copy_data.append(j)

  for i in shuffle_data:
    print(i, end = "")

  print()


Measured memory_bytes: 6336
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<list>
#include<queue>
#include<map>
using namespace std;

int main(){
	int i, j, k, n;
	char s[8];

	scanf("%s", s);
	int a = s[0] - '0';
	int b = s[1] - '0';
	int c = s[2] - '0';
	int d = s[3] - '0';

	for (i = 0; i < 2; i++) {
		b *= (-1);
		for (j = 0; j < 2;j++) {
			c *= (-1);
			for (k = 0; k < 2; k++) {
				d *= (-1);

				if (a+b+c+d == 7) break;
			}
			if (a+b+c+d == 7) break;
		}
		if (a+b+c+d == 7) break;
	}

	printf("%d%c%d%c%d%c%d=7\n", a, 
							((b>=0)?'+':'-'), ((b>=0)?b:(-b)),
							((c>=0)?'+':'-'), ((c>=0)?c:(-c)),
							((d>=0)?'+':'-'), ((d>=0)?d:(-d)));

	return 0;
}


Measured memory_bytes: 888