akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FASTIO
using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

template <typename T1, typename T2>
bool chmin(T1& a, const T2& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool chmax(T1& a, const T2& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class Prints {
private:
    class __Prints {
    public:
        __Prints(const char* sep, const char* term) : sep(sep), term(term) {}
        template <class... Args>
        void operator()(const Args&... args) const { print(args...); }

    private:
        const char *sep, *term;
        void print() const { std::cout << term; }
        void print_rest() const { std::cout << term; }
        template <class T, class... Tail>
        void print(const T& head, const Tail&... tail) const { std::cout << head, print_rest(tail...); }
        template <class T, class... Tail>
        void print_rest(const T& head, const Tail&... tail) const { std::cout << sep << head, print_rest(tail...); }
    };

public:
    Prints() {}
    __Prints operator()(const char* sep = " ", const char* term = "\n") const { return __Prints(sep, term); }
};

Prints prints;

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    constexpr ll MX_A = 100100;
    vector<bool> is_prime(MX_A + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 1; i <= MX_A; i++) {
        if (!is_prime[i]) continue;
        for (ll j = i + i; j <= MX_A; j += i) {
            is_prime[j] = false;
        }
    }

    Vi vec(MX_A / 2);
    for (ll i = 1; i < MX_A / 2; i++) {
        if (is_prime[i] && is_prime[i * 2 - 1]) {
            vec[i] = 1;
        }
    }
    for (ll i = 0; i + 1 < MX_A / 2; i++) {
        vec[i + 1] += vec[i];
    }

    ll Q;
    cin >> Q;
    while (Q--) {
        ll left, right;
        cin >> left >> right;
        ll res = vec[(right + 1) / 2] - vec[(left + 1) / 2 - 1];
        prints()(res);
    }
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(nullptr), cout.tie(nullptr);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    cout << setprecision(18) << fixed;
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 3624
N,*A=map(int,open(0).read().split())
S=sum(A)
if S%(N*(N+1)//2):
	print('NO')
	exit()
M=S//(N*(N+1)//2)
for b in[A[i]-A[i-1]for i in range(N)]:
	if M-b<0 or (M-b)%N:
		print('NO')
		exit()
print('YES')


Measured memory_bytes: 14068
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
i=0
j=0
N=int(input())
#N, W=input().split()
#S=input()
#T=input()
#S_list=list(S)
#h_list=  list(map(int, input().split(" ")))
#M=int(input())
#drink_list = [list(map(int, input().split(" ")))for i in range(M)]
#print(T_list[1])
#N=int(N)
#W=int(W)
#不本意だが内包表記で二次元の空のリストを作成する

dp=[['' for i in range(3)] for j in range(N)]
a, b, c =[0]*N, [0]*N, [0]*N
#print(dp)
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split(" "))
dp[0]=a[0], b[0], c[0]
#幸福度は自然数なので必ず幸福度は増加する
#0がa,1がb,2がc
for i in range(N-1):
    dp[i+1][0]=max(dp[i][1]+a[i+1],dp[i][2]+a[i+1])
    dp[i+1][1]=max(dp[i][0]+b[i+1],dp[i][2]+b[i+1])
    dp[i+1][2]=max(dp[i][0]+c[i+1],dp[i][1]+c[i+1])
print(max(dp[N-1]))


Measured memory_bytes: 36260
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int inf = 100000 * 1000;
        Scanner sc = new Scanner(System.in);

        
        int[][] dist = new int[200][200];
        int[][] dp = new int[1<<8][8];
        int[] r = new int[8];

        int n = sc.nextInt();
        int m = sc.nextInt();
        int R = sc.nextInt();
        for(int i=0;i<R ;i++){
            r[i] = sc.nextInt();
            r[i]--;
        }

        for(int i=0;i<n;i++)for(int j=0;j<n;j++)dist[i][j] = inf;
        for(int i=0;i<n;i++)dist[i][i] = 0;

        for(int i=0;i<m;i++){
            int a,b,c;
            a=sc.nextInt();
            b=sc.nextInt();
            c=sc.nextInt();
            a--;b--;
            dist[a][b]=dist[b][a]=c;
        }
        for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
        }
        for(int i=0;i<(1<<R);i++)for(int j=0;j<R;j++)dp[i][j]=inf;
        for(int i=0;i<R;i++)dp[1<<i][i] = 0;

        for(int i=0;i<(1<<R);i++)for(int k=0;k<R;k++)if((i&(1<<k))!=0){
            for(int j=0;j<R;j++) if((i&(1<<j))==0){
                dp[i|1<<j][j] = Math.min(dp[i|1<<j][j], dp[i][k]+dist[r[k]][r[j]] );
            }
        }
        int ans=inf;
        for(int j=0;j<R;j++){
            ans = Math.min(ans, dp[(1<<R)-1][j]);
        }


        System.out.println(ans);
    }
}

Measured memory_bytes: 48672
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
	int X, A;
	cin >> X >> A;
	if (X < A) cout << 0 << endl;
	else cout << 10 << endl;
	return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

ll num[200001] = {};

int main(){
    ll n, k, i, fact = 0;
    cin >> n >> k;
    for(i=0; i<n+1; i++){
        if(i==0) num[i] = n+1;
        else num[i] = num[i-1] + (i+1)*n - i*(i+1)+1;
        num[i] %= MOD;
    }
    cout << (num[n]-num[k-2]+MOD)%MOD;
    return 0;
}

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

int main(){
  int N; 
  cin >>N;
  
  vector<int> H(N);
  int ans=0;
  int max=0;
  repeat(i,N) {
    cin >>H[i];
    if(H[i]>=max){
      max=H[i]; 
      ans++;
    }
  }
  cout << ans << endl;
}

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

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> pii;
typedef priority_queue< int, vector< int >, greater< int > >  minHeap;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define sz(v) v.size()
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define sqr(x) x*x
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define ten(n) (int)1e##n
#define tenll(n) (lli)1e##n
#define mod 1000000007
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int Set(int N,int pos)
{
    return N=N | (1<<pos);
}
int reset(int N,int pos)
{
    return N = N & ~(1<<pos);
}
bool check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}


inline int addmod(int x ,int y){return (x%mod + y%mod)%mod;}
inline int submod(int x ,int y){return (x%mod - y%mod + mod)%mod;}
inline int mulmod(int x ,int y){return (x%mod *1LL* y%mod)%mod;}
inline int nextSubMask(int i , int mask) {return (i-1)&mask;} /// returns next smallest submask

void we_r_done(){cout<<"NO"; exit(0);}

void debug(bool ok , string mssg)
{
    if(ok)return;
    cout<<mssg;
    exit(0);
}

int main()
{
    ///freopen("output.txt","w",stdout);
    ///freopen("input.txt","r",stdin);

    FastIO;

    int n,T;
    cin>>n>>T;

    lli t[n];

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

    lli last = 0 , ans = 0;

    for(int i=1; i<n; i++){

        if(last+T >= t[i]){
            ans += t[i]-last;
        }
        else{
            ans += T;
        }
        last = t[i];
    }

    cout<<ans+T;

    return 0;

}

///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)
///using bs = bitset<MX>; // how many distinct number can be form?


Measured memory_bytes: 1792
import numpy
import re
import math

def main():
	"""
	テストコード実行
	:return:
	"""
	"""
	ビットマスクを用いた解法
	"""
	abcd = input()
	ans = 0
	for i in range(2 ** (len(abcd) - 1)):
		p = "0" * (len(abcd) - 1 - len(bin(i)[2:])) + bin(i)[2:]
		equals = ""
		for index, num in enumerate(abcd):
			equals += num
			if index != (len(abcd) - 1) and p[index] == "1": equals += "+"
			if index != (len(abcd) - 1) and p[index] == "0": equals += "-"
		if eval(equals) == 7:
			print(equals + "=7")
			exit()

if __name__ == '__main__':
	main()


Measured memory_bytes: 12508
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int Hcount,Wcount;

	    while(true){
	        Hcount = sc.nextInt();
	        Wcount = sc.nextInt();

	        if(Hcount ==0 && Wcount ==0) {
	        	break;
	        }
	        for(int i =0; i<Hcount;i++) {
	        	for(int x =0; x<Wcount;x++) {
		        	if(i==0||i == Hcount-1)
						System.out.print("#");
					else if(x==0||x==Wcount-1)
						System.out.print("#");
					else
						System.out.print(".");
		        }
		        System.out.println();
	        }
	        System.out.println();
	    }
	}
}


Measured memory_bytes: 36740
package main

import "fmt"

func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
} 

func main() {
	var s string

	fmt.Scan(&s)

	ans := 0
	tmp := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T' {
			tmp += 1
		} else {
			tmp = 0
		}
		ans = max(ans, tmp)
	}
	
	fmt.Println(ans)
}

Measured memory_bytes: 1772
<?php
  list($n,$k) = explode(" ", trim(fgets(STDIN)));
  $a = array_map('intval', explode(" ", trim(fgets(STDIN))));

  $cnt=[];
  for($i=0;$i<$n;$i++){
    if(!isset($cnt[$a[$i]])){
      $cnt[$a[$i]]=0;
    }
    $cnt[$a[$i]]++;
  }
  if(count($cnt) <= $k){
    echo "0";
    exit;
  }
  sort($cnt);
  $ans=0;
  for($i=0;$i<(count($cnt)-$k);$i++){
    $ans+=$cnt[$i];
  }
  echo $ans;

Measured memory_bytes: 44088
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

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

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int N = scan.nextInt();
        int A[] = new int[N];
        for(int i = 0; i < N; i++)
            A[i] = scan.nextInt();

        Arrays.sort(A);
        for(int i = 1; i < N; i++){
            if(A[i-1] == A[i]) {
                os.println("NO");
                return;
            }
        }
        os.println("YES");
    }
}

Measured memory_bytes: 63276
//
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
//
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// solution 
use std::cmp;
#[allow(unused_mut)]
#[allow(non_snake_case)]
fn main() {
    input!{
        N: usize,
        A: [[usize;N];2],
    }

    let mut dp = vec![ vec![0_usize;N];2];
    dp[0][0] = A[0][0];
    for col in 1..N {
        dp[0][col] = dp[0][col-1] + A[0][col];
    }
    dp[1][0] = dp[0][0] + A[1][0];
    for col in 1..N {
        dp[1][col] = cmp::max(dp[0][col], dp[1][col-1]) + A[1][col];
    }

    println!("{}", dp[1][N-1]);
}


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

int s[10][10];

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> k(m);
  rep(i,m){
    cin >> k[i];
    rep(j,k[i]){
      cin >> s[i][j];
      s[i][j]--;
    }
  }
  vector<int> p(m);
  rep(i,m){
    cin >> p[i];
  }
  int ans = 0;

  rep(tmp,(1 << n)){
    bitset<10> switches(tmp);
    bool light = true;
    rep(i,m){
      int cnt = 0;
      rep(j,k[i]){
        if(switches.test(s[i][j])){
            cnt++;
        }
      }
      if(cnt%2!=p[i]){
        light = false;
      }
    }
    if(light == true){
      ans++;
    }
  }
  cout << ans << endl;

}



Measured memory_bytes: 256
#include <stdio.h>

inline int abs(int val) {
    return val >= 0 ? val : -val;
}

int gcd(int a, int b) {
    if (a < b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

int main(void) {
    int n;
    int x, x_next;
    int dx;
    int d;


    scanf("%d%d", &n, &x);
    scanf("%d", &x_next);
    dx = abs(x_next - x);
    x = x_next;
    d = dx;
    for (int i = 2; i <= n; i++) {
        scanf("%d", &x_next);
        dx = abs(x_next - x);
        x = x_next;
        d = gcd(d, dx);
    }
   
    printf("%d\n", d);

    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a, b, c;
    int count = 0;
    a = sc.nextInt(); b = sc.nextInt(); c = sc.nextInt();
    for (int i = a; i <= b; i++) {
    	if (c % i == 0) { count++; }
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 26384
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int ll;
using namespace std;
ll M=1000000007;
int main()
{
    IOS;
    int t=1;
	//cin>>t;
	while(t--)
	{
		ll n,i,ans=0,sum=0;
		cin>>n;
		ll a[n],b[n];
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			b[i]=a[i];
		}
		for(i=1;i<n;i++)
		{
			b[i]+=b[i-1];
		}
		for(i=0;i<n;i++)
		{
			sum=(a[i]%M)*((b[i]-a[i])%M);
			ans+=sum%M;
			if(ans>M) ans-=M;
		}
		cout<<ans%M<<endl;
	}
}


Measured memory_bytes: 6772
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp make_pair
#define fi first
#define se second
#define pt(num) cout << num << "\n"
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;



int main(void) {
    ll N;
    cin >> N;
    string s;
    cin >> s;
    ll i, j, k;
    
    ll ans=0;
    
    
    //O(N^2)
    
    for(ll mid=1; mid<N; mid++) {
        ll l[26]={}, r[26]={};
        ll t=0;
        
        for(i=0; i<mid; i++) {
            l[s[i]-'a']++;
        }
        
        for(j=mid; j<N; j++) {
            r[s[j]-'a']++;
        }
        
        for(k=0; k<26; k++) {
            if(l[k]>0 && r[k]>0) {
                t++;
            }
        }
        
        ans=max(ans, t);
        
    }
    pt(ans);
    
}


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

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (i % 2 == 0)
        {
            if (s[i] == 'L')
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else
        {
            if (s[i] == 'R')
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
use std::io;

fn gets() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

fn main() {
    let line = gets();
    let mut it = line
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<u32>().ok().unwrap());
    let a = it.next().unwrap();
    let b = it.next().unwrap();
    let c = it.next().unwrap();
    println!("{} {} {}", c, a, b);
}


Measured memory_bytes: 2052
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
	string s;
	cin >> s;
	int n;
	n = s.length();
	vector<int> answer(n,0);
	vector<int> RLpoint;

	answer[0] = 1;

	for (int i = 0; i < n; i++) {
		
		cout << endl;

		if (s.substr(i, 1) == "R") {
			if (i > 0) {
				if (s.substr(i - 1, 1) == "L") {
					answer[i] = 1;
				}
			}
			answer[i + 1] = answer[i] + 1;
			answer[i] = 0;
		}
		if (s.substr(i, 1) == "L") {
			if (s.substr(i-1, 1) == "R") {
				RLpoint.push_back(i - 1);
				answer[i - 1] = answer[i] / 2;
				answer[i] = (answer[i] + 1) / 2;
			}
			else {
				answer[RLpoint[RLpoint.size()-1] + (i - RLpoint[RLpoint.size()-1]) % 2]++;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			cout << answer[i];
		}
		else {
			cout << " " << answer[i];
		}
	}
}

Measured memory_bytes: 1404
a,b,c = map(int, input().split())
k = int(input())
ans = 0
while a >= b and k > 0:
    b *= 2
    k -= 1
if b > a: ans += 1
while b >= c and k > 0:
    c *= 2
    k -= 1
if c > b: ans += 1
print("Yes" if ans == 2 else "No")

Measured memory_bytes: 9188
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int[][] ab = new int[n][2];
        for(int i=0;i<n;i++){
            ab[i][0] = Integer.parseInt(sc.next());
            ab[i][1] = Integer.parseInt(sc.next());
        }
        Arrays.sort(ab,new Comparator<int[]>(){

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        }
        );
        int remain = m;
        long res = 0;
        int count = 0;
        for(int i=0;i<n;i++){
            if(remain==0)break;
            count = Math.min(remain,ab[i][1]);
            res+=(long)count*ab[i][0];
            remain-=count;
        }
        System.out.println(res);
        sc.close();
    }
    
}

Measured memory_bytes: 66040
#include <iostream>
#include <stdio.h>

using namespace std;

int n, m;
int pt[3][2005];
int gain[] = {5, 3, 2};
double dp[2005][2005];
double dp2[2005][3];
double exp[3][2005];
double prob[2005];

int main(void)
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> pt[0][i] >> pt[1][i] >> pt[2][i];
	}
	
	dp[0][0] = 1;
	for(int i = 0; i < m; i++){
		for(int j = 0; j <= m; j++){
			if(j == m) dp[i+1][j] += dp[i][j];
			else{
				dp[i+1][j+1] += dp[i][j] / 3.0;
				dp[i+1][j] += dp[i][j] / 3.0 * 2;
			}
		}
	}
	double sum = 0;
	for(int i = 0; i <= m; i++){
		sum += dp[m][i];
		prob[i] = sum;
	}
	
	double p, wp;
	for(int g = 0; g < 3; g++){
		for(int x = 0; x <= m; x++){
			
			for(int i = 0; i <= n; i++){
				for(int j = 0; j < 3; j++){
					dp2[i][j] = 0;
				}
			}
			dp2[1][0] = 1.0;
			
			wp = 1.0;
			for(int i = 1; i < n; i++){
				int t = (pt[g][1] * x + pt[g][i+1] - 1) / pt[g][i+1] - 1;
				if(t > m) t = m;
				if(t < 0) p = 0;
				else p = prob[t];
				wp *= 1.0 - p;
				for(int j = 0; j < 3; j++){
					dp2[i+1][j] += p * dp2[i][j];
					if(j < 2) dp2[i+1][j+1] += (1.0 - p) * dp2[i][j];
				}
			}
			
			for(int i = 0; i < 3; i++) exp[g][x] += dp2[n][i];
			exp[g][x] *= gain[g];
			exp[g][x] -= wp;
		}
	}
	
	double ans = -1e18;
	for(int i = 0; i <= m; i++){
		for(int j = 0; j <= m; j++){
			int k = m - i - j;
			if(k < 0) continue;
			ans = max(ans, exp[0][i] + exp[1][j] + exp[2][k]);
		}
	}
	printf("%.11f\n", ans);
	
	return 0;
}


Measured memory_bytes: 34644
#include <stdio.h>

int main(){
    int i,j,k,ans=1;
    int w,h,x,y,judge;
    double s=0.0;


    scanf("%d %d %d %d",&w,&h,&x,&y);

    s = (double)w*(double)h/2.0;

    judge=0;
//        if((w%2==0)&&(h%2==0)){
            if((2*x==w)&&(2*y==h)){
                judge=1;
            }   
//        }

    printf("%lf %d",s,judge);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,k,c=0;
cin>>n>>k;
map<ll,ll> mp;
set<ll> st;
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
st.insert(a);
mp[a]+=b;
}
for(ll s:st){
c+=mp[s];
if(k<=c){
cout<<s;
return 0;
}
}
}

Measured memory_bytes: 7168
#include <bits/stdc++.h>
#include <iomanip>
#include<algorithm>
#define ll long long
using namespace std;

int main() {
  ll N, M, A, B, ans = 0;
  cin>> N >> M;
  vector<ll> H(N), cnt(N, 1);
  for(ll i = 0; i < N; i++) cin >> H.at(i);
  for(ll i = 0; i < M; i++) {
    cin >> A >> B;
    if(H.at(A - 1) < H.at(B - 1)) cnt.at(A - 1) = 0;
    else if(H.at(A - 1) > H.at(B - 1)) cnt.at(B - 1) = 0;
    else  cnt.at(A - 1) = cnt.at(B - 1) = 0;
  }
  for(ll i = 0; i < N; i++) {
    if(cnt.at(i) == 1) ans++;
  }
  cout << ans << endl; 
}

Measured memory_bytes: 4840
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <deque>  
#include <iomanip>

using namespace std;

using ll = long long;
#define INF 1e9
#define MOD 1e9 + 7
#define rep(i, n) for(int i = 0; i < n; i++)
#define loop(i, a, n) for(int i = a; i < n; i++)
#define all(in) in.begin(), in.end()
int main(){
    string S;
    cin >> S;
    int ans = 0;
    rep(i, 2) if(S[i]== '9') ans++;
    cout << (ans != 0 ? "Yes" : "No") << endl;
    return 0;

}


Measured memory_bytes: 256
nm = input()
N = int(nm[:nm.index(" ")])
M = int(nm[nm.index(" ")+1:])
A = list(map(int,input().split()))
A.sort()
restriction = 1/(4*M)*sum(A)
string = "Yes"
for i in range(N-1,N-M-1,-1):
	if A[i]<restriction:
		string = "No"
		break;
print(string)


Measured memory_bytes: 3060
#include<stdio.h>
#define mod 1000000007

int main(){
  long long n,m,i,j,k,l,np,nf,nr,nb,res=0;
  long long dp[8192][2]={0},ndp[8192][2]={0};
  scanf("%lld%lld",&n,&m);
  for(i=1;i<=n;i++){
    dp[i][0]=1;
  }
  dp[0][1]=1;
  for(i=0;i<m;i++){
    for(j=0;j<=n;j++){
      for(k=0;k<2;k++){
        for(l=0;l<4;l++){
          nr=j;
          nb=n-j;
          np=dp[j][k];nf=k;
          if((l/2)==0){
            nb--;
            if(nb<0){np=0;}
          }
          else{
            nr--;
            if(nr==0){nf=1;}
            if(nr<0){np=0;}
          }

          nr++;
          nb++;

          if((l%2)==0){
            nb--;
            if(nb<0){np=0;}
          }
          else{
            nr--;
            if(nr==0){nf=1;}
            if(nr<0){np=0;}
          }
          if(np==0){continue;}
          ndp[nr][nf]+=np;
        }
      }
    }
    for(j=0;j<=n;j++){
      dp[j][0]=ndp[j][0]%mod;
      dp[j][1]=ndp[j][1]%mod;
      ndp[j][0]=0;
      ndp[j][1]=0;
    }
  }
  for(i=0;i<=n;i++){
    res+=dp[i][1];
  }
  printf("%lld\n",res%mod);
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int N;
  cin >> N;
  if (N == 1) {
    int a;
    cin >> a;
    cout << a/2 << endl;
    return 0;
  }
  ll A[N];
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 1; i < N; i++) {
  ans += (A[i-1] + A[i]) / 2;
  if (A[i-1] == 1 && A[i] == 0) {
    continue;
  }
    if ((A[i-1] + A[i]) % 2 == 0) {
      A[i-1] = 0;
      A[i] = 0;
    } else {
      A[i-1] = 0;
      A[i] = 1;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
//verify AOJ1508
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;


int dp[100001][10];

int main(){
	int n,m;
	int a[10];
	string id;

	cin>>n>>id;
	cin>>m;
	for(int i=0;i<m;i++)cin>>a[i];
	dp[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<10;j++){
			if(id[i]=='*'){
				for(int k=0;k<m;k++){
					int x=a[k];
					if((n-i)%2==0){
						x*=2;
						if(10<=x)x=x/10+x%10;
					}
					dp[i+1][(j+x)%10]+=dp[i][j];
				}
			}else{
				int x=id[i]-'0';
				if((n-i)%2==0){
					x*=2;
					if(10<=x)x=x/10+x%10;
				}
				dp[i+1][(j+x)%10]+=dp[i][j];
			}
		}
	}
	cout<<dp[n][0]<<endl;
	return 0;
}

Measured memory_bytes: 5284
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
	double a, b, c, d, e, f;
	for (; cin >> a >> b >> c >> d >> e >> f;)
	{
		double x, y;
		if (a == 0 || b == 0 || d == 0 || e == 0)
		{
			if (a == 0)
			{
				y = c / b;
				x = (f - e * y) / d;
			}
			else if (b == 0)
			{
				x = c / a;
				y = (f - d * x) / e;
			}

			if (d == 0)
			{
				y = f / e;
				x = (c - b * y) / a;
			}
			else if (e == 0)
			{
				x = f / d;
				y = (c - a * x) / b;
			}
		}
		else
		{
			double a0 = a * e;
			double c0 = c * e;

			double d0 = d * b;
			double f0 = f * b;

			x = (f0 - c0) / (d0 - a0);

			y = (c - a * x) / b;
		}

		if (x == 0)
		{
			x = abs(x);
		}
		if (y == 0)
		{
			y = abs(y);
		}

		cout << fixed << setprecision(3) << x << " " << y << endl;

	}
}


Measured memory_bytes: 3188
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <tuple>
#include <climits>
#include <sstream>
using namespace std;

static const unsigned long long int MOD = 1000000007LL;

int main()
{
    int n, d, res = 0;
    double x[11][11];
    cin >> n >> d;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            cin >> x[i][j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            double dist = 0;
            for (int k = 0; k < d; k++)
            {
                dist += pow((x[i][k] - x[j][k]), 2);
            }

            dist = pow(dist, 0.5);

            if (ceil(dist) == floor(dist))
            {
                res++;
            }
        }
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		char s[] = sc.next().toCharArray();
		int[][] az = new int[s.length][26];

		az[0][s[0] - 'a']++;
		for (int i = 1; i < s.length; i++) {
			az[i][s[i] - 'a']++;
			for (int j = 0; j < 26; j++) {
				az[i][j] += az[i - 1][j];
			}
		}
		int max = 0;
		int cnt;
		for (int i = 0; i < s.length; i++) {
			cnt = 0;
			for (int j = 0; j < 26; j++) {
				if (az[i][j] > 0 && az[s.length - 1][j] - az[i][j] > 0) {
					cnt++;
				}
			}
			max = Math.max(max, cnt);
		}
		System.out.println(max);
	}
}


Measured memory_bytes: 23764
def main():
    N, M, X, Y = map(int, input().split())
    A = [int(x) for x in input().split()]
    B = [int(y) for y in input().split()]
    for Z in range(X+1, Y+1):
        isFound = True
        for i in range(N):
            if A[i] >= Z:
                isFound = False
                break
        if isFound:
            for j in range(M):
                if B[j] < Z:
                    isFound = False
                    break
        if isFound:
            return "No War"
    return "War"

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 3064
s=str(input())
alphabet=["a","b","c","d","e","f"
,"g","h","i","j","k","l","m","n",
"o","p","q","r","s","t","u","v","w","x","y","z"]
for i in s:
    if i in alphabet:
        alphabet.remove(i)
if len(alphabet)!=0:
    print(alphabet[0])
else:
    print("None")

Measured memory_bytes: 3188
#include <stdio.h>

using ll = long long;
const int MX = 1000005, MM = 998244353;

ll F[MX], I[MX], IF[MX];

ll C(int x,int y){return F[x+y]*IF[x]%MM*IF[y]% MM;}

int main()
{
	int N, M, i;
	I[1]=F[0]=IF[0]=F[1]=IF[1]=1;
	for(i = 2; i < MX; i++){
		I[i] = (MM - MM/i) * I[MM%i] % MM;
		F[i] = F[i-1] * i % MM;
		IF[i] = IF[i-1] * I[i] % MM;
	}

	scanf("%d%d", &N, &M);
	if( N > M ) N^=M^=N^=M;
	ll ans = M, tot = IF[N+M] * F[N] % MM * F[M] % MM;
	for(i = 1; i <= N; i++){
		ans = (ans + tot * C(N-i, M-i) % MM * C(i, i) % MM * I[2]) % MM;
	}
	printf("%lld\n", ans);
}



Measured memory_bytes: 23680
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int a[100100],b[100100];
int c[100100];

int aa[100100];

vector<int> ab[100100];

int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a[i]>>b[i];
		ab[a[i]].push_back(b[i]);
		ab[b[i]].push_back(a[i]);
	}
	for(int i=0;i<n;i++){
		cin>>c[i];
	}
	sort(c,c+n,greater<int>());
	ll sum=0;
	for(int i=1;i<n;i++){
		sum+=(ll)c[i];
	}
	
	for(int i=0;i<100100;i++)
		aa[i]=-1;
	queue<int>q;
	q.push(1);
	aa[1]=0;
	int count=1;
	while(q.size()){
		int fr=q.front();q.pop();
		for(int i=0;i<ab[fr].size();i++){
			if(aa[ab[fr][i]]==-1){
				aa[ab[fr][i]]=count;
				count++;
				q.push(ab[fr][i]);
			}
		}
	}
	cout<<sum<<endl;
	int ra[100100];
	for(int i=1;i<=n;i++){
		ra[aa[i]]=i;
	}
	for(int i=1;i<=n;i++){
		cout<<c[aa[i]]<<" ";
	}
	cout<<endl;
	return 0;
}

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

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

int n, D[N], m, mark[N], ans[N], ind[N];
vector<pii> G[N];

bool cmp(int x, int y){
	return D[x] < D[y];
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	memset(mark, -1, sizeof mark);
	for (int i = 1; i <= n; i++){
		ind[i] = i;
		cin >> D[i];
	}
	for (int i = 1; i <= m; i++){
		int v, u;
		cin >> v >> u;
		G[v].pb({u, i}), G[u].pb({v, i});
	}
	for (int i = 1; i <= n; i++){
		bool f = 0;
		for (auto u:G[i]){
			if (D[u.F] <= D[i]) f = 1;
		}
		if (!f) return cout << -1, 0;
	}
	sort(ind + 1, ind + n + 1, cmp);
	for (int i = 1; i <= n; i++){
		if (mark[ind[i]] != -1) continue;
		for (auto u:G[ind[i]]){
			if (D[u.F] <= D[ind[i]]){
				if (mark[u.F] == -1){
					mark[u.F] = 0;
					mark[ind[i]] = 1;
					ans[u.S] = D[ind[i]];
				}else{
					mark[ind[i]] = 1 - mark[u.F];
					ans[u.S] = D[ind[i]];
				}
			//	cout << "Fuck " << u.S << '\n';
				break;
			}
		}
	}
	for (int i = 1; i <= n; i++)cout << (mark[i]?'W':'B');
	cout << '\n';
	for (int i = 1; i <= m; i++){
		cout << (ans[i] == 0?1000000000:ans[i]) << '\n';
		//cout << ans[i] << '\n';
	}
	return 0;
}


Measured memory_bytes: 16168
#include <stdio.h>
#define max(a,b) a<b?b:a
int n,m,cnt;short v[5005][5005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0,x,y,z;i<m;i++){
		scanf("%d%d%d",&x,&y,&z);
		v[x][y]=max(v[x][y],(short)(z+1));
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) if(v[i][j]) v[i+1][j]=max(v[i+1][j],(short)(v[i][j]-1));
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) if(v[i][j]) v[i+1][j+1]=max(v[i+1][j+1],(short)(v[i][j]-1));
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cnt+=!!v[i][j];
	printf("%d\n",cnt);
}

Measured memory_bytes: 48776
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		
		System.out.printf("%d %d %.10f\n",(a / b),(a % b),((double)a / (double)b));
		
	}

}



Measured memory_bytes: 26500
import java.util.*;

class Kakaku{
	public long value;
	public int num;

	Kakaku(long a){
		value = a;
		num = 1;
	}

	public void add(){
		num++;
		return;
	}
}
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int p1 = 0;
		int p2 = 0;
		long[] ireko = new long[n];
		long sum = 0;
		double ans1;
		long ans2;

		for(int i=0; i<n; i++){
			ireko[i] = sc.nextLong();
		}
		Arrays.sort(ireko);
		Kakaku[] sorted = new Kakaku[n];
		sorted[0] = new Kakaku(ireko[n-1]);

		for(int i=n-2; i>=0; i--){
			if( sorted[p1].value == ireko[i] ){
				sorted[p1].add();
			}else{
				p1++;
				sorted[p1] = new Kakaku(ireko[i]);
			}
		} //sorted[0]~sorted[p1]までデータが入っている

		if( sorted[0].num >= a ){ //この場合のみbが用いられる
			ans1 = (double)sorted[0].value;
			ans2 = 0;
			for( int i=a; i<=Math.min(b,sorted[0].num); i++ ){
				ans2 += calcC(sorted[0].num,i);
			}
		}else{
			b = a;
			while(true){
				if( sorted[p2].num < b ){
					b -= sorted[p2].num;
					sum += sorted[p2].num * sorted[p2].value;
					p2++;
				}else{
					sum += b * sorted[p2].value;
					ans1 = (double)sum / (double)a;
					ans2 = calcC(sorted[p2].num,b);
					break;
				}
			}
		}
		System.out.println(ans1);
		System.out.println(ans2);
		return;
	}

	public static long calcC( int n, int m ){
		long c = 1;
		m = ( n-m < m ? n-m:m );
		for( int ns = n-m+1, ms=1; ms<= m; ns++, ms++ ){
			c *= ns;
			c /= ms;
		}
		return c;
	}

}

Measured memory_bytes: 22860
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;

string toUpper(string s){
    string t = s;
    for(int i = 0; i < s.size(); i++){
        t[i] = toupper(s[i]);
    }
    return t;
}

int main(){
    string word, text;
    cin >> word;
    word = toUpper(word);

    int count = 0;
    while(1){
        cin >> text;
        if(text == "END_OF_TEXT") break;
        text = toUpper(text);
        if(word == text) count++;
    }
    cout << count << endl;
    return 0;
    
}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main()
{
    ios::sync_with_stdio(0);
    string s;
    cin>>s;
    s += 'R';
    vector<int> ve;
    int cnt = 1;
    for (int i = 1;i < s.size();i ++)
    {
        if (s[i] != s[i-1])
        {
            ve.push_back(cnt);
            if (s[i] == 'L') a[i-1] = a[i] = 1;
            cnt = 0;
        }
        cnt ++;
    }
    for (int i = 0;i < ve.size();i += 2)
    {
        if ((ve[i]+ve[i+1]) & 1)//不同
        {
            int sum = ve[i] + ve[i+1];
            if (ve[i]&1) ve[i] = sum/2+1,ve[i+1] = sum/2;
            else ve[i] = sum/2,ve[i+1] = sum/2+1;
        }
        else ve[i] = (ve[i]+ve[i+1])/2,ve[i+1] = ve[i];
    }
    bool flag = 0;
    int pos = 0;
    for (int i = 0;i < s.size()-1;i++)
    {
        if (flag) cout<<' ';
            flag = 1;
        if (a[i])
            cout<<ve[pos ++];
        else cout<<0;
    }
    return 0;
}


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

int main() {
	char a[3];
	cin >> a;
	for (int i = 0; i < 3; i++) {
		if (a[i] == '1') {
			a[i] = '9';
		}
		else if (a[i] == '9') {
			a[i] = '1';
		}
	}
	cout << a << endl;
	return 0;
}

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

namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {

            int a,b,c,d,g=0;

            a = int.Parse(Console.ReadLine());
            b = int.Parse(Console.ReadLine());
            c = int.Parse(Console.ReadLine());
            d = int.Parse(Console.ReadLine());

            for (int i = 0; i < a; i++)
            {
                if (i < b)
                {
                    g += c;
                }
                else
                {
                    g += d;
                }
            }

            Console.WriteLine(g);


        }
    }
}

Measured memory_bytes: 2776
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, std::string S, std::string T){
  for(int i=0; i<2*N; i++) {
    if(i%2==0)
      std::cout << S[i/2];
    else
      std::cout <<  T[i/2];
  }
  std::cout  << std::endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  std::string S;
  std::cin >> S;
  std::string T;
  std::cin >> T;
  solve(N, S, T);
  return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	int n;
    cin>>n;
    vi a(n);
    vi cn(101010,0);
    LL s=0;
    FOR(i,0,n){
        cin>>a[i];
        cn[a[i]]++;
        s+=a[i];
    }
    int q;
    cin>>q;
    vi b(q),c(q);
    FOR(i,0,q){
        cin>>b[i]>>c[i];
        s=s+(c[i]-b[i])*cn[b[i]];
        cn[c[i]]+=cn[b[i]];
        cn[b[i]]=0;
        cout<<s<<endl;
    }

}


Measured memory_bytes: 4784
#include <bitset>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stdio.h>
#include <math.h>


using namespace std;

typedef long long ll;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<ll> vll;

typedef vector<vector<ll>> vvll;

typedef pair<int, int> Pair;
#define mp(x, y) make_pair(x, y)

typedef queue<int> qi;
typedef queue<string> qs;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define repp(i, a, b) for(int i = (a); i <= (b); i++)
#define repm(i, n) for(int i=n; i >= 0; i--)

#define all(v) v.begin(), v.end()
//sort( all(v) )　などと使える

//nが素数かをO(√n)で判断
bool is_prime(int n) {
    bool res = true;

    if (n == 1) return false;
    else if (n == 2) return true;

    else {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = false;
                break;
            }
        }
    }

    return res;
}



int perm(int n, int r) {
    if (r == 1) return n;
    return n * perm(n - 1, r - 1);
}

int fact(int n) {
    if (n == 1) return 1;
    return fact(n - 1) * n;
}

int comb(int n, int r) {
    int a = min(n, r), b = max(n, r);
    return perm(a, b) / fact(a);
}



/*
ll pow_mod(ll a, ll n, ll mod) {
    ll res = 1;

    ll base = a;
    while (n) {
        if (n & 1) res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
*/

//aの逆元　（a^(-1)）を求める
ll inv_mod(ll a, ll mod) {
    ll b = mod, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

/*
ll fact_mod(ll n, ll mod) {
    if (n == 1) return 1;
    return n * fact_mod(n - 1, mod) * mod;
}
*/

// 階乗 (mod とりバージョン)
ll fact_mod(ll n, ll mod) {
    ll f = 1; for (int i = 2; i <= n; i++) f = f * (i % mod) % mod;
    return f;
}

ll pow_mod(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * x) % mod; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % mod;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

// 組み合わせ nCr を求める (modあり)
ll comb_mod(ll n, ll r, ll mod) {
    if (r > n - r) r = n - r;
    if (r == 0) return 1;
    ll a = 1;
    for (int i = 0; i < r; i++) a = a * ((n - i) % mod) % mod;
    ll b = pow_mod(fact_mod(r, mod), mod - 2, mod);
    return (a % mod) * (b % mod) % mod;
}


int main() {
    int k; cin >> k;
    string c;
    rep(i, k) c += "ACL";

    cout << c << endl;
}

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

#if 0
まず計算量を見積もる。
入力であるeの制約がe ≦ 10^6と大きいことに注目する。
x + y^2 + z^3 = eのもと、総当たりでfor文を回すと計算量はO(n^3)<10^6*10^3*10^2=10^11となり時間制限を越えそうである。
そこで、x=e-z^3-y^2の関係を用いればyとzについてのみ探索すれば良く、計算量はO(n-2)<10^2*10^3=10^5程度になる。これは十分計算可能である。
#endif

int solve(int E){
  int minimum = 100000;
  int x,y,z;

  for(z = 0; z <= 100; ++z)
    for(y = 0; y <= 1000; ++y){
      x = E - y*y - z*z*z;
      if(x >= 0)
        minimum = min(minimum, x + y + z);
    }

  return minimum;
}

int main() {
  int E;
  while(cin >> E && E>0){
    cout << solve(E) << endl;
  }
 }



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

int main(){
    int n,A[100];
    cin>>n;
    for(int i=0;i<n;i++)cin>>A[i];
    
    for(int i=n-1;i>=0;i--){
        if(i!=n-1)cout<<" ";
        cout<<A[i];
    }
    cout<<endl;
    return 0;
}
         


Measured memory_bytes: 3076
#include<stdio.h>
#include<math.h>

int main(){
  int i;
  int N;
  int sum;
  while(scanf("%d",&N),N!=0){
    sum=0;
    for(i=1;i<sqrt(N);i++){
      if(N%i==0){
	if(i*i==N) sum+=i;
	else sum+=i+N/i;
      }
    }
    sum-=N;

    if(sum==N) puts("perfect number");
    else if(sum<N) puts("deficient number");
    else puts("abundant number");
  }
  return 0;
}

Measured memory_bytes: 584
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        vector<int> ts(n);
        for (int i = 0; i < n; i++) {
            cin >> ts[i];
        }
        sort(ts.begin(), ts.end());
        long long sum = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            ans += sum;
            sum += ts[i];
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1248
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<deque>
#include<cmath>
#include<stack>
#include<string.h>
#include <iomanip>
#define rep(i,n) for(int i = 0;i<n;i++)
#define _GLIBCXX_DEBUG
using ll = long long; 
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n,A,B,C;

vector<int>L;
int INF = 100000000;

int rec(int i,int a,int b,int c) {
	if(i==n) {
		if(!a || !b || !c)return INF;
		return abs(a-A)+abs(b-B)+abs(c-C)-30;
	}
	int res0 = rec(i+1,a,b,c);
	int res1 = rec(i+1,a+L[i],b,c)+10;
	int res2 = rec(i+1,a,b+L[i],c)+10;
	int res3 = rec(i+1,a,b,c+L[i])+10;
	
	return min({res0,res1,res2,res3});   
}

int main() {
	cin >> n >> A >> B >> C;
	L.resize(n);
	rep(i,n) cin >> L[i];
	cout << rec(0,0,0,0) << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#include <complex>
#define pa pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
	int k=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	return k*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
	write(x);puts("");
}
const int N=1e5+10;
map<pa,int>mp;
set<int>e[N];
int fa[N],n;
queue<pa>q;
inline int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
inline void addedge(int x,int y){
	e[x].insert(y);e[y].insert(x);
	pa now=mkp(min(x,y),max(x,y));
	mp[now]++;
	if(mp[now]==2)q.push(now);
}
int main()
{
	n=read();
	for(int i=1;i<2*n-1;i++){
		int x=read(),y=read();
		addedge(x,y);
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	while(!q.empty()){
		int x,y;
		x=q.front().fi;y=q.front().se;
		q.pop();
		x=find(x);y=find(y);
		if(x==y)continue;
		e[x].erase(y);e[y].erase(x);
		if(e[x].size()>e[y].size())swap(x,y);
		fa[x]=y;
		for(auto k:e[x]){
			k=find(k);
			mp[mkp(min(x,k),max(x,k))]=0;
			addedge(k,y);
			e[k].erase(x);
		}
		e[x].clear();
	}
	int sum=0;
	for(int i=1;i<=n;i++)if(fa[i]==i)sum++;
	if(sum==1)puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 40320
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <string>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define REVE(x) reverse(x.begin(),x.end())
#define all(x) (x).begin(),(x).end()
#define fst first
#define mp make_pair
#define pb push_back
using LL = long long;
using ULL = unsigned long long;
#define FOR(i, m, n) for(int i = m;i < n;i++)
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B, C, D;
    cin >> A >> B >> C;
  for(int i=A;i<=A*B;i+=A){
  	if(i%B==C){
  	cout<<"YES";
      return 0;
  	}
     	}
 
  cout << "NO";
  
}

Measured memory_bytes: 256