akhauriyash/Code-Regression huggingface dataset:
import java.util
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    val cnt = (x: Int) => {
      var ret = 0
      var y = x
      while(y%2==0) {
        y /= 2
        ret += 1
      }
      ret
    }
    var l = List[Int]()
    for(i <- 0 until n) {
      l = sc.nextInt() :: l
    }
    println(l.map(cnt).min)
  }
}


Measured memory_bytes: 25688
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

template<class T> inline void checkmin(T &a,const T &b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,const T &b){if(b>a) a=b;}

const int inf=1e9+10;
const int maxn=5e5+10;

int bit[maxn*4][30],n,q;
string s;

int sum(int i,int c){
	int s=0;
	while(i>0){
		s+=bit[i][c];
		i-=i&-i;
	}
	return s;
}

void add(int i,int x,int c){
	while(i<=n){
		bit[i][c]+=x;
		i+=i&-i;
	}
}

int main(){
	cin>>n>>s;
	for(int i=s.size();i>=1;i--) s[i]=s[i-1];
	for(int i=1;i<=n;i++) s[i]=s[i]-'a';
	s[0]=0;
	for(int i=1;i<=n;i++){
		add(i,1,s[i]);
	}
	int q;
	cin>>q;
	while(q--){
		int f;
		cin>>f;
		if(f==2){
			int l,r;
			cin>>l>>r;
			l--;
			int ans=0;
			for(int c=0;c<26;c++){
				int val=sum(r,c)-sum(l,c);
				if(val>0) ans++;
			}
			cout<<ans<<endl;
		}
		else{
			int x; char c;
			cin>>x>>c;
			c-='a';
			add(x,-1,s[x]);
			add(x,1,c);
			s[x]=c;
		}
	}
	return 0;
}


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

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


if __name__ == '__main__':
    data = input()
    if '7' in data:
        print("Yes")
    else:
        print("No")

    #print('\33[32m' + 'end' + '\033[0m') # debug


Measured memory_bytes: 68632
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;

public class Main {
	public static void main(final String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int l = sc.nextInt();
    List<Integer> list = new ArrayList<>();
    int sum = 0;
    int min = 1000000;
    int num = 0;

    for(int i = 0; i < n ; i++){
        list.add(l+i);
    }

    //Collections.sort(list);

    for(int i = 0; i < n ; i++){
        sum += list.get(i);
    }

    for(int i = 0 ; i < n ; i++){
        if(min > Math.abs(list.get(i))){
            min = Math.abs(list.get(i));
            num = i;
        }
    }
    if(list.get(num)<=0){
        System.out.println(sum + min);
    }else{
        System.out.println(sum - min);
    }


    
    }
    public static int getNearestValue( List<Integer> list, int v )
	{
		
		int i;		
		int num;	
		int minv;	

		
		if ( 1 >list.size() ) return -1;

		
		num = 0;
		minv = Math.abs( list.get(0) - v );
		for ( i = 1; i < list.size(); ++ i ) {
			if ( Math.abs( list.get(i) - v ) < minv ) {
				num = i;
				minv = list.get(i) - v ;
			}
		}

        return minv;
        
	}
}

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

using namespace std;

int main(void) {
  int n, m;
  cin >> n >> m;

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

  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < n - 1; j++) {
      if (a[j] % i > a[j + 1] % i) {
        swap(a[j], a[j + 1]);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    cout << a[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 3076
//OPTIMIZATONS
#pragma GCC optimize("02")
//CODE
#include<bits/stdc++.h>
// uncomment the below code to use int as long long
#define int long long
// uncomment the below code to use float as double
//#define float double
#define endl "\n"
#define debug cout<<"Good uptill here"<<endl<<flush;
#define deb(x) cout<<#x<<":"<<x<<endl<<flush;

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//CODE FOR SPECIFIED INPUT AND OUTPUT
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin>>n;
	string s;
	cin>>s;
	vector<int> r,b,g;
	for(int i=0;i<n;i++){
		if(s[i]=='R') r.push_back(i);
		else if(s[i]=='G') g.push_back(i);
		else b.push_back(i);
	}
	int ans = 0;
	//deb(r.size()); deb(g.size()); deb(b.size());
	for(auto i:r){
		for(auto j:g){
			int res = b.size();
			int k =(i+j)/2;
			int d = abs(i-j);
			if((i+j)%2==0 && s[k]=='B') res--;
			if(min(i,j)-d>=0 && s[min(i,j)-d]=='B') res--;
			if(max(i,j)+d<n && s[max(i,j)+d]=='B') res--;
			ans += res;
		}
	}
	cout<<ans<<endl;
	return 0;
}



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

int main() {
	string S,T;
	cin >>S>>T;
	int k=1;
	for(int i=0;i<S.length();i++){
		if(S.at(i)!=T.at(i)){
			k=0;
		}
	}
	if(k==1){
		cout <<"Yes";
	}
	else{
		cout <<"No";
	}
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define inf (int)1e9+7
#define eb emplace_back
#define eps 1e-10

int main() {
    int x, a; cin >> x >> a;
    if (x < a) cout << 0 << endl;
    else cout << 10 << endl;
}


Measured memory_bytes: 256
N, M, X = map(int, input().split())
C = []
A = []

for i in range(N):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])

ans = -1

for i in range(1, 1 << N):
    price = 0
    skill = [0] * M
    b = len(bin(i)) - 2
    for j in range(b):
        price += C[j] * (i >> j & 1)
        for k in range(M):
            skill[k] += A[j][k] * (i >> j & 1)

    if min(skill) >= X and (price < ans or ans < 0):
        ans = price

print(ans)


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

int main()
{
    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;
    for (int i = 0; i < a; ++i)
    {
        if (s[i] < '0' || s[i] > '9')
        {
            cout << "No";
            return 0;
        }
    }
    if (s[a] != '-')
    {
        cout << "No";
        return 0;
    }
    for (int i = a + 1; i < a + b + 1; ++i)
    {
        if (s[i] < '0' || s[i] > '9')
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;

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

const int INF = 1e9 + 7;

int a[100];

int main()
{
	IO_OP;
	
	int n, m;
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		int t;
		cin >> t;
		for(int j=0;j<t;j++) {
			int k;
			cin >> k;
			a[k]++;
		}
	}
	int ans = 0;
	for(int i=0;i<100;i++)
		if(a[i] == n) {
			ans++;
		}
	cout << ans << endl; 	
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
using namespace         std;
#define                 int long long
#define                 double long double
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<'\n'
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 1014159
#define  vi vector<int>
#define  v  vector
#define die exit(0)
#define alln(arr) arr+1 , arr+1+n
using namespace __gnu_pbds;  
typedef tree<int, null_type, less<int>, rb_tree_tag,  
            tree_order_statistics_node_update> oset; 

int n,m,k,A[N],H[N],a;
int P[N];
v<pi>B;

int get(int idx)
{
	int left = idx,right = n,ans=n;
	while(left<=right)
	{
		int mid = (left+right)/2;
		if(A[mid]-A[idx]<=k)
		{
			ans = mid;
			left = mid+1;
		}
		else right = mid-1;
	}
	return ans;
}


void solve()
{
    cin>>n>>k>>a;
    forn(i,1,n)
    {
    	int x,y;
    	cin>>x>>y;
    	y = ceil(1.0*y/a);
    	B.pb({x,y});
    }
    k*=2;
    sort(all(B));

   

    forn(i,1,n)
    {
    	A[i] = B[i-1].X;
    	H[i] = B[i-1].Y;
    }

    int ans = 0;

    forn(i,1,n)
    {
    	P[i]+=P[i-1];
    	H[i]+=P[i];
    	//cout<<i<<" "<<P[i]<<" "<<H[i]<<"\n";
    	if(H[i]>0)
    	{
    		ans+=H[i];
    		P[i]-=H[i];
    		int x = get(i);
    	//	cout<<i<<" "<<x;nl;
    		P[x+1]+=H[i];
    	}
    }

    cout<<ans;





}


signed main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
    int t = 1;
    //cin>>t;
    forn(i,1,t)
    {
        solve();
        nl;
    }



    return 0;

}

//       clang++ c.cpp ; ./a.out < a.txt ;  

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

int main() {
  char ch;
  cin >> ch;
  if(ch == 'a' || ch == 'i' || ch == 'u' || ch == 'e' || ch == 'o') {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
char s[305];
int dp[305][305][305];
int dfs(int l, int r, int x) {
    if(l >= r) {
        return r - l + 1;
    }
    if(dp[l][r][x] != -1) {
        return dp[l][r][x];
    }
    int ret = max(dfs(l + 1, r, x), dfs(l, r - 1, x));
    if(s[l] == s[r]) {
        ret = max(ret, dfs(l + 1, r - 1, x) + 2);
    } else if(x) {
        ret = max(ret, dfs(l + 1, r - 1, x - 1) + 2);
    }
    return dp[l][r][x] = ret;
}
int main() {
    memset(dp, -1, sizeof(dp)); 
    scanf("%s%d", s + 1, &k);
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; ++j) {
            ans = max(ans, dfs(i, j, k));
        }
    } 
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 111104
#include <stdio.h>

int main(void) {
	int y,i,n,d[1024][4] = {0},p,q,r,c;
	while(scanf("%d",&n) , n != 0){
		for(i = 1;i <= n;i++){
			scanf("%d%d%d%d",&d[i][0],&d[i][1],&d[i][2],&d[i][3]);
		}
		scanf("%d%d%d%d",&p,&q,&r,&c);
		y = 1;
		for(i = 1;i <= n;i++){
			if(d[i][1] <= p && d[i][2] <= q && d[i][3] <= r && (d[i][1] + d[i][3]) * 4 + d[i][2] * 9 <= c){
				printf("%d\n",d[i][0]);
				y = 0;
			}
		}
		if(y){printf("NA\n");}
	}
	return 0;
}

Measured memory_bytes: 636
a, b, c, d = map(int, input().split())
dp = [[1 for _ in range(d - b + 1)] for _ in range(c - a + 1)]

mod = 998244353
for x in range(c - a + 1):
    for y in range(d - b + 1):
        if x == 0:
            if y > 0:
                dp[x][y] = dp[x][y - 1] * (a + x) % mod
        elif y == 0:
            dp[x][y] = dp[x - 1][y] * (b + y) % mod
        else:
            dp[x][y] = (((dp[x - 1][y] * (b + y)) + (dp[x][y - 1] * (a + x))) - (dp[x - 1][y - 1] * (a + x - 1) * (b + y - 1))) % mod

print(dp[-1][-1])

Measured memory_bytes: 146736
n=int(input())
d=[]
for _ in range(n):
    a,b=map(int,input().split(" "))
    d.append([a,b])
from math import sqrt,factorial
from itertools import permutations
sum=0
for i in permutations(d,n):
    for j in range(1,n):
        c=sqrt((i[j-1][0]-i[j][0])**2+(i[j-1][1]-i[j][1])**2)
        sum+=c
print(sum/factorial(n))

Measured memory_bytes: 3064
N = int(input())
An = input().split(' ')
ball_list = [0] * N
output_list = []
count = 0
for i in range(N):
    sum_amari = sum(ball_list[(N - i -1)::(N - i)])
    if sum_amari % 2 != int(An[N - i -1]): 
        ball_list[N - i -1] = 1
        output_list.append(str(N - i))
output_list.reverse()
print(len(output_list))
if len(output_list) > 0:
    print(' '.join(output_list))

Measured memory_bytes: 17296
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    b = [0] * n
    c = [0] * n

    score1 = 0
    cur = 0
    for i, x in enumerate(a):
        if i % 2 == 0:
            nx = x + cur
            if nx <= 0:
                diff = abs(nx) + 1
                score1 += diff
                cur = 1
            else:
                cur = nx
        else:
            nx = x + cur
            if nx >= 0:
                diff = abs(nx) + 1
                score1 += diff
                cur = -1
            else:
                cur = nx

    score2 = 0
    cur = 0
    for i, x in enumerate(a):
        if i % 2 == 1:
            nx = x + cur
            if nx <= 0:
                diff = abs(nx) + 1
                score2 += diff
                cur = 1
            else:
                cur = nx
        else:
            nx = x + cur
            if nx >= 0:
                diff = abs(nx) + 1
                score2 += diff
                cur = -1
            else:
                cur = nx

    print(min(score1, score2))


if __name__ == '__main__':
    main()


Measured memory_bytes: 86676
#include <bits/stdc++.h>
using namespace std;
 
#define N 100010
int n, a[N];
 
int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        sort(a + 1, a + 1 + n);
        int mid = n / 2;
        if (a[mid] == a[mid + 1]) {
            puts("0");
        } else {
            printf("%d\n", a[mid + 1] - a[mid]);
        }
    }
    return 0;
}

Measured memory_bytes: 640
h,w,a,b=map(int,input().split())
l=[['0' for i in range(w)] for j in range(h)]
if b==0:
  for i in range(h):
    for j in range(w):
      if j<a:
        l[i][j]='1'
elif a==0:
  for i in range(h):
    if i<b:
      for j in range(w):
        l[i][j]='1'
else:
  for i in range(h):
    if i<b:
      for j in range(w):
        if j<a:
          l[i][j]='1'
    else:
      for j in range(w):
        if j>=a:
          l[i][j]='1'
for i in range(h):
  print(''.join(l[i]))

Measured memory_bytes: 12788
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}

	Scanner cin;

	const int MOD = 1000000007;
	const int INF = int.MaxValue - 10;
	const long INFL = long.MaxValue - 10;
	const double EPS = 1e-8;
	const double PI = 3.1415926536;
	int[,] dir8;
	int[,] dir4;



	void prog()
	{
		cin = new Scanner();
		dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
		dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

		long I = cin.nextInt();
		long O = cin.nextInt();
		int T = cin.nextInt();
		long J = cin.nextInt();
		long L = cin.nextInt();
		long ans1 = O;
		long ans2 = O;
		ans1 += (I / 2) * 2 + (J / 2) * 2 + (L / 2) * 2;
		if (I >= 1 && J >= 1 && L >= 1)
		{
			I--;
			J--;
			L--;
			ans2 += 3 + (I / 2) * 2 + (J / 2) * 2 + (L / 2) * 2;
		}
		Console.WriteLine(Math.Max(ans1, ans2));
	}
}

class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		i = 0;
		return next();
	}

	public int nextInt()
	{
		return int.Parse(next());
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}
}

Measured memory_bytes: 2904
use std::io::stdin;
use std::str::FromStr;

fn main(){
    let (n, k): (i64, i64) = get_pair();
    let ans = if (n + 1) / 2 >= k {
        "YES"
    } else {
        "NO"
    };
    println!("{}", ans);
}

#[allow(dead_code)]
fn get_line() -> String {
    let mut s = String::new();
    match stdin().read_line(&mut s){
        Ok(_) => {s.trim().to_string()}
        Err(_) => String::new()
    }
}

#[allow(dead_code)]
fn get_vec<T: std::str::FromStr>() -> Vec<T> {
    let line = get_line();
    line.split_whitespace().filter_map(|x| x.parse().ok()).collect()
}

#[allow(dead_code)]
fn get_one<T: FromStr + Copy>() -> T {
    let v = get_vec();
    v[0]
}

#[allow(dead_code)]
fn get_pair<T: FromStr + Copy>() -> (T, T) {
    let v = get_vec();
    (v[0], v[1])
}

#[allow(dead_code)]
fn get_triple<T: FromStr + Copy>() -> (T, T, T) {
    let v = get_vec();
    (v[0], v[1], v[2])
}

#[allow(dead_code)]
fn get_chars() -> Vec<char> {
    get_line().chars().collect()
}


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

using namespace std;

int read() {
  int res = 0, w = 1; char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), w = -1;
  while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();
  return res * w;
}

const int N = 1e5 + 10;

#define NO {puts("No"); exit(0);}
#define YES {puts("Yes"); exit(0);}

int deg[N];
vector<int> g[N];

void dfs(int u, int fa, int x, int y) {
  for (auto v : g[u]) {
    if (v == fa || v == y) continue;
    if (v == x) YES;
    dfs(v, u, x, y);
  }
}

int main() {
  int n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    int u = read(), v = read();
    deg[u]++, deg[v]++;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int cnt = 0, x = 0, y = 0;
  for (int i = 1; i <= n; i++) if (deg[i] & 1) NO
  for (int i = 1; i <= n; i++) {
    if (deg[i] > 4) YES
    if (deg[i] == 4) {
      cnt++;
      if (x) y = i;
      else x = i;
    }
  }
  if (cnt > 2) YES
  if (cnt < 2) NO
  dfs(x, 0, x, y);
  NO
  return 0;
}


Measured memory_bytes: 7680
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<iterator>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	double coins[n];
	int i,j;
	for(i=0; i<n; i++)
	{
		double p;
		cin>>p;
		coins[i]=p;
	}
	double dp[n+1][n+1];
	for(i=0; i<=n; i++)
	{
		for(j=0; j<=n; j++)
		{
			dp[i][j]=0;
		}
	}
	dp[0][0]=1;
	for(i=1; i<=n; i++)
	{
		dp[i][0]=dp[i-1][0]*(1-coins[i-1]);
	}
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			dp[i][j]=dp[i-1][j-1]*coins[i-1]+dp[i-1][j]*(1-coins[i-1]);
		}
	}
	double ans=0;
	for(j=0; j<=n; j++)
	{
		if(j>n/2)
		{
			ans+=dp[n][j];
		}
	}
	cout<<fixed<<setprecision(12)<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 70656
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = map(int,input().split()) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
edges = []
for i in range(m):
    u, v, w = map(int,input().split())
    d[u-1][v-1] = w
    d[v-1][u-1] = w
    edges.append((u-1,v-1))
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

fwd = warshall_floyd(d)   #d[i][j]に頂点i, j間の最短距離を格納

ret = 0
for u,v in edges:
    if fwd[u][v] < d[u][v]:
        ret += 1
print(ret)


Measured memory_bytes: 9776
//https://atcoder.jp/contests/dp/tasks/dp_c
//29-02-2020
#include <bits/stdc++.h>
using namespace std;

const int max_n = 100001;
long long dp[max_n][3], act[max_n][3];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // #ifndef ONLINE_JUDGE
  // freopen ("input.txt", "r", stdin);
  // freopen ("output.txt", "w", stdout);
  // #endif 
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> act[i][0] >> act[i][1] >> act[i][2];
  }

  dp[0][0] = act[0][0];
  dp[0][1] = act[0][1];
  dp[0][2] = act[0][2];

  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        if (k != j)
          dp[i][j] = max (dp[i][j], dp[i - 1][k] + act[i][j]);
      }
    }
  }
  long long ans = 0;
  for (int i = 0; i < 3; ++i) {
    ans = max (ans, dp[n - 1][i]);
  }
  cout << ans << '\n';
}

Measured memory_bytes: 4992
N = int( input())
B = list( map( int, input().split()))
C = [0]*(N+1)
ans = 0
for i in range(N):
    if B[i] > i+1:
        ans = -1
        break
ANS = []
if ans == 0:
    for i in range(1, N+1):
        L = []
        for j in range(N):
            if 1 <= B[j] <= i:
                L.append(B[j])
        now = i-1
        for s in L[::-1]:
            if s == i:
                ANS.insert(now,i)
            now += 1
if ans == -1:
    print(-1)
else:
    for i in range(N):
        print(ANS[i])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> PP;

struct edge {
	int to,cost;
	edge(int t,int c):to(t),cost(c) {}
};

int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int ddx[]={1,1,1,0,-1,-1,-1,0},ddy[]={1,0,-1,-1,-1,0,1,1};

ll mypow(ll x,ll n,ll m) {	//xのn乗をmで割った余り
	if(n==0) return 1;
	if(n%2==0) return mypow(x*x%m,n/2,m);
	else return x*mypow(x,n-1,m)%m;
}

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

int x,a,b;

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

	cin>>x>>a>>b;
	if(a-b>=0) cout<<"delicious"<<endl;
	else if(a+x-b>=0) cout<<"safe"<<endl;
	else cout<<"dangerous"<<endl;

	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <queue>

using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
int const inf = 1e9;
#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,b) loop(i,0,b)
#define iter(it,c) for(auto it=c.begin(); it!=c.end(); ++it)
#define all(c) (c).begin(), (c).end()

typedef int Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
        src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

// Dijkstra法で1対多の最短経路を求める
// gは隣接リスト表現のグラフ，sは始点
// distに各頂点までの距離，prevに最短経路である頂点の1つ手前の頂点
void dijk(Graph const&g, int s, vector<Weight> &dist, vi &prev) {
    int n = g.size();
    dist.assign(n, inf); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> q; // "e < f" <=> "e.weight > f.weight"
    q.push(Edge(-2, s, 0));
    while (q.size()) {
        Edge e = q.top();
        q.pop();
        if (prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        iter(f, g[e.dst]) {
            if (dist[f->dst] > e.weight + f->weight) {
                dist[f->dst] = e.weight + f->weight;
                q.push(Edge(f->src, f->dst, e.weight + f->weight));
            }
        }
    }
}

// 経路復元
// prevはダイクストラ法で求めた手前の頂点，tは終点
vi buildPath(vi const& prev, int t) {
    vi path;
    for (int u = t; u >= 0; u = prev[u])
        path.push_back(u);
    reverse(all(path));
    return path;
}

inline bool in(int x, int y, int h, int w){
    return 0 <= x && 0 <= y&&y < h&&x < w;
}

int main(){
    int w, h;
    while (cin >> w >> h && w | h){
        cin.ignore();
        vector<string> gs(h * 2 - 1);
        rep(i, h * 2 - 1){
            getline(cin, gs[i]);
            gs[i].resize(w * 2 - 1, ' ');
        }

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

        Graph g(h*w);
        for (int y = 0; y < gs.size(); y += 2){
            for (int x = 0; x < gs[0].size(); x += 2){
                for (int d = 0; d < 4; d++){
                    int bx = x + dx[d];
                    int by = y + dy[d];
                    if (!in(bx, by, gs.size(), gs[0].size())) continue;
                    if (gs[by][bx] == '0'){
                        int nx = bx + dx[d];
                        int ny = by + dy[d];

                        int v1 = x / 2 + y / 2 * w;
                        int v2 = nx / 2 + ny / 2 * w;
                        g[v1].push_back(Edge(v1, v2, 1));
                        g[v2].push_back(Edge(v2, v1, 1));
                    }
                }
            }
        }

        vi dist, prev;
        dijk(g, 0, dist, prev);
        int d = dist.back();
        if (d == inf) cout << 0 << endl;
        else cout << d + 1 << endl;
    }
}

Measured memory_bytes: 1340
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int

struct Union{
  vector<ll> par;
  Union(ll a){
  par=vector<ll>(a,-1);
  }
  ll find(ll a){
    if(par[a]<0){
      return a;
    }
    else{
      return par[a]=find(par[a]);
    }
  }
  bool same(ll a,ll b){
    return (find(a)==find(b));
  }
  ll size(ll a){
    return -par[find(a)];
  }
  void unite(ll a,ll b){
    ll c=find(a),d=find(b);
    if(c==d)
      return;
    if(size(c)<size(d)){
      swap(c,d);
    }
    par[c]+=par[d];
    par[d]=c;
  }
};
ll Nagaemon1;
void swap(ll i,ll j){
  Nagaemon1=i;
  i=j;
  j=Nagaemon1;
}
int main(){
  int a,b,c,d,e;
  cin >> a >> b >> c >> d >> e;
  cout << (c-a)*60+d-b-e << endl;

}

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

int main(int argc, char* argv[]){
    int X, ans = 1;
    cin >> X;
    vector<int> v;

    if(X == 1){
        cout << 1 << endl;
        return 0;
    }
    rep(i, 33){
        for(int j = 2; j < 10; j++){
            int tmp = pow(i, j);
            if(tmp <= 1000){
                if(tmp > ans && tmp <= X) ans = tmp;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<pll> sushies;// おいしさ、ネタIDの順
    for (int i = 0; i < N; i++)
    {
        ll T, D;
        cin >> T >> D;
        sushies.emplace_back(D, T);
    }
    sort(sushies.begin(), sushies.end(), greater<pll>());
    //初め貪欲にとる
    ll typeNum = 0;
    ll basicPoint = 0;
    vector<ll> typeCount(N + 1, 0);
    vector<pll> currentSushies(0);
    for(int i = 0; i < K; i++)
    {
        pll sushi = sushies.at(i);
        ll point, type;
        tie(point, type) = sushi;
        if(typeCount.at(type) == 0)
        {
            typeNum++;
        }
        typeCount.at(type)++;
        currentSushies.push_back(sushi);
        basicPoint += point;
    }
    ll answer = basicPoint + typeNum * typeNum;
    //1種類ずつ可能なラインまで増やし、既存の最高値を超えたら更新
    int checkIndex = K;
    int currentSushiIndex = K - 1;
    for(int i = typeNum + 1; i <= K; i++)
    {
        //貪欲で保持した寿司から種類数を崩さないように一個除去(必ず見つかる見込み)
        while(true)
        {
            pll sushi = currentSushies.at(currentSushiIndex);
            currentSushiIndex--;
            ll point, type;
            tie(point, type) = sushi;
            if(typeCount.at(type) == 1)
            {
                continue;
            }
            typeCount.at(type)--;
            basicPoint -= point;
            break;
        }
        //他の種類の寿司を追加
        while(checkIndex < N)
        {
            pll sushi = sushies.at(checkIndex);
            ll point, type;
            tie(point, type) = sushi;
            if(typeCount.at(type) > 0)
            {
                checkIndex++;
                continue;
            }
            typeCount.at(type)++;
            typeNum++;
            basicPoint += point;
            checkIndex++;
            break;
        }
        //状況次第でcheckIndex == Nでsushiが一個removeされたのみで来ることがあるが
        //maxより少なくなるため問題ない
        answer = max(answer, basicPoint + typeNum * typeNum);
        if(checkIndex == N)
        {
            //これ以上種類を増やせない
            break;
        }
    }

    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 5744
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define ll long long






int main() {



	ll n, we;
	cin >> n >> we;

	vector<ll> a(n + 1), w(n + 1);

	for (ll i = 1; i < n + 1; i++) {
		cin >> w[i] >> a[i];
	}


	ll dp[n + 1][we + 1];
	for (ll i = 0; i <= we; i++) {
		dp[1][i] = 0;
	}
	dp[1][w[1]] = a[1];

	for (ll i = 2; i <= n; i++) {

		for (ll j = 0; j <= we; j++) {

			dp[i][j] = dp[i - 1][j];
			if (w[i] > j) continue;

			dp[i][j] = max(dp[i][j], a[i] + dp[i - 1][j - w[i]]);

		}
	}

	cout << *max_element(dp[n], dp[n] + we + 1);

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





}

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

int main(){
  int n;
  cin >> n;
  vector<int64_t> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  int64_t nside = a.at(n-1);
  int64_t rside = -1;
  for(int i=0;i<n-1;i++){
    if(rside == -1){
      rside = a.at(i);
    }else if(abs( ( (double)nside/2)-a.at(i)) < abs( ( (double)nside/2) - rside) ){
      rside = a.at(i);
    }
   // cout << abs((double)nside/2 - a.at(i))<< ",";
  }
  cout << nside << " " << rside << endl;
}
    
    

Measured memory_bytes: 1024
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

typedef long long ll;

const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

typedef vector<int> vi;
typedef pair<int, int> pi;

#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define ALL(v) (v).begin(), (v).end()

int main(){
  int a,b;
  scanf("%d %d",&a, &b);
  int c=a+b;
  if(c>=10)
    printf("error\n");
  else
    printf("%d\n",c);
  

  return 0;
}


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

int main(){
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n+1, 0);
    vector<ll> b(m+1, 0);
    for(int i=1; i<=n; i++){
        cin >> a[i]; 
        a[i] += a[i-1];
    }
    for(int i=1; i<=m; i++){
        cin >> b[i];
        b[i] += b[i-1];
    }
    ll ans = 0, j = m;
    for(ll i=0; i<=n; i++){
        if(a[i] > k) continue;
        while(b[j] > k - a[i]) j-=1;
        ans = max(ans, i+j);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6412
import sys
from collections import Counter, deque, defaultdict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
sumlist = [(0,0)]*n
res = 0
for i in range(n):
    aa,bb = MAP()
    sumlist[i] = (aa, bb)

sumlist = sorted(sumlist, key = lambda x:x[0]+x[1], reverse = True)
for i in range(n):
    res += (-1)**i * sumlist[i][i%2]

print(res)
    

Measured memory_bytes: 74712
/*
 * atcoder/abc161/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

ll N, K;

void input() {
  cin >> N >> K;
}

void solve() {
  if (N%K == 0) {
    cout << 0 << endl;
    return;
  }

  cout << min((N%K), abs((N%K) - K)) << endl;
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>

#define INF 100000000
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

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

    if((a+b)%2 == 0){
        cout << (a+b)/2 << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
}



Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include <iomanip> // setprecisionを使用するのに必要
using namespace std;
#define PI 3.141592653589

int main(void){
    long double a, b, h, m;

    cin >> a >> b >> h >> m;

    long double hx, hy, mx, my;

    hx = a * sin(2 * PI * (h+(m/60))/12);
    //cout << "hx=" << hx << endl;
    hy = a * cos(2*PI*(h+(m/60))/12);
    //cout << hy << endl;
    mx = b * sin(2*PI*m/60);
    //cout << mx << endl;
    my = b * cos(2*PI*m/60);
    //cout << "my=" << my << endl;

    //double diffx = mx-hx;
    //double diffy = my-hy;


    long double dif;
    //dif = sqrt((diffx*diffx) + (diffy*diffy));
    dif = hypot(hx-mx, hy-my);
    cout << fixed << setprecision(10) << dif << endl;

}

Measured memory_bytes: 4180
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 19;
int n, F[N];
char A[N];
int main()
{
    scanf("%d%s", &n, &A);
    for (int i = 0; i < n; i ++)
        A[i] -= '1';
    for (int i = 1; i <= n; i ++)
        F[i] = F[i - 1] + __builtin_ctz(i);
    int Pr = 0;
    for (int i = 0; i < n; i ++)
        if (A[i] == 1 && F[n - 1] - F[i] - F[n - 1 - i] == 0)
            Pr ^= 1;
    if (Pr) return !printf("1\n");
    for (int i = 0; i < n; i ++)
        if (A[i] == 1)
            return !printf("0\n");
    for (int i = 0; i < n; i ++)
        A[i] /= 2;
    Pr = 0;
    for (int i = 0; i < n; i ++)
        if (A[i] == 1 && F[n - 1] - F[i] - F[n - 1 - i] == 0)
            Pr ^= 1;
    if (Pr) return !printf("2\n");
    return !printf("0\n");
}

Measured memory_bytes: 5120
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	void doIt() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		System.out.println(n - k + 1);
	}


	public static void main(String[] args) {
		new Main().doIt();
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
typedef long long ll;

int N,M,H,W,K,A,B;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
    cin>>N>>M;
    vector<ll> a(N,0);
    vector<pair<ll,ll> > cb(M,pair<ll,ll>(0,0));
    rep(i,N) cin>>a.at(i);
    rep(i,M) cin>>cb.at(i).se>>cb.at(i).fi;
    sort(a.begin(),a.end());
    sort(cb.begin(),cb.end());
    reverse(cb.begin(),cb.end());
    int card = 0;
    bool fin = false;
    rep(i,M){
        rep(j,cb.at(i).se){
            if(card == N){
                fin = true;
                break;
            }
            if(a.at(card) > cb.at(i).fi) {
                fin = true;
                break;
            }
            a.at(card) = cb.at(i).fi;
            card++;
        }
        if(fin) break;
    }
    ll ans = 0;
    rep(i,N) ans += a.at(i);
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
//Burn It Dowwwnnnnn.....................
#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
long long int MX=1e18;
long long int MN=-MX;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long int i,j,k,l,a,b,c,d,q,s,n,m,o,p,tc=1,jj,z;
//    cin>>tc;
    for(jj=0; jj<tc; jj++)
    {
        vector<long long int>vv;
        string aa;
        map<long long int,long long int>uu;
        cin>>aa;
        for(i=0;i<aa.size(); i++)
        {
            if(aa[i]=='?')
            {
                if(i>0 && aa[i-1]=='P')
                {
                    aa[i]='D';
                }
                else if(i<aa.size()-1 &&aa[i+1]=='D')
                {
                    aa[i]='P';
                }
                else if( aa.size()-1  && aa[i+1]=='?')
                {
                    aa[i]='P';
                }
                else
                {
                    aa[i]='D';
                }

            }
        }
        cout<<aa<<endl;


    }
}



Measured memory_bytes: 3748
#include <bits/stdc++.h>
typedef long long ll;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 1 << 30;
const ll INFll = 1ll << 60;
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main() {
  int N, K;
  string S;
  cin >> N >> S >> K;
  char target = S[K - 1];
  for (int i = 0; i < N; i++) {
    if (S[i] != target) S[i] = '*';
  }

  cout << S << endl;
  return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
S = ['.'+input()+'.' for _ in range(h)]
S = ['.'*(w+2)] + S + ['.'*(w+2)]
flag = False
for i in range(1, h+1):
    for j in range(1, w+1):
        if S[i][j] == '.':
            continue
        if S[i-1][j] != '#' and S[i][j-1] != '#' and S[i][j+1] != '#' and S[i+1][j] != '#':
            flag = True
print('No' if flag else 'Yes')


Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <map>

#define ST_ARR_LEN(array) (sizeof(array)/sizeof(*array))

using namespace std;

using ll = long long;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;
typedef vector<int> IntVector;
typedef list<int> IntList;

typedef struct S{
  int a;
  int b;
} Object;

int main(){
  int N;
  cin >> N;
  int P[N];
  for(int i=0;i<N;i++){
    cin >> P[i];
  }
  
  int ans = 1;
  int min_number = P[0];
  for(int i=1;i<N;i++){
    if(P[i] <= min_number){
      ans++;
      min_number = P[i];
    }
  }
  
  
  
  cout << ans << endl;
}

Measured memory_bytes: 1024
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]
#a = [int(input()) for _ in range(n)]

s = input()

if s[0] == s[2]:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9008
in_len = input().split(" ")

in_h = int(in_len[0])
in_n = int(in_len[1])
in_a = input().split(" ")

for i in range(in_n):
  in_h -= int(in_a[i])

if(in_h <= 0):
  print("Yes")
else:
  print("No")

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


int main()
{
  int n;
  cin >> n;
  map<int, int> mp;
  ll s = 0;
  rep(i, n)
  {
    int a;
    cin >> a;
    s += a;
    mp[a]++;
  }
  int q;
  cin >> q;
  rep(i, q)
  {
    int b, c;
    cin >> b >> c;
    s += -mp[b] * b + mp[b] * c;
    printf("%lld\n", s);
    mp[c] += mp[b];
    mp[b] = 0;
  }
  return 0;
}

Measured memory_bytes: 8004
#include <iostream>

int main() {
  int a, b;
  std::cin >> a >> b;
  int cnt = 0;
  for (int mm = 1; mm <= 12; ++mm)
    for (int dd = 1; dd <= 31; ++dd) {
      if (mm == dd) ++cnt;
      if (mm == a && dd == b) std::cout << cnt << "\n";
    }
}

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

int main(void){
  int i, j, n, len;
  char f[200]={}, p[200], q[200], r[200];
  char *ptrf=f, *ptrp=p;

  while(1){
    scanf("%s", f);
    if(strcmp(f, "-") == 0) break;
    len = strlen(f);
    f[len] = '\0';
    scanf("%d", &len);
    for(i=0;i<len;i++){
      scanf("%d", &n);
      for(j=0;j<n;j++) *ptrp++ = *ptrf++;
      *ptrp = '\0';
      strcpy(q,ptrf);
      strcpy(r, q);
      strcat(q, p);
      strcpy(f, q);
      strcpy(q, r);
      ptrf=f;
      ptrp=p;
    }
    printf("%s\n", f);
  }
  return 0;
}



Measured memory_bytes: 2068
n,m=map(int,input().split())
p=10**9+7
if abs(n-m)>=2:
    print(0)
elif n==m:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%p
    print((2*ans*ans)%p)
else:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%p
    for i in range(1,m+1):
        ans=(ans*i)%p
    print(ans%p)


Measured memory_bytes: 9092
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
int main()
{
    int a,b,c,d,x,y;
    string S;
    cin>>S;
    
    int num = stoi(S);
    d = num%10;
    num = num/10;
    
    c = num%10;
    num = num/10;
    
    b = num%10;
    num = num/10;
    
    a = num%10;
    num = num/10;
    
    x = a*10 +b;
    y = c*10 + d;
    
    if(x<=12 && y<=12 && y>0 && x>0)
   { cout<<"AMBIGUOUS";
     return 0;
   }
    
    if(x>12 && y<=12 && y>0)
    { cout<<"YYMM";
     return 0;
   }
    
    if(x<=12 && y>12 && x>0)
  { cout<<"MMYY";
     return 0;
   }
    
    if(x>12 && y>12 || x==0 && y>12 || x>12 && y==0 || x==0 && y==0 )
   { cout<<"NA";
     return 0;
   }
   
   if(x==0 && y<=12 && y>0)
   {
       cout<<"YYMM";
       return 0;
   }
   
   if(y==0 && x<=12 && x>0)
   {
       cout<<"MMYY";
       return 0;
   }
    return 0;
    
    
    
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class BCraneAndTurtle {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int X, Y;
        cin >> X >> Y;
        FOR(i, 0, X) {
            int j = X - i;
            if (2 * i + 4 * j == Y) {
                cout << "Yes" << endl;
                return;
            }
        }
        cout << "No" << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    BCraneAndTurtle solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,1};
const int dy[6] = {0, 1, 0, -1,1,-1};
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(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H,W,K;
    cin >> H >> W >> K;
    vector<string> G(H);
    for(int i=0; i<H; i++){
        cin >> G[i];
    }
    int ans = 0;
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            bool okh=true,okw=true;
            for(int k=0; k<K; k++){
                if(i+k>=H or G[i+k][j] == '#') okh = false;
                if(j+k>=W or G[i][j+k] == '#') okw = false;
            }
            if(okh){
                ans++;
            }
            if(okw){
                ans++;
            }
        }
    }
    cout << ans << enld;
    return 0;
}


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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import deque

N = int(input())
S = input()

ans = deque()
tmp = ''
l = r = 0
for c in S:
    if c == '(':
        l += 1
        tmp += '('
    else:
        if l == 0:
            ans.appendleft('(')
            ans.append(')')
        else:
            r += 1
            tmp += ')'
            if l == r:
                ans.append(tmp)
                tmp = ''
                l = r = 0
if l > r:
    tmp += ')' * (l-r)
    ans.append(tmp)
print(''.join(ans))


Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
    int R[MAX], n;

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

    int result=-1000000001;
    int min = 1000000001;
    int sub = -1000000001;
    for(int i = 0; i<n; i++) {
        if (i>=1) {
            sub = R[i] - min;
        }
        if (R[i]<min) {
            min = R[i];
        }
        if (sub > result) {
            result = sub;
        }
    }

    cout << result << endl;

    return 0;
}
    

Measured memory_bytes: 1940
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ll N;
    cin >> N;
    ll ans = N * (N - 1) / 2;
    //ans -= N / 2;
    //ans += N % (N / 2 + 1);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
cs=set(s)
a=0
for c in cs:
    if a<s.count(c)-t.count(c):
        a=s.count(c)-t.count(c)
print(a)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
	cin>>s;
	if(s[0]=='S'&&s[1]=='U') printf("7");
	else if(s[0]=='M') printf("6");
	else if(s[0]=='T'&&s[1]=='U') printf("5");
	else if(s[0]=='W') printf("4");
	else if(s[0]=='T') printf("3");
	else if(s[0]=='F') printf("2");
	else printf("1");
	return 0;
}

Measured memory_bytes: 256