akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <set>
using namespace std;

int dp[2002][2002];
int cnt_white[2002][4002];
int cnt_black[2002][4002];

int main(){
    int N;
    cin >> N;
    map<int, int> white, black;
    for(int i=0; i<2*N; i++){
        char c;
        int a;
        cin >> c >> a;
        if(c == 'W') white[a] = i+1;
        else black[a] = i+1;
    }

    int aa[4002];
    fill_n(aa, 4002, 0);
    for(int i=N; i>=1; i--){
        aa[white[i]] = 1;
        for(int j=1; j<=2*N; j++)
            cnt_white[i][j] = cnt_white[i][j-1] + aa[j];
    }
    fill_n(aa, 4002, 0);
    for(int i=N; i>=1; i--){
        aa[black[i]] = 1;
        for(int j=1; j<=2*N; j++)
            cnt_black[i][j] = cnt_black[i][j-1] + aa[j];
    }

    for(int i=0; i<=N; i++)
        for(int j=0; j<=N; j++)
            dp[i][j] = 1<<30;
    dp[0][0] = 0;

    for(int i=0; i<2*N; i++){
        for(int w=0; w<=i; w++){
            int b = i - w;
            if(b > N || w > N) continue;
            if(w < N)
                dp[w+1][b] = min(dp[w+1][b], dp[w][b] + cnt_white[w+2][white[w+1]] + cnt_black[b+1][white[w+1]]);
            if(b < N)
                dp[w][b+1] = min(dp[w][b+1], dp[w][b] + cnt_black[b+2][black[b+1]] + cnt_white[w+1][black[b+1]]);
        }
    }
    cout << dp[N][N] << endl;
    return 0;
}


Measured memory_bytes: 78720
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string S;
    cin >> S;
    int r = 0;
    int b = 0;
    int Count = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] == '1') r++;
        else b++;
    }
    //cout << r << " " << b << endl;
    Count = min(r*2,b*2);
    cout << Count << endl;
}


Measured memory_bytes: 512
///mAAria...
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pii pair<int,int>
#define pi 3.1415926535897932384626433832
#define mod 1000000007
//#define mod 998244353
#define inf 1000000000
#define pr1(a) cout << a << "\n"
#define pr2(a,b)cout << a <<  " " <<b<< "\n"
#define pr3(a,b,c) cout << a <<" " << b << " " << c << "\n"

const long double PI = acos(-1);

int powm(int a, int b) {
    int res=1;
    while(b) {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

int gcd(int a, int b){
    if(b==0)return a;
    gcd(b,a%b);
}
const int maxn = 2*1e5 + 10;

void solve(){

    int n;
    cin >> n;

    int ans= n*(n+1)/2;

    for(int i  =1;i<=n;i++){
        if(i%3==0 || i%5==0){
            ans-=i;
        }

    }

    cout << ans << endl;

} 

signed main() 
{   
    IOS;
    int t = 1;
    // cin >> t;

    for(int i = 1;i<=t;i++){
        solve();
    }
    return 0;
} 

 


Measured memory_bytes: 3652
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
template <typename T>
T pow(T a, ll n, T e = 1) {
    T ret = e;
    while (n) {
        if (n & 1) ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}
 
template <int mod>
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod) x -= mod;
    }
    ModInt& operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    ModInt& operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0) x += mod;
        return *this;
    }
    ModInt& operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt& operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }
 
    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }
 
    friend ostream& operator<<(ostream& s, ModInt<mod> a) {
        s << a.x;
        return s;
    }
    friend istream& operator>>(istream& s, ModInt<mod>& a) {
        s >> a.x;
        return s;
    }
};
 
using mint = ModInt<1000000007>;
using Graph = vector<vector<int>>;
Graph G;
/*------------------------------------------------------------------*/
ll dp [3000][3000][4];
ll score[3000][3000];
int main(){
    ll R, C, K; cin >> R >> C >> K;
    
    rep(i, R + 1)rep(j, C + 1) score[i][j] = 0;
    rep(i, K){
        ll a, b, c; cin >> a >> b >> c;
        a--, b--;
        score[a][b] = c;
    }
    rep(i, 3000)rep(j, 3000)rep(k, 4) dp[i][j][k] = 0;
    if(score[0][0] > 0) dp[0][0][1] = score[0][0];

    rep(i, R)rep(j, C)rep(k, 4){
        if(j + 1 < C){
            dp[i][j + 1][k] = max(dp[i][j][k], dp[i][j + 1][k]);
            if(k < 3) dp[i][j + 1][k + 1] = max(dp[i][j][k] + score[i][j + 1], dp[i][j + 1][k + 1]);
        }
        if(i + 1 < R){
            dp[i + 1][j][0] = max(dp[i][j][k], dp[i + 1][j][0]);
            dp[i + 1][j][1] = max(dp[i][j][k] + score[i + 1][j], dp[i + 1][j][1]);
        }
    }    
    ll ans_max = 0;
    rep(k, 4) ans_max = max(ans_max, dp[R - 1][C - 1][k]);
    cout << ans_max << endl;
}

Measured memory_bytes: 355140
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    string newStr = "";
    for (int i = 0; i < 2 * n; i++) {
        if (i % 2 == 0) {
            newStr += s[i / 2];
        } else {
            newStr += t[i / 2];
        }
    }
    OUT(newStr);
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int N,A,min=1000000010,max=0;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%d",&A);
    if(A<min) min=A;
    if(A>max) max=A;
  }
  printf("%d\n",max-min);
  return 0;
}

Measured memory_bytes: 128
from collections import deque

h, w = map(int, input().split())

s = []
white = 0
for y in range(h):
    s.append(input())
    white += s[y].count('.')

def gets(y, x):
    if 1 <= y <= h and 1 <= x <= w:
        return s[y - 1][x - 1] == '.'
    else:
        return False

v = set()
q = deque([(1, 1, 0)])
costMin = -1
while len(q) > 0:
    y, x, cost = q.popleft()
    if (y, x) == (h, w):
        costMin = cost
        break

    if (y, x) not in v:
        v.add((y, x))
        if gets(y - 1, x): q.append((y - 1, x, cost + 1))
        if gets(y + 1, x): q.append((y + 1, x, cost + 1))
        if gets(y, x - 1): q.append((y, x - 1, cost + 1))
        if gets(y, x + 1): q.append((y, x + 1, cost + 1))

if costMin < 0:
    print(-1)
else:
    print(white - costMin - 1)

Measured memory_bytes: 3700
// Vacation

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int n;
int a, b, c;

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

    // dp[i][j]: i-2日目までの幸福の最大値 + i-1日目に選択肢jを選んだ時の幸福量
    int dp[n][3];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = a;
    dp[0][1] = b;
    dp[0][2] = c;
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> c;
        for (int j = 0; j < 3; j++) {
            if (j == 0) {
                dp[i][j] = max(dp[i-1][1], dp[i-1][2]) + a;
            } else if (j == 1) {
                dp[i][j] = max(dp[i-1][0], dp[i-1][2]) + b;
            } else {
                dp[i][j] = max(dp[i-1][0], dp[i-1][1]) + c;
            }
        }
    }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < 3; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }


    int res = max(dp[n-1][0], dp[n-1][1]);
    cout << max(res, dp[n-1][2]) << endl;

    return 0;
}


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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second　//pairの二つ目の要素

int main(){
    string s,ans="";
    cin>>s;
    rep(i,s.size()) ans+='x';
    cout<<ans<<endl;
    return 0;
}

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

// Participants ... N
// initial point ... K
// if(answer[N]) point[!N] -=1
// Q collect answers at this round
// i'th answer is by Ai
// check if who lost(point 0)
//
// input
// N K Q
// A1
// A2
// ...
// Aq
//
// output
// No
// No
// ...
// Yes

int main(){
    int32_t N,K,Q;
    std::cin >> N >> K >> Q;
    std::vector<int32_t> points(N, 0);

    int32_t answer;
    for(int32_t round = 1; round <= Q; round++){
        std::cin >> answer;
        points[answer-1]++;
    }
    for(int32_t n = 0; n < N; n++){
        if(K - Q + points[n] > 0){
            std::cout << "Yes" << std::endl;
        }
        else{
            std::cout << "No" << std::endl;
        }
    }

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define x1 jfkljfewlkjfwekl
#define x2 jkfwejklfwej
#define y1 kfewfe
#define y2 jfwekj3w3e

int bomb[50][50];


int a[4][4] = {
	{0,0,0,0},
	{0,0,0,0},
	{1,1,0,0},
	{1,1,0,0},
};
int myquery(int x1,int x2,int y1,int y2){
	int sum = 0;
	for(int i = y1 ; i <= y2 ; i++)
		for(int j = x1 ; j <= x2 ; j++)
			sum += a[i][j];
	return sum;
}
int query(int x1,int x2,int y1,int y2){
	cout << "? " << y1 << " " << x1 << " " << y2 << " " << x2 << endl;
	//return myquery(x1,x2,y1,y2);
	int sum;
	cin >> sum;
	return sum;
}
void dfs(int x1,int x2,int y1,int y2,int prv){
	if( x1 > x2 or y1 > y2 ) return;
	if( x1 == x2 and y1 == y2 ){
		bomb[y1][x1] = query(x1,x2,y1,y2);
		
		return;
	}else{
		int ask = query(x1,x2,y1,y2);
		
		if(!ask) return;
		int X = (x1+x2) / 2;
		int Y = (y1+y2) / 2;
		dfs(x1,X,y1,Y,ask);
		dfs(X+1,x2,y1,Y,ask);
		dfs(x1,X,Y+1,y2,ask);
		dfs(X+1,x2,Y+1,y2,ask);
	}
	
}
signed main(){
	int H,W,N,K;
	cin >> H >> W >> N >> K;
	dfs(0,W-1,0,H-1,-1);
	long long ans = 0;
	long long w = 1;
	for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++){
			ans += w * bomb[i][j];
			ans %= K;
			w *= 2;
			w %= K;
		}
	}
	cout << "!" << " " << ans << endl;
}

Measured memory_bytes: 724
import sys

def gcd(x,y):
    if(y>0):
        return gcd(y,x%y)
    else:
        return x

def lcm(x,y):
    return x/gcd(x,y)*y

for x in sys.stdin.readlines():
    n = [float(y) for y in x.split()]

    print "%d %d" % (gcd(n[0], n[1]),(lcm(n[0], n[1])))

Measured memory_bytes: 5948
#include<bits/stdc++.h> 
using namespace std; 
//python interactive_runner.py python3 local_testing_tool.py 0 -- ./Code
 
#define x first
#define y second
#define rep(i, a,b) for(int i = int(a); i < int(b); ++i)
#define forn(i,b) for(int i = 0; i < int(b); ++i)


void solve(){
	int A,B;
	cin>>A>>B;
	cout<<A*B<<'\n';
}
int main(){

	 solve();
	return 0;
}

Measured memory_bytes: 3592
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;

int main(){
	string s,t;
	
	cin >> s >>t;
	int ans=0;
	REP(i,s.size()){
		if(s[i]!=t[i]) ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3916
#ifndef __cplusplus
    cat << EOF
#endif
#include <bits/stdc++.h>
using namespace std;

#define rep(...) overload_rep(__VA_ARGS__, rep_1, rep_0)(__VA_ARGS__)
#define rep_0(i, end) for(int i = 0; i < (end); ++i)
#define rep_1(i, fr, ba) for(int i = (fr); i <= (ba); ++i)
#define overload_rep(arg0, arg1, arg2, name, ...) name
#define all(box) box.begin(), box.end()

template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if(lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if(lhs > rhs) { lhs = rhs; return 1; } return 0; }

int main() {

    int a, b;
    cin >> a >> b;
    cout << 6 - a - b << '\n';
    return 0;

}


Measured memory_bytes: 256
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
chk = [0, 0, 0]
cnt = [0, 0, 0]
ans = ''
ans = -1
sc2 = []

if M == 0:
    if N == 1:
        print(0)
        exit()
    else:
        tmp = ''
        for i in range(N):
            if i == 0:
                tmp += '1'
            else:
                tmp += '0'
        print(int(tmp))
        exit()
for i in range(M):
    if cnt[sc[i][0] - 1] == 0:
        chk[sc[i][0] - 1] = sc[i][1]
        cnt[sc[i][0] - 1] += 1
        sc2.append([sc[i][0], sc[i][1]])
    else:
        if chk[sc[i][0] - 1] != sc[i][1]:
            print(-1)
            exit()

for i in range(1000):
    cnt = 0
    for j in range(len(sc2)):
        if len(str(i)) < N:
            break
        if str(i)[sc2[j][0] - 1] == str(sc2[j][1]):
            cnt += 1

    if cnt >= len(sc2):
        ans = i
        break

print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
    public static void main(String[] args ){
        Scanner scanner = new Scanner(System.in);
        int H = scanner.nextInt();
        int W = scanner.nextInt();
        while(H != 0 || W != 0){
            for(int i = 1; i <= H; i++){
                for(int j = 1; j <= W; j++){
                    if(i == 1 || j == 1 || i == H || j == W)
                        System.out.print("#");
                    else
                        System.out.print(".");
                }
                System.out.print("\n");
            }
            System.out.print("\n");
            H = scanner.nextInt();
            W = scanner.nextInt();
        }
    }
}



Measured memory_bytes: 36728
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        for (int i = 0; i <= x; i++) {
            int j = x - i;
            if (2 * i + 4 * j == y) {
                System.out.println("Yes");
                return;
            }
        }

        System.out.println("No");
    }

}

Measured memory_bytes: 35768
N,M = list(map(int,input().split()))
a = list(map(int,input().split()))

data = {}

tmp = 0
for i in range(N):
  tmp += a[i]
  if tmp%M not in data:
    data[tmp%M] = 1
  else:
    data[tmp%M] += 1
else:
  if 0 in data:
      data[0] += 1

cnt = list(data.values())
ans = 0
for i in cnt:
  ans += (i*(i-1))//2
print(ans)


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

int a, b, ta = 0;

int main() {
	cin >> a >> b;
	for (int i = a; i <= b; i++) {
		if (i == 0) {
			cout << "Zero" << endl;
			return 0;
		}
		else if (i < 0) {
			ta++;
		}
	}
	if (ta % 2 == 0) {
		cout << "Positive" << endl;
		return 0;
	}
	else {
		cout << "Negative" << endl;
		return 0;
	}
}

Measured memory_bytes: 256
s = list(input())
s_f = s[0: (len(s) - 1) // 2]
s_b = s[(len(s) + 3) // 2 - 1:len(s)]

if (s != s[::-1]) or (s_f != s_f[::-1]) or (s_b != s_b[::-1]):
    print('No')
else:
    print('Yes')


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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

divisors = make_divisors(N)

min_v = 10 ** 10
for i in range(len(divisors)):
    div1 = str(divisors[i])
    div2 = str(N // divisors[i])
    min_v = min(min_v, max(len(div1), len(div2)))
    
print(min_v)


Measured memory_bytes: 3064
#include<stdio.h>
 
int main(){
  
  int n;
  int a[101];
  int i;
  int check;
  
  check=0;
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d ",&a[i]);
  }
  
  for(i=0;i<n;i++){	
    if(a[i]%2==0){	
      if(a[i]%3==0){
      
      }else if(a[i]%5==0){
        
      }else if(a[i]==2){
        check++;
      }
      else{
        check++;
      }
    }else{
      
    }
  }
	if(check){
      printf("DENIED");
   		
    }else{
      printf("APPROVED");
    }
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<utility>//swapでaとbの値を入れ替える
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
#define sort(s) sort(s.begin(),s.end())
#define r(s) reverse(s.begin(),s.end())
using namespace std;


int main() {
	int a, b;
	int ans = 0;
	cin >> a >> b;
	ans = abs(a - b);
	if (ans % 2 == 0)cout << (a + b) / 2 << endl;
	else cout << "IMPOSSIBLE" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

char a[13][13];
int count;
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

void lake(int i, int j)
{
	int newx, newy;
	int k;
	
	a[i][j] = '0';
	
//	if (a[i][j] == '1'){
		for (k = 0; k < 4; k++){
			newx = i + dx[k];
			newy = j + dy[k];
			
			if (newx >= 0 && newy >= 0 && newx < 12 && newy < 12 && a[newx][newy] == '1'){
				lake(newx, newy);
			}
		}
//	}
}

int main(void)
{
	int i, j;
	
	while (1){
		for (i = 0; i < 12; i++){
			if (scanf("%s", a[i]) == EOF){
				return (0);
			}
		}
		
		for (i = 0; i < 12; i++){
			for (j = 0; j < 12; j++){
				if (a[i][j] == '1'){
					lake(i, j);
					
					count++;
				}
			}
		}
		
		printf("%d\n", count);
		count = 0;
	}
}

Measured memory_bytes: 540
def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)

Measured memory_bytes: 106076
import scala.io.StdIn
import Math.{sqrt,pow}
/**
  * AOJ
  */
object Main {

  def main(args: Array[String]): Unit = {
    while(true){
      val n = StdIn.readInt()
      if(n == 0){return}
      val sArray = StdIn.readLine().split(" ").map(_.toDouble)
      val m:Double = sArray.sum / n
      println("%.8f".format(sqrt(sArray.map(x => (x - m) * (x - m)).sum / n)))
    }
  }
}

Measured memory_bytes: 45276
from collections import defaultdict
 
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(int)
for a in A:
  d[a]+=1

q = int(input())
sum_a=sum(A)
for _ in range(q):
  b,c=list(map(int,input().split()))
  sum_a+=(c-b)*d[b]#初期配列で数えた数
  d[c]+=d[b]#変換した数を引き継ぎ
  d[b]=0#変換されたので消す
#  print(d)
  print(sum_a)


Measured memory_bytes: 24080
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define ull unsigned long long

const int base = 233;
const int N = 1e5 + 5;

char st[N];
ull hasf , hass , hast;

int main ( void ) {
    scanf ( "%s" , st + 1 );
    int len = strlen ( st + 1 );
    for ( int i = 1 ; i <= len ; i++ ) 
        hasf = hasf * base + st[i];
    for ( int i = len ; i >= 1 ; i-- )
        hass = hass * base + st[i];
    if ( hasf == hass ) {
        puts ( "Yes" );
      //  system ( "pause" );
        return 0;
    }
    for ( int i = 1 ; i <= len ; i++ ) {
        if ( st[i] == 'b' ) 
            st[i] = 'd';
        else if ( st[i] == 'd' ) 
            st[i] = 'b';
        else if ( st[i] == 'p' ) 
            st[i] = 'q';
        else if ( st[i] == 'q' ) 
            st[i] = 'p';
    } 
    for ( int i = 1 ; i <= len ; i++ ) 
        hast = hast * base + st[i];
    if ( hasf == hast || hast == hass ) {
        puts ( "Yes" );
     //   system ( "pause" );
        return 0;
    }
    puts ( "No" );
    //system ( "pause" );
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
int main() {
    int W, H, N;
    cin >> W >> H >> N;
    Graph G;
    Graph square(H, vector<int>(W, 1));
    for(int i = 0; i < N; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        int start_x = 0;
        int end_x = 0;
        int start_y = 0;
        int end_y = 0;
        if(a == 1) {
            start_x = 0;
            end_x = x;
            start_y = 0;
            end_y = H;
        } else if(a == 2) {
            start_x = x;
            end_x = W;
            start_y = 0;
            end_y = H;
        } else if(a == 3) {
            start_x = 0;
            end_x = W;
            start_y = 0;
            end_y = y;
        } else {
            start_x = 0;
            end_x = W;
            start_y = y;
            end_y = H;
        }
        for(int i = start_y; i < end_y; i++) {
            for(int j = start_x; j < end_x; j++) {
                square[i][j] = 0;
            }
        }
    }
    int count = 0;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(square[i][j] == 1) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#define int long long 
using namespace std;
int dp[55],mod=1000000007LL;
char map[2][55],a[55],tot;
main()
{
	int i,j,k,n,m,last=0;
	char c,d,e;
	cin>>n;
	for(i=1;i<=n;i++)cin>>map[0][i];
	for(i=1;i<=n;i++)cin>>map[1][i];
	for(i=1;i<=n;i++)
	{
		if(map[0][i]==map[1][i])
		{
			tot++;
			a[tot]=1;
		}
		else 
		{
			i++;
			tot++;
			a[tot]=2;
		}
	}
	if(a[1]==1)dp[1]=3;
	else dp[1]=6;
	for(i=2;i<=tot;i++)
	{
		if(a[i-1]==1)
		{
			if(a[i]==1)dp[i]=dp[i-1]*2%mod;
			else dp[i]=dp[i-1]*2%mod;
		}
		else
		{
			if(a[i]==2)dp[i]=dp[i-1]*3%mod;
			else dp[i]=dp[i-1];
		}
	}
	cout<<dp[tot]%mod;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>

int n, m, l;
int64_t a[100][100], b[100][100], c[100][100];

int main(void) {
	int i, j, k;
	if (scanf("%d%d%d", &n, &m, &l) != 3) return 1;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (scanf("%"SCNd64, &a[i][j]) != 1) return 1;
		}
	}
	for (i = 0; i < m; i++) {
		for (j = 0; j < l; j++) {
			if (scanf("%"SCNd64, &b[i][j]) != 1) return 1;
		}
	}
	for (i = 0; i < n; i++) {
		for (k = 0; k < m; k++) {
			for (j = 0; j < l; j++) {
				c[i][j] += a[i][k] * b[k][j];
			}
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < l; j++) {
			if (j > 0) putchar(' ');
			printf("%"PRId64, c[i][j]);
		}
		putchar('\n');
	}
	return 0;
}




Measured memory_bytes: 2136
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
int main() {
    long long n;
    cin >> n;
    if (n == 1) cout << '0';
    else
    {
        long long p9 = 9, p8 = 8, a = 0;
        for (long long i = 1; i < n; i++)
        {
            a = (a * 10) % mod;
            a = (a + (p9 - p8) * 2) % mod;
            p9 = p9 * 9 % mod;
            p8 = p8 * 8 % mod;
        }
        cout << (a + mod) % mod;
    }
}


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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  string s;
  cin >> s;
  vector<int> count(26,0);
  LL souwa=0;
  LL ans=1;
  for(int i=0;i<s.length();i++){
    ans+=souwa-count[s[i]-'a'];
    souwa++;
    count[s[i]-'a']++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int, int> p;
 
int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);

    vector<int> x(5);

    for(int i = 0; i < 5; i++) cin >> x[i];

    for(int i = 0; i < 5; i++) {
        if(x[i] == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int N;
    int cnt = 0;
    cin >> N;
    int count = 0;

    for(int i = 1; i <= N; i++){
        count = 1;
        int X = i;
        while((X / 10) != 0){
            X = (X / 10);
            count++;
        }
        if(count % 2 != 0){
            cnt++;
        }
    }

    cout << cnt << endl;       
}

Measured memory_bytes: 256
import sys

def main():
    N = int(input())
    s = set()
    for _ in range(N):
        a = int(input())
        if a in s:
            s.remove(a)
        else:
            s.add(a)
    ans = len(s)
    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 11884
// Aizu Vol-20 2006: Keitai Message
// 2017.8.12 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

char *gets();
char *t[10] = {	"\0", ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
int w[10] = { 0, 5, 3, 3, 3, 3, 3, 4, 3, 4 };
char buf[1100], *p;

int main()
{
	int n;
	int a, k;

	gets(buf), n = atoi(buf);
	while (n-- > 0) {
		gets(p = buf);
		while (*p) {
			if (*p == '0') p++;
			else {
				a = *p++ - '0', k = 1;
				while (*p != '0') p++, k++;
				p++;
				putchar(t[a][(k - 1) % w[a]]);
			}
		}
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 524
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(sc.next());
        }
        System.out.println(set.size());
        sc.close();
    }
}

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

using namespace std;
int main()
{
    int i;
    int n;
    cin >> n;

    double x[1000];
    double y[1000];
    double man = 0.0;                      //p=1
    double euc = 0.0;                      //p=2
    double cub = 0.0;                      //p=3
    double chb = 0.0;                      //p=∞
    for (i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    for (i = 0; i < n; i++)
    {
        cin >> y[i];
    }

    for (i = 0; i < n; i++)
    {
        double dis = 0.0;
        double maxdis = 0.0;
        dis = abs(x[i] - y[i]);            //x-yの差分
        man += dis;
        euc += dis * dis;   
        cub += dis * dis * dis;
        if (chb < dis) 
        {
            chb = dis;
        }


    }
    euc = sqrt(euc);
    cub = pow(cub, 1.0 / 3);
    cout << fixed << setprecision(6) << man << endl;
    cout << fixed << setprecision(6) << euc << endl;
    cout << fixed << setprecision(6) << cub << endl;
    cout << fixed << setprecision(6) << chb << endl;

    return 0;

}


Measured memory_bytes: 3488
#include<cstdio>
#include<cstring>

int w,h;
char map[70][70], wmap[70][70], bmap[70][70];

void wdfs(int x, int y) {
    if(x<0 || x>=w || y<0 || y>=h) return;
    if(map[y][x] != '.') return;
    if(wmap[y][x]) return;
    wmap[y][x] = 1;
    wdfs(x-1,y);
    wdfs(x,y-1);
    wdfs(x+1,y);
    wdfs(x,y+1);
}
void bdfs(int x, int y) {
    if(x<0 || x>=w || y<0 || y>=h) return;
    if(map[y][x] != '.') return;
    if(bmap[y][x]) return;
    bmap[y][x] = 1;
    bdfs(x-1,y);
    bdfs(x,y-1);
    bdfs(x+1,y);
    bdfs(x,y+1);
}

int main(void) {
    while(true) {
        scanf("%d%d",&w,&h);

        if(!w) break;
        memset(map, 0, sizeof(map));
        memset(wmap, 0, sizeof(wmap));
        memset(bmap, 0, sizeof(bmap));

        for(int j=0; j<h; j++)
            scanf("%s", map[j]);
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                switch(map[j][i]) {
                    case 'W':
                        wdfs(i-1,j);
                        wdfs(i,j-1);
                        wdfs(i+1,j);
                        wdfs(i,j+1);
                        break;
                    case 'B':
                        bdfs(i-1,j);
                        bdfs(i,j-1);
                        bdfs(i+1,j);
                        bdfs(i,j+1);
                        break;
                }
        int bres=0,wres=0;
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                if(wmap[j][i] && !bmap[j][i]) wres++;
                else if(bmap[j][i] && !wmap[j][i]) bres++;

        printf("%d %d\n", bres, wres);

    }
    return 0;
}

Measured memory_bytes: 1092
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>
#include <set>

#define mod 1000000007
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)

using namespace std;
using ll = long long;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

int gcd(int a, int b) {
    int x = max(a, b);
    int y = min(a, b);
    int z = x % y;
    if(z == 0){
        return y;
    }else{
        return gcd(y, z);
    }
}

int lcm(int a, int b) {
    return (a*b)/gcd(a, b);
}

void solve() {
    int n;
    cin >> n;
    ll a[n];
    vector<ll> b;
    REP(i, n) cin >> a[i];

    for(int i = n-1; i >= 0; i-=2){
        if(i >= 0 && i < n){
            b.push_back(a[i]);
        }
    }
    for(int i = n%2; i < n; i+=2){
        if(i >= 0 && i < n){
            b.push_back(a[i]);
        }
    }
    for(auto i = b.begin(); i != b.end(); i++){
        cout << *i << " ";
    }
    cout << endl;
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 5488
import java.util.*;

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 s = 0;
        for (int i=1; i <= n; i++) {
            int x = i;
            int digSum = 0;
            while (x>0) {
                digSum += x %10;
                x /= 10;
            }
            if (digSum >= a && digSum <= b)
                s += i;
        }
        System.out.println(s);
        sc.close();
    }
}

Measured memory_bytes: 35640
# -*- coding: utf-8 -*-


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

if N == 1:
    print(v[0])
elif N == 2:
    avg = (v[0] + v[1])/2
    print(avg)
else:
    v.sort()
    avg = (v[0] + v[1])/2
    for i in range(2,N):
        avg = (avg + v[i]) /2
    print(avg)


Measured memory_bytes: 3060
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	aSum := make([]int, n+1)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)

		aSum[i+1] = a + aSum[i]
	}
	store := make(map[int]int, n+1)

	cnt := 0
	for i := 0; i < n+1; i++ {
		cnt+= store[aSum[i]]
		store[aSum[i]]++

	}
	fmt.Println(cnt)

}


Measured memory_bytes: 11536
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a;
    cin >> a;
    cout << ((a+999)/1000)*1000-a;

    return 0;
}

Measured memory_bytes: 3648
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}
int read() {
	int tmp;
	cin >> tmp;
	return tmp;
}
int xor128() {
	static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	int t = (x xor (x << 11));
	x = y; y = z; z = w;
	return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}

signed main() {
	int d, g;
	cin >> d >> g;
	tuple<int, int, int>tu[15];
	rep(i, d) {
		int p, c;
		cin >> p >> c;
		tu[i] = make_tuple((i + 1) * 100,p,c);
	}
	sort(tu, tu + d), reverse(tu, tu + d);

	int bans = INF;
	rep(i, 1 << d) {
		int bit[15];
		rep(j, d) bit[j] = i / (1 << j) % 2;

		int cnt = 0, sans = 0;
		rep(j, d) {
			if (bit[j]) {
				cnt += get<2>(tu[j]);
				cnt += get<1>(tu[j]) * get<0>(tu[j]);
				sans += get<1>(tu[j]);
			}
		}
		//cout << cnt << " ";
		if (cnt >= g) {
			bans = min(bans, sans);
			goto bou;
		}
		rep(j, d) {
			if (!bit[j]) {
				rep(k, get<1>(tu[j])) {
					cnt += get<0>(tu[j]);
					sans++;
					if (cnt >= g) {
						bans = min(bans, sans);
						goto bou;
					}
				}
			}
		}
	bou:;
		//cout << cnt << " " << sans << endl;
	}
	cout << bans << endl;
		
	return 0;
}


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

bool IsChusin(vector<vector<long>> &data,long cx,long cy,long ch){
    for(vector<long> d:data){
        long t = ch-abs(cx-d[0])-abs(cy-d[1]);
        if(t<0) t=0;
        if(d[2] != t) return 0;
    }
    return 1;
}

int main(){
    long n; cin>>n;
    vector<vector<long>> data(n,vector<long>(3));
    for(int i=0;i<n;++i){
        cin>>data[i][0]>>data[i][1]>>data[i][2];
    }
    
    long mini_h = 10000000000;
    for(int i=0;i<n;++i) mini_h = min(mini_h,data[i][2]);
    
    for(int x=0;x<=100;++x) for(int y=0;y<=100;++y) for(int h=mini_h;h<=mini_h+200;++h) if(IsChusin(data,x,y,h)) cout<<x<<" "<<y<<" "<<h<<endl;
    return 0;
}


Measured memory_bytes: 768
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/abc140/tasks/abc140_d

N, K = map(int, input().split())
S = input().strip()

happiness = 0
for idx in range(1, N):
    if S[idx] == S[idx - 1]:
        happiness += 1

# 一人しか幸せにできないときがあるか?
#
# あっ...これは不要なのでは...
# 単に後述の幸せの最大値で丸めればよいのでは
# always_two_happiness = S[0] == S[-1]

# 幸せの最大値
max_happiness = N - 1

for i in range(K):
    happiness += 2

print(min(happiness, max_happiness))


Measured memory_bytes: 3316
#include<vector>
#include<map>
#include<algorithm>
#include<set>
#include<iostream>
#include<string>
#include<set>
#include<queue>
#include<random>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")

#define pb push_back
#define int long long
#define ld long double
#define ll long long

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	if (n == 2){
        cout << 1;
        return 0;
	}
	int ans = 0;
	map<int, int> used;
	for (int i = 2; i <= sqrt(n); i++) {
		int m = n;
		while (m % i == 0) {
			m /= i;
		}
		if (m % i == 1) {
			ans++;
			used[i] = 1;
		}
		m = n;
		while (m % (n / i) == 0) {
			m /= n / i;
		}
		if (m % (n / i) == 1 && !used[n / i]) {
			ans++;
			used[n / i] = 1;
		}
	}
	n--;
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0 && !used[i]) {
			ans++;
			used[i] = 1;
		}
		if (n % i == 0 && !used[n / i]) {
			ans++;
			used[n / i] = 1;
		}
	}
	if (!used[n]){
        ans++;
	}
	if (!used[n + 1]){
        ans++;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
use std::collections::VecDeque;
use std::io::stdin;
use std::str::FromStr;

fn read_line<T>() -> Vec<T>
where
    T: FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect()
}

fn read_str_as_char_vec() -> VecDeque<char> {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().chars().collect()
}

fn read_str_as_T<T>() -> T
where
    T: FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().parse().unwrap()
}

fn main() {
    let in_vec: Vec<usize> = read_line();
    let n = in_vec[0];
    let p = in_vec[1];

    let s = read_str_as_char_vec();

    if vec![2, 5].contains(&p) {
        let mut res = 0;
        for (i, &s_i) in s.iter().enumerate() {
            if (s_i as usize - '0' as usize) % p == 0 {
                res += i + 1;
            }
        }
        println!("{}", res);
        return;
    }

    let mut cnt_vec: Vec<usize> = vec![0; p as usize];
    cnt_vec[0] += 1;

    let mut bef_mod = 0;
    let mut bef_base_mod = 1 % p;
    for &s_i in s.iter().rev() {
        bef_mod = (bef_base_mod * (s_i as usize - '0' as usize) + bef_mod) % p;
        cnt_vec[bef_mod as usize] += 1;
        bef_base_mod = (bef_base_mod * 10) % p;
    }

    let mut res = 0;
    for cnt in cnt_vec {
        if cnt > 1 {
            res += cnt * (cnt - 1) / 2;
        }
    }

    println!("{}", res);
}


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

int main()
{
    int A, B, M;
    cin >> A >> B >> M;
    vector<int> a(A);
    vector<int> b(B);
    for (int i = 0; i < A; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < B; i++)
    {
        cin >> b[i];
    }
    int minA = *min_element(a.begin(), a.end());
    int minB = *min_element(b.begin(), b.end());
    int ans = minA + minB;
    for (int i = 0; i < M; i++)
    {
        int x, y ,c;
        cin >> x >> y >> c;
        x--;
        y--;
        ans = min(ans, a[x] + b[y] - c);
    }
    cout << ans << endl;
    return 0;
 

}



Measured memory_bytes: 1024
import java.io.*;
import java.util.*;
import java.lang.*;

class Main{
  public static void main(String[] args) throws IOException{
    Scanner scan=new Scanner(System.in);
    String s=scan.next();
    String p=scan.next();

    if(s.contains(p)){
      System.out.println("Yes");
    }else if(isSubString(s,p)){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
  static boolean isSubString(String str1,String str2){

    for(int i=1;i<str2.length();i++){
      if(str1.endsWith(str2.substring(0,i))){
        if(str1.startsWith(str2.substring(i,str2.length()))){
          return true;
        }
      }
    }

    return false;
  }
}



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

int a[100010];
int b[100010];
long long bp[100010];
int c[100010];
long long cp[100010];

int main(){ 
    int n;
    cin >> n;
    for (int i=0;i<n;i++)
        cin >> a[i];
    sort(a,a+n);
    for (int i=0;i<n;i++)
        cin >> b[i];
    sort(b,b+n);
    for (int i=0;i<n;i++)
        cin >> c[i];
    sort(c,c+n);

    for (int i=0;i<n;i++) {
        int* p = lower_bound(a,a+n,b[i]);
        int v = p - a - 1;
        if (v < 0) {
            bp[i] = 0;
        } else {
            bp[i] = v + 1;
        }
        //cerr << bp[i] << " ";
    }
    //cerr << endl;
    for (int i=1;i<n;i++) {
        bp[i] += bp[i-1];
    }
    for (int i=0;i<n;i++) {
        int* p = lower_bound(b,b+n,c[i]);
        int v = p - b - 1;
        if (v < 0) {
            cp[i] = 0;
        } else {
            cp[i] = bp[v];
        }
        //cerr << cp[i] << " ";

    }
    //cerr << endl;
    long long answer = 0;
    for (int i=0;i<n;i++) {
        answer += cp[i];
    }

    cout << answer << endl;

    return 0;
}




Measured memory_bytes: 2944
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let k: usize = sc.read();
    let mut hs: Vec<usize> = sc.vec(n);
    hs.sort();
    let mut result = 10e9 as u64;
    for i in 0..n {
        if i + k - 1 >= n {
            break;
        }
        let tmp = (hs[i + k - 1] - hs[i]) as u64;
        result = std::cmp::min(result, tmp);
    }
    println!("{}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self.stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self.stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8572
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

int main()
{
    int A, B, K;
    cin >> A >> B >> K;

    int cnt = 0;
    bool flag=true;

    REP(i,K){
        if(flag){
            if(A%2!=0){
                A--;
            }
            A = A / 2;
            B+=A;
            flag = false;
        }else{
            if(B%2!=0){
                B--;
            }
            B = B / 2;
            A+=B;
            flag = true;
        }
    }

    cout << A << " " << B << endl;

    return 0;
}

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

void solve() {
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '?') {
			s[i] = 'D';
		}
	}
	cout << s << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

Measured memory_bytes: 3780
a, b = map(int, input().split())

# x = sorted([a, b, a - 1, b - 1], reverse=True)
# print(x[0] + x[1])

if a > b:
	print(a + (a - 1))
elif b > a:
  	print(b + (b - 1))
else:
	print(a + b)

Measured memory_bytes: 2940
#include <stdio.h>

using namespace std;
typedef long long llong;

#define MAX 200001
const llong mod = 1000000000 + 7;

int main()
{
  int N;
  int A[MAX];
  int a;
  int current = 0;
  scanf("%d", &N);

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

  for (int i = 0; i < N - 1; i++)
  {
    scanf("%d", &a);
    A[a]++;
  }

  for (int i = 0; i < N; i++)
  {
    printf("%d\n", A[i + 1]);
  }

  return 0;
}

Measured memory_bytes: 2508
#include<bits/stdc++.h>
using namespace std;
int main(){
	int x,y,i,f=0;
	cin>>x>>y;
	for(i=0;i<=x;i++){
		if((i*2+(x-i)*4)==y){
			f=1;
			break;
		}
	}
	if(f==1)
	cout<<"Yes\n";
	else
	cout<<"No\n";
	return 0;
}

Measured memory_bytes: 3628
class ModInt(x: Long) {

    companion object {
        const val MOD = 998244353L
    }

    val x = (x % MOD + MOD) % MOD

    operator fun plus(other: ModInt): ModInt {
        return ModInt(x + other.x)
    }

    operator fun minus(other: ModInt): ModInt {
        return ModInt(x - other.x)
    }

    operator fun times(other: ModInt): ModInt {
        return ModInt(x * other.x)
    }

    operator fun div(other: ModInt): ModInt {
        return this * other.inv()
    }

    fun pow(exp: Long): ModInt {
        if (exp == 0L) return ModInt(1L)
        var a = pow(exp shr 1)
        a *= a
        if (exp and 1L == 0L) return a
        return this * a
    }

    fun inv(): ModInt {
        return this.pow(MOD - 2)
    }

    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false

        other as ModInt

        if (x != other.x) return false

        return true
    }

    override fun hashCode(): Int {
        return x.hashCode()
    }

    override fun toString(): String {
        return "$x"
    }

}

class Comb(n: Int) {

    companion object {
        const val MOD = ModInt.MOD
    }

    private val fact = LongArray(n + 1)
    private val factInv = LongArray(n + 1)

    init {
        fact[0] = 1L
        for (i in 1..n) {
            fact[i] = fact[i - 1] * i % MOD
        }
        factInv[n] = ModInt(fact[n]).inv().x
        for (i in n downTo 1) {
            factInv[i - 1] = factInv[i] * i % MOD
        }
    }

    fun comb(n: Int, k: Int): Long {
        if (k !in 0..n) return 0L
        return fact[n] * factInv[k] % MOD * factInv[n - k] % MOD
    }

}

fun main() {
    val cb = Comb(200000)
    val (n, m, k) = readLine()!!.split(' ').map { it.toInt() }

    var ans = ModInt(m.toLong()).pow(n.toLong())
    var x = ModInt(m.toLong())
    for (i in 0 until (n - 1 - k)) {
        val y = ModInt(cb.comb(n - 1, i))
        ans -= (x * y)
        x *= ModInt(m - 1L)
    }
    println(ans)
}


Measured memory_bytes: 54780
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    ans = 0
    for i in range(1,n+1):
        if i%3 and i%5:
            ans += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 67800
n = int(input())
h = list(map(int,input().split()))
ans = 0
tmp = 0
for i in range(1,n):
    if h[i] <= h[i - 1]:
        tmp += 1

    else:
        ans = max(ans, tmp)
        tmp = 0
ans = max(ans,tmp)
print(ans)


Measured memory_bytes: 14224