akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf  = 1e6+5;
vector<int> freq (5);
int main() {
  int a,b,c; cin >> a >> b >> c;
  if (a + b + c == 17){
      cout << "YES";
  }
  else{
      cout << "NO";
  }
}

Measured memory_bytes: 384
#include <stdio.h>
int ruijou(int);
int ruijou(int n){
  int sum=1, i;

  for(i=0;i<n;i++){
    sum*=10;
  }
  return sum;
}
main(){
  char data[10], data1[10];
  int i, p=0, temp, c=0, l,data2,a;
  
  while(1){
    if(scanf("%d", &data2)==EOF) break;
    /*for(i=0;i<10;i++){
      data[i]='0';
      data1[i]='0';
    }
    for(i=0;i<6;i++){
      if(scanf("%c", &data1[i])==EOF){
	p=1;
      }
      if(data1[i]=='\n'){
        temp=i;
        break;
      }
      if(p==1) break;
    }
    if(p==1 && i==0) break;
    else if(temp==0) continue;
    else{
      for(i=0;i<temp;i++){
	data[i+5-temp]=data1[i];
	}*/
      if(c==1) printf("\n");
      c=1;
      /*
      for(i = 0; i < 5; i++) {
	if((data[i]-'0')>= 5) printf(" ");
	else printf("*");
      }
      printf("\n");
      for(i = 0; i < 5; i++) {
	if((data[i]-'0') >= 5) printf("*");
	else printf(" ");
      }
      
      printf("\n");
      printf("=====\n");
      
      for(l = 0; l < 5; l++) {
	for(i = 0; i < 5; i++) {
	  if((data[i]-'0') % 5 == l) printf(" ");
	  else printf("*");
	}
	printf("\n");
      }
      }*/
      for(i = 4; i>=0; i--) {
	a=data2 / ruijou(i)%10;
	if(a>=5) printf(" ");
	else printf("*");
      }
      printf("\n");
      for(i = 4; i>=0; i--) {
	a=data2 / ruijou(i)%10;
	if(a>=5) printf("*");
	else printf(" ");
      }
      
      printf("\n");
      printf("=====\n");
      
      for(l = 0; l < 5; l++) {
	for(i = 4; i>=0; i--) {
	  a=data2 / ruijou(i)%10;
	  if(a%5 == l) printf(" ");
	  else printf("*");
	}
	printf("\n");
      }

  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int search(int A[], int n, int key) {
    int i = 0;
    A[n] = key;
    while (A[i] != key) i++;
    return i != n;
}

int main() {
    int i, n, A[10000 + 1], q, key, sum = 0;
    
    scanf("%d", &n);
    for (i = 0; i < n; i++) scanf("%d", &A[i]);
    
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &key);
        if (search(A, n, key)) sum++;
    }
    printf("%d\n", sum);
    
    return 0;
}


Measured memory_bytes: 2140
#include <iostream>
#include <string>
using namespace std;
int main(){
	string s;
	int i,j,k,sum,max;
	cin>>s;
    for(i=0;i<s.length();i++)
    	if(s[i]=='C')
    		for(j=i+1;j<s.length();j++)
    		if(s[j]=='F'){
			cout<<"Yes"<<endl;
    		return 0;
			}
			cout<<"No"<<endl;
}

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


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

  int n,c,k;
  cin >> n >> c >> k;
  vector<int> t(n);  
  rep(i,n) cin >> t[i];
  sort(t.begin(),t.end());
  int cnt=0;
  int tl;
  int ans=0;
  rep(i,n){
    if(cnt==0){
      tl = t[i]+k;
      cnt++;
    }
    else if(tl<t[i]){
      ans++;
      cnt=1;
      tl = t[i]+k;
    }
    else{
      cnt++;
    }
    if(cnt==c){
      ans++;
      cnt=0;
    }
    //    cout << "ans cnt " << ans  << " " << cnt << endl;
  }
  if(cnt>0) ans++;
  cout << ans << endl;
  
  return 0;
    

}


Measured memory_bytes: 640
import math
s = input().rstrip().split(' ')
a = int(s[0])
b = int(s[1])
by = 0
sq = 0
if b < 10:
	by = a * 10 + b
elif 10 <= b and b < 100:
	by = a * 100 + b
else:
	by = a * 1000 + b
sq = math.sqrt(by)
res = str(sq)

if res[-1] == "0":
	print("Yes")
else:
	print("No")

Measured memory_bytes: 3064
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long int;

int main() {
  ll N, K;
  cin >> N >> K;

  vector<ll> R(N);
  for (size_t i = 0; i < N; i++) {
    cin >> R[i];
  }

  ll mn = INT_MAX;
  for (size_t i = 0; i <= N - K; i++) {
    if (R[i] < 0 && R[i + K - 1] > 0) {
      mn = min(mn, R[i + K - 1] - R[i] + min(abs(R[i + K - 1]), abs(R[i])));
    }
  }

  if (mn == INT_MAX) {
    ll ans = 0;
    ll cnt = 0;
    if (R[N - 1] > 0) {
      for (size_t i = 0; i < N; i++) {
        if (cnt == K - 1) {
          ans = R[i];
          break;
        } else {
          cnt++;
        }
      }

    } else {
      for (int i = N - 1; i >= 0; --i) {
        if (cnt == K - 1) {
          ans = abs(R[i]);
          break;
        } else {
          cnt++;
        }
      }
    }
    cout << ans << endl;
  } else {
    cout << mn << endl;
  }
}

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

// macros
#define overload_rep(_1, _2 ,_3 ,name, ...) name
#define re_p(i, n) for(int i = 0; i < (n); ++i)
#define r_ep(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep(...) overload_rep(__VA_ARGS__, r_ep, re_p)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
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; }
void debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// AtCoder Beginner Contest 143
int main(){

    int N;
    string S;
    cin >> N >> S;
    S.push_back('*');
    int cnt = 0;
    rep(i, N){
        if(S[i] != S[i + 1])cnt++;
    }
    cout << cnt << endl;

}

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

using namespace std;
using ll = long long;

int main() {
    ll n, m; cin >> n >> m;
    ll sum = 0;
    for (int i = 0; i < m; i++) {
        ll x; cin >> x;
        sum += x;
    }

    n -= sum;
    if (n < 0) n = -1;
    cout << n << endl;
}

Measured memory_bytes: 3600
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	map<string,int>Rm,Bm;
	set<string>rr;
	int R,B;
	cin>>R;
	for(int i=0;i<R;i++)
	{
		string s;
		cin>>s;
		Rm[s]++;
		rr.insert(s);
	}
	cin>>B;
	for(int i=0;i<B;i++)
	{
		string s;
		cin>>s;
		Bm[s]++;
	}
	int res=0;
	for(string s : rr)
	{
		res=max(res,Rm[s]-Bm[s]);
	}
	printf("%d\n",res);
}


Measured memory_bytes: 256
/**
*	created: 11.09.2020 19:08:13
**/
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
using ll = long long;
using P = pair<int,int>;
// #define endl '\n'
#define int long long
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define rrep(i,n) for (int i = (int)(n - 1); i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1ll << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;
template<typename T> inline bool chmax(T &a, T &b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T> inline bool chmin(T &a, T &b) {if (b < a) {a = b; return 1;} return 0;}
template<typename T> T pow(T a, ll n) {T r(1); while(n) {if (n & 1) r *= a; a *= a; n >>= 1;} return r;}
struct faster_io {faster_io() {cin.tie(0); ios_base::sync_with_stdio(false);}} faster_io_;

// Dijkstra's Algorithm
struct edge {int to, cost;};

struct graph {
    int n;
    vector<vector<edge>> G;
    vector<int> d, pre;
    graph(int i) : n(i), G(i), d(i,INF), pre(i) {}
    void add_edge(int s, int t, int cost) {
        edge e; e.to = t; e.cost = cost;
        G[s].push_back(e);
    }
    void dijkstra(int s) {
        rep(i,n) {d[i] = INF; pre[i] = 0;}
        d[s] = 0;
        priority_queue<P, vector<P>, greater<P>> que;
        que.push(P(0,s));
        while(!que.empty()){
            P p = que.top(); que.pop(); int v = p.second;
            if(d[v] < p.first) continue;
            for(auto e : G[v]) if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost; pre[e.to] = v;
                que.push(P(d[e.to],e.to));
            }
        }
    }
};
int dist[220][220]; // dist[i][j] : iからjまでの最短距離

signed main() {
    int n, m, r; cin >> n >> m >> r;
    graph g(n);
    vector<int> v(r);
    rep(i,r) {cin >> v[i]; v[i]--;}
    sort(all(v));
    rep(i,m) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        g.add_edge(a,b,c);
        g.add_edge(b,a,c);
    }
    rep(i,r) {
        g.dijkstra(v[i]);
        rep(j,r) dist[v[i]][v[j]] = g.d[v[j]];
    }
    int ans = INF;
    do {
        int tmp = 0;
        rep(i,r-1) tmp += dist[v[i]][v[i+1]];
        chmin(ans,tmp);
    } while(next_permutation(all(v)));
    cout << ans << endl;
    return 0;
}

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

# In[14]:


N = int(input())
sp = []
for i in range(N):
    S,P = input().split()
    P = int(P)
    sp.append([i]+[S]+[P])


# In[16]:


mylist = sorted(sp, key=lambda x: x[2], reverse=True)
mylist = sorted(mylist, key=lambda x: x[1])
for i in range(len(mylist)):
    print(mylist[i][0]+1)


# In[ ]:






Measured memory_bytes: 9172
#include<stdio.h>
int main()
{
  int a,b;
  scanf("%d %d",&a,&b);
    if((a+b)%2==0){
      printf("%d",(a+b)/2);
    }
  else{
      printf("%d",(a+b)/2+1);
    }
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
static const int64_t mod=1000000007;
int64_t f(int64_t x,int64_t y){
if(y==0)
  return 1;
  else{
  if(y%2==0){
   return (f(x,y/2)*f(x,y/2))%mod;
  }else{
   return (((x*f(x,y/2))%mod)*f(x,y/2))%mod;
  }
  }
}
int64_t comb(int64_t n,int64_t k){
int64_t N=1;
  for(int64_t i=n-k+1;i<=n;i++)
    N=(N*i)%mod;
  int64_t K=1;
  for(int64_t i=1;i<=k;i++)
    K=(K*i)%mod;
  return (N*f(K,mod-2))%mod;

}
int main(){
int64_t X,Y;
  cin>>X>>Y;
  if((X+Y)%3!=0)
    cout<<0<<endl;
  else{
    if(2*X-Y<0 || 2*Y-X<0)
      cout<<0<<endl;
    else
    cout<<comb((X+Y)/3,(2*X-Y)/3)<<endl;
  }
   return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
if __name__ == '__main__':
    N,A,B = map(int, input().split())
    values = list(map(int, input().split()))
    values.sort(reverse=True)
    result = 0
    max_values = []
    dic_values = defaultdict(int)
    for x in values:
        dic_values[x] += 1
    for limit in range(A, B + 1):
        res = []
        for i,x in enumerate(values):
            if (i >= limit):
                break
            res.append(x)
        if (result < sum(res) / len(res)):
            result = sum(res) / len(res)
            max_values = res

    print ("%.20lf" % result)
    comb = 0
    for limit in range(A, B + 1):
        res = []
        for i,x in enumerate(values):
            if (i >= limit):
                break
            res.append(x)
        if (result == sum(res) / len(res)):

            res_dic = defaultdict(int)
            for x in res:
                res_dic[x] += 1
            tmp = 1
            for key in res_dic:
                a = dic_values[key]
                b = res_dic[key]
                res = 1
                for x in range(b):
                    res *= a
                    a -= 1
                while (b > 0):
                    res //= b
                    b -= 1
                tmp *= res
            comb += tmp
    print (comb)


Measured memory_bytes: 3316
n,x=map(int,input().split())
l=list(map(lambda m:abs(int(m)-x),input().split()))
def gcd(x, y):
    if x<y:x,y=y,x
    while x % y != 0:
        x, y = y, x % y
    return y
ans=l[0]
for i in range(1,n):
    ans=gcd(ans,l[i])
print(ans)


Measured memory_bytes: 15020
"""
Aの値が大きいものからheapqにぶち込んでいけばよい。
"""
from heapq import heappop,heappush
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(reverse=True)
que = []
for a,b in AB:
    if M >= a:
        heappush(que,b)
        M -= 1
    elif que:
        if que[0] < b:
            heappop(que)
            heappush(que,b)
print(sum(que))



Measured memory_bytes: 94316
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 1<<18, mod = 1000000007;
using ll = long long;
int n, m;
struct node
{
	ll a, b, sum;
	node() {sum = 0; a = 1;b = 0;}
	node(int val)
	{
		sum = val;
		a = 1;b = 0;
	}
	void apply(ll c, ll d) {
		ll na = c*a%mod;
		ll nb = (c*b + d)%mod;
		a = na, b = nb;
	}
};
 
node temp, broken;
 
node merge(node l, node r)
{
	temp.sum = (l.sum + r.sum)%mod;
	temp.a = 1;temp.b = 0;
	return temp;
}
 
struct segment_tree
{
	node tr[4 * maxn];
 
	void push(int l, int r, int idx)
	{
		tr[idx].sum = ( ((r - l + 1) * tr[idx].b) + (tr[idx].sum * tr[idx].a) )%mod;
		if(l != r)
		{
			tr[2 * idx + 1].apply(tr[idx].a, tr[idx].b);
			tr[2 * idx + 2].apply(tr[idx].a, tr[idx].b);
		}
		tr[idx].a = 1;tr[idx].b = 0;
	}
 
	void init(int l, int r, int idx)
	{
		if(l == r)
		{
			tr[idx] = node();
			return;
		}
 
		int mid = (l + r) >> 1;
		init(l, mid, 2 * idx + 1);
		init(mid + 1, r, 2 * idx + 2);
 
		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}
 
	void update(int qL, int qR, int A, int B, int l, int r, int idx)
	{
		push(l, r, idx);
 
		if(qL > r || l > qR)
			return;
 
		if(qL <= l && r <= qR)
		{
			tr[idx].apply(A, B);
			push(l, r, idx);
			return;
		}
 
		int mid = (l + r) >> 1;
		update(qL, qR, A, B, l, mid, 2 * idx + 1);
		update(qL, qR, A, B, mid + 1, r, 2 * idx + 2);
 
		tr[idx] = merge(tr[2 * idx + 1], tr[2 * idx + 2]);
	}
 
	node query(int qL, int qR, int l, int r, int idx)
	{
		push(l, r, idx);
 
		if(l > qR || r < qL)
			return broken;
 
		if(qL <= l && r <= qR)
			return tr[idx];
 
		int mid = (l + r) >> 1;
		return merge(query(qL, qR, l, mid, 2 * idx + 1), query(qL, qR, mid + 1, r, 2 * idx + 2));
	}
};
 
segment_tree st;
vector<int> a, b;
int tree[maxn];
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	for(auto &i : a) cin >> i;
	for(auto &i : b) cin >> i;
	vector<array<int, 2>> segs;
	vector<int> C{0};
	for(auto &i : a) {
		auto it = upper_bound(all(b), i);
		if(it == b.begin() || it == b.end()) continue;
		auto it2 = it; it2--;
		segs.push_back({i-*it2, *it-i});
		C.push_back(segs.back()[1]);
	}
	sort(all(C));
	for(auto &[x, y] : segs) y = lower_bound(all(C), y)-C.begin();
	for(auto &[x, y] : segs) y *= -1;
	sort(all(segs));
	segs.erase(unique(all(segs)), segs.end());
	for(auto &[x, y] : segs) y *= -1;
	st.init(0, n, 0);
	st.update(0, 0, 0, 1, 0, n, 0);
	for(auto &[cur, p] : segs) {
		st.update(p, p, 1, st.query(0, p-1, 0, n, 0).sum, 0, n, 0);
	}
	cout << st.query(0, n, 0, n, 0).sum << '\n';
}


Measured memory_bytes: 29968
n,m=map(int,input().split())
arr = [[1,False] for i in range(n)]
arr[0][1]=True

for i in range(m):
    x,y=map(lambda x:int(x)-1,input().split())
    if arr[x][1]:
        if arr[x][0]>1:
            arr[x][0]-=1
            arr[y][0]+=1
            arr[y][1]=True
        else:
            arr[x][0]-=1
            arr[y][0]+=1
            arr[x][1]=False
            arr[y][1]=True
    else:
        arr[x][0]-=1
        arr[y][0]+=1

count=0
for i in range(n):
    if arr[i][1]:
        count+=1

print(count)


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

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;
  std::vector<long long> a(n);

  long long money = 1000;
  for (int i = 0; i < n; ++i)
    std::cin >> a.at(i);
  for (int i = 0; i < n - 1; ++i) {
    if (a.at(i) < a.at(i + 1)) {
      long long kabu = money / a.at(i);
      money -= a.at(i) * kabu;
      money += a.at(i + 1) * kabu;
    }
  }

  std::cout << money << std::endl;
}


Measured memory_bytes: 3196
import java.io.*;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		sc.nextLine();
		char[] s =sc.nextLine().toCharArray();
		int total = 0;
		for (int i = 0, j = 0; i < n; i = j) {
		    while (j < n && s[i] == s[j])
		        j++;

		    total++;
		}
		
		System.out.println(total);

	}

}


Measured memory_bytes: 26324
import sys
input = sys.stdin.readline

import collections
import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def dist(x1,y1,x2,y2):
	return abs(x1-x2)+abs(y1-y2)

def testInput():
	n = 2* 10**5
	def ran():
		#return random.randint(-10**9,10**9)
		return 0
	va = [ran() for _ in [0,]*n]
	return n, va

def main():
	N = int(input())
	vA = linput()
	
	#N,vA=testInput()
	#print(N,vA[:5])
	
	vC = [0,]
	s = 0
	for a in vA:
		s += a
		vC.append(s)
	
	cC = collections.Counter(vC)
	#print(cC)
	
	res = 0
	for p,c in cC.items():
		#print(p,c)
		res += c*(c-1)//2
	
	print(res)
	#sT = "No Yes".split()
	#print(sT[res])
	

if __name__ == "__main__":
	main()


Measured memory_bytes: 44980
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;

int main(){
    int tn, km, tm, kc, ans = 0;
    vector<int> tc;
    cin >>tn >>km >>tm >>kc;
    tc = vector<int>(tn);
    REP(i, tn) cin >>tc[i];
    sort(tc.begin(), tc.end());
    reverse(tc.begin(), tc.end());
    int sum = 0;
    REP(i, tn){
        sum += tc[i];
        ans = max(ans, (int)((kc + sum) / (km + (i + 1) * tm)));
    }
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 1216
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

alias P = Tuple!(int , "to", int, "d");

void main()
{
    auto N = readln.chomp.to!int;
    auto as = readln.split.to!(int[]);
    auto bs = readln.split.to!(int[]);

    P[][] G;
    G.length = 51;
    foreach (i; 1..51) {
        foreach (j; 1..i+1) {
            G[i] ~= P(i%j, j);
        }
    }

    bool check(int i, int j, ulong m) {
        if (i == j) return true;
        
        auto FS = new bool[](51);
        FS[i] = true;
        auto ss = [i];
        while (!ss.empty) {
            auto h = ss[0];
            ss = ss[1..$];
            foreach (n; G[h]) if (!FS[n.to] && (m & (1UL<<n.d))) {
                if (n.to == j) return true;
                FS[n.to] = true;
                ss ~= n.to;
            }
        }
        return false;
    }

    ulong m = (1UL<<51)-1 ^ 1;
    foreach (i; 0..N) {
        if (!check(as[i], bs[i], m)) {
            writeln(-1);
            return;
        }
    }
    foreach_reverse (x; 1..51) {
        m ^= 1UL<<x;
        foreach (i; 0..N) if (!check(as[i], bs[i], m)) goto ng;
        continue;
        ng:
        m |= 1UL<<x;
    }
    writeln(m);
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define INF 2000000000000000000
#define ll long long
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll mod = pow(10, 9) + 7;
  ll N, M;
  cin >> N >> M;
  vector<ll> S(N), T(M);
  for (ll i = 0; i < N; ++i) {
    cin >> S.at(i);
  }
  for (ll i = 0; i < M; ++i) {
    cin >> T.at(i);
  }
  vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
  dp.at(0).at(0) = 1;
  for (ll i = 0; i <= N; ++i) {
    for (ll j = 0; j <= M; ++j) {
      if (i != N) {
        dp.at(i + 1).at(j) = (dp.at(i + 1).at(j) + dp.at(i).at(j)) % mod;
      }
      if (j != M) {
        dp.at(i).at(j + 1) = (dp.at(i).at(j + 1) + dp.at(i).at(j)) % mod;
      }
      if (i != N && j != M) {
        dp.at(i + 1).at(j + 1) = dp.at(i + 1).at(j + 1) - dp.at(i).at(j);
        if (dp.at(i + 1).at(j + 1) < 0) {
          dp.at(i + 1).at(j + 1) += mod;
        }
        if (S.at(i) == T.at(j)) {
          dp.at(i + 1).at(j + 1) = (dp.at(i + 1).at(j + 1) + dp.at(i).at(j)) % mod;
        }
      }
    }
  }
  // for (ll i = 0; i <= N; ++i) {
  //   for (ll j = 0; j <= M; ++j) {
  //     cout << dp.at(i).at(j) << " ";
  //   }
  //   cout << "\n";
  // }
  cout << dp.at(N).at(M) << "\n";
}


Measured memory_bytes: 34528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)
#define _overload4(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload4(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)
#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)
#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl


int main(){
    int n,m;
    int x,y;
    cin>>n>>m>>x>>y;
    int mx=x,my=y;

    REP(i,n){
        cin>>x;
        chmax(mx,x);
    }
    REP(i,m){
        cin>>y;
        chmin(my,y);
    }
    cout<<((mx<my)?"No ":"")<<"War"<<endl;
    return 0;
}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print((n-2)*180)
    return

#B
def B():
    b = S()
    kati = b.count("o")
    kati += 15 - len(b)
    if kati >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    return

#D
def D():
    n = II()
    ab = LIR_(n-1)
    C = LI()
    C.sort(reverse=True)
    c = deque()
    for ci in C:
        c.appendleft(ci)
    edg = [[] for i in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    for num,e in enumerate(edg):
        if len(e) == 1:
            start = num
            break
    q = deque()
    ans = [0 for i in range(n)]
    q.append(start)
    ans[start] = c.pop()
#    print(start)
    while q:
        p = q.pop()
        for e in edg[p]:
            if not ans[e]:
                ans[e] = c.pop()
                q.append(e)
    anssum = 0
    for a, b in ab:
        anssum += min(ans[a], ans[b])
    print(anssum)
    ans = list(map(str, ans))
    print(" ".join(ans))


    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()


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

using namespace std;

int main() {
    int n, m, q;
    int l, r;
    int qp, qq;
    int ans;
    cin >> n >> m >> q;

    vector<vector<int>> x(n+1, vector<int>(n+1, 0));
    vector<vector<int>> c(n+1, vector<int>(n+1, 0));

    for(auto i=0;i<m;++i) {
        cin >> l >> r;
        x[l][r] += 1;
    }

    for(auto i=0;i<n+1;++i) {
        for(auto j=0;j<n+1;++j) {
            for(auto k=0;k<=j;++k) {
                c[i][j] += x[i][k];
            }   
        }
    }

    for (auto i=0;i<q;++i) {
        cin >> qp >> qq;
        ans = 0;
        for (auto j=qp;j<=qq;++j) {
            ans += c[j][qq] - c[j][qp-1];
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 2944
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144*4
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<int> vertexs[4000];
long long cnt[4000];
long long solve(long long now, long long back) {
	long long tmp = 0;
	int cnter = 0;
	REP(q, vertexs[now].size()) {
		int going = vertexs[now][q];
		if (going == back) continue;
		long long neko = solve(going, now);
		if (neko < cnt[now]) {
			tmp = 1;
		}
		cnter++;
	}

	if (tmp == 1) return LONG_INF;
	return cnt[now];
}
int main() {
	int n;
	cin >> n;
	REP(i, n) {
		cin >> cnt[i];
	}
	REP(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		vertexs[a].push_back(b);
		vertexs[b].push_back(a);
	}
	long long ans = 0;
	REP(i, n) {
		if (solve(i, -1) == LONG_INF) {
			cout << i + 1 << endl;
		}
	}
}

Measured memory_bytes: 640
var input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
var obj = {
  "list" : input, "index" : 0, "max" : input.length,
  "hasNext" : function(){return (this.index < this.max);},
  "next" : function(){
    if(!this.hasNext()){throw "NoSuchElementException:次に要素は無いよ";}
    var returnObj = this.list[this.index];
    this.index++;
    return returnObj;
  }
}
Main();
function next(){return obj.next();}
function nextInt(){return myconv(next(),1);}
function nextStrArray(){return myconv(next(),2);}//半角スペース分割
function nextIntArray(){return myconv(next(),4);}//半角スペース + 数値化
function nextCharArray(){return myconv(next(),6);}//1文字分割
function hasNext(){return obj.hasNext();}
function myout(t){console.log(t);}//標準出力
function myerr(t){console.error(t);}//標準エラー出力
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す　1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}
function Main(){
  var s = next().length;
  var output = "";
  for(var i = 0; i < s; i++){
    output += "x";
  }
  myout(output);
}

Measured memory_bytes: 7372
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int p[11][11];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<10;i++)for(int j=0;j<10;j++)scanf("%d",&p[i][j]);
	for(int k=0;k<10;k++)for(int i=0;i<10;i++)for(int j=0;j<10;j++)
		p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
	int ret=0;
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		int s;scanf("%d",&s);if(s!=-1)ret+=p[s][1];
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
#define LL long long
#define Num 1000000007
// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    if(a%b==0) cout<<"0"<<endl;
    else cout<<"1"<<endl;
    return 0;
}

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

const long long MOD = 1e9 + 7;

long long fast_pow(long long a, long long b, long long p){
    long long ans = 1;
    long long base = a % p;
    b = b % (p - 1);
    while (b){
        if (b & 1)
            ans = (ans * base) % p;
        base = (base * base) % p;
        b >>= 1;
    }
    return ans;
}

long long inv(long long a, long long p){
    return fast_pow(a, p - 2, p);
}

long long C(long long n, long long m, long long p){
    if (n < m)
        return 0;
        m = min(m, n - m);
        long long nom = 1, den = 1;
        for (long long i = 1; i <= m; i++){
            nom = (nom * (n - i + 1)) % p;
            den = (den * i) % p;
        }
        return (nom * inv(den, p)) % p;
}

long long lucas(long long n, long long m, long long p){
    if (m == 0)
        return 1;
    return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, a, b;
    cin >> n >> a >> b;

    long long ans = 1, base = 2, nn = n;
    while (nn){
        if (nn & 1)
            ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        nn >>= 1;
    }

    ans -= 1LL;
    ans -= lucas(n, a, MOD);
    while (ans < 0)
        ans += MOD;
    ans -= lucas(n, b, MOD);
    while (ans < 0)
        ans += MOD;

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  AC
//
//  Created by makinofuya on 2019/07/08.
//  Copyright © 2019 makinofuya. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <math.h>
#include <map>

typedef long long ll;
using namespace std;
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define out(s) cout << s << endl



int main(){
    string s;cin >> s;
    map<char,int> w;
    for(char c:s){
        w[c]++;
    }
    for(int i=0;i<w.size();i++){
        if(w[i]%2!=0){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[]args) {
        try {
        
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

      HashSet<String> lottery = new HashSet<String>();
      for(int i = 0;i<n;i++) {
          String words = br.readLine();
          lottery.add(words);
      }
System.out.println(lottery.size());

        }catch(Exception e) {
        }
    }

    
}

Measured memory_bytes: 59040
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

vint v;

bool check(int n){
	while(n){
		int t = n%10;
		n/=10;
		rep(i,v.size()){
			if(v[i] == t) return false;
		}
	}
	return true;
}

void mainmain(){
	int n,m;
	cin>>n>>m;
	v=vint(m);
	rep(i,m) cin>>v[i];
	while(1){
		if(check(n)){
			cout<<n<<endl;
			return;
		}
		n++;
	}
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func scanInts(n int) []int {
	sl := make([]int, n)
	for i := range sl {
		sl[i] = scanInt()
	}
	return sl
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()
	a := scanInts(n)

	sort.Ints(a)
	var w, h int
	for i := n - 1; i > 0; i-- {
		if a[i] == a[i-1] {
			if w == 0 {
				w = a[i]
				i--
				continue
			} else if h == 0 {
				h = a[i]
				break
			}
		}
	}
	fmt.Println(w * h)
}


Measured memory_bytes: 4184
//保留所有权利。
#include<iostream>
#include<stdio.h>//printするよ
#include<vector>
#include<algorithm>//辞書順はnext_permutationだよ
#include<set>
#include<string>
#include<string.h>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<utility>//swapで数値交換するよ
//END OF LIBRARIES.
#define rt "\n"//改行を最速化させるよ
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define vcin(v) for (int i = 0; i < (v).size(); i++) { cin >> (v)[i]; }
#define sort(s) sort(s.begin(),s.end())
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define cncn int cnt=0
#define smsm int sum=0
#define str srting
#define nn int n=0
#define please return
#define AC 0//おまじないだよ
#define Rapid cin.tie(0);ios::sync_with_stdio(false)
//END OF DEFINE.
using namespace std;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vcha;
typedef vector<double> vdou;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool; 
//END OF TYPEDEF.

//最大公約数（GCD）を求めるよ
//最小公倍数（LCM）は＜＜　A × B ÷ GCD　 ＞＞で求まるよ

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}
int x = 0, y = 0;
//BEGIN OF CODE.
int main(void){
	int h, n;
	cin >> h >> n;
	vint a(n);
	rep(i, n)cin >> a[i];
	asas; int cnt = h;//cntってのは残りの体力
	rep(i, n) {
		cnt -= a[i];
	}
	Yes(cnt<=0);
	please AC;
}
//THE END.

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int dfs(int x,int y,int sum);
int ans=0,nsum=0;
int h,w;
int mas[111][111];
int aha[111][111];
int main(){
  while(1){
    ans=0;
    cin >> w >> h;
    if(w==0 && h==0)break;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> aha[i][j];
      }
    }
    
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(aha[i][j]==1){
	  for(int k=0;k<h;k++){
	    for(int q=0;q<w;q++){
	      mas[k][q]=aha[k][q];
	    }
	  }
	  nsum=0;
	  dfs(j,i,0);
	  ans=max(ans,nsum);
	}
      }
    }
    cout << ans << endl;
  }
}

int dfs(int x,int y,int sum){
  //cout << '(' << x << ',' << y<< ')' << sum << endl;
  int dx[4]={0,1,0,-1};
  int dy[4]={1,0,-1,0};
  int nx,ny;
  if(sum>nsum){
    nsum=sum;
  }
  for(int i=0;i<4;i++){
    nx=x+dx[i];
    ny=y+dy[i];
    if(nx>=0 && ny>=0 && nx<w && ny<h && mas[ny][nx]==1){
      mas[ny][nx]=0;
      dfs(nx,ny,sum+1);
      mas[ny][nx]=1;
    }
  }
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 30)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};



int main(){
  
  int n;
  string s;
  cin >> n >> s;
  ll r = 0,g = 0,b = 0;
  REP(i,n){
    if(s[i] == 'R')r++;
    if(s[i] == 'G')g++;
    if(s[i] == 'B')b++;
  }
  ll res = r*g*b;
  for(int i = 0;i < n;i++){
    for(int j = i+2;j < n;j+=2){
      ll mid = (i+j)/2;
      if(s[i] != s[j] && s[i] != s[mid] && s[j] != s[mid])res--;
    }
  }
  cout << res << endl;



  return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 2e5 + 5;
set<int> p[2];
int b[2][MAX];
int mn[2];

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

    ll ans = 1LL * (n - 2) * (n - 2);
    mn[0] = mn[1] = n;

    fori (i, 0, q) {
        int type, x;
        cin >> type >> x;

        type--;

        auto &s = p[type];
        auto it = s.lower_bound(x);
        if (it != begin(s)) {
            b[type][x] = b[type][*prev(it)];
        }
        else {
            b[type][x] = mn[!type];
        }

        ans -= b[type][x] - 2;

        s.insert(x);
        mn[type] = min(mn[type], x);
    }

    cout << ans << endl;
}

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



Measured memory_bytes: 14568
#include<bits/stdc++.h>
using namespace std;
int main(){
	char ch[100001],ch2[100001];
	int ans=0,ans1=0,i=1;
	cin>>ch[0];
	ch2[0]=ch[0];
	while(cin>>ch[i]){
		ch2[i]=ch[i];
		if(ch[i]==ch[i-1]){
			if(ch[i]=='1')ch[i]='0';
			else ch[i]='1';
			ans++;
		}
		i++;
	}
	for(i=strlen(ch2)-2;i>=0;i--){
		if(ch2[i]==ch2[i+1]){
			if(ch2[i]=='1')ch2[i]='0';
			else ch2[i]='1';
			ans1++;
		}
	}
	//cout<<ans<<ans1<<endl;
	cout<<min(ans,ans1);
	return 0;
}

Measured memory_bytes: 384
N = int(input())
A = list(map(int, input().split()))
xs = [None] * N
xs[0] = sum(A[i] * (1 if i % 2 == 0 else -1) for i in range(N))
for i in range(1, N):
    xs[i] = 2 * A[i - 1] - xs[i - 1]
print(' '.join(map(str, xs)))


Measured memory_bytes: 85988
//?????£???????????????????????£???????????°??±???????????¶???????????????.
//??????????????????????????°???DP
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n;
int a[2000];
int dp[2][2000][2000];		//dp[2][l][r] := ????????????????????????????????¢([0]->IOI?????????,[1]->JOI??????)

int ioi(int l, int r);	//???????????????????????£???????????????l??¨r, ?????????l??????????¨??????????????????¨?????????r?????????????????????l??¨r???????????????
int joi(int l, int r);	//??±??????????????£???????????´?????????????????????l, r???????????????????????????????????????

int ioi(int l, int r){
	if( dp[0][l][r] >= 0 ) return dp[0][l][r];
	if( (l+n-1) % n == r ){ return (dp[0][l][r] = 0); }
	else if( a[l] > a[r] ){ return (dp[0][l][r] = joi((l+1) % n, r)); }
	else{ return (dp[0][l][r] = joi(l, (r+n-1) % n)); }
}
int joi(int l, int r){
	if( dp[1][l][r] >= 0 ) return  dp[1][l][r];
	if( (l+n-1) % n == r ){ return (dp[1][l][r] = 0); }
	int u = ioi((l+1) % n, r) + a[l];
	int v = ioi(l, (r+n-1) % n) + a[r];
	return (dp[1][l][r] = max(u, v));
}

signed main()
{
	int i;
	
	cin >> n;
	for( i = 0; i < n; i++ )
		cin >> a[i];
	
	for( int l = 0; l < n; l++ ){
		for( int r = 0; r < n; r++ ){
			dp[0][l][r] = -1;
			dp[1][l][r] = -1;
		}
	}
	
	int ans = 0;
	for( i = 0; i < n; i++ ){
		ans = max(ans, ioi((i+1) % n, (i+n-1) % n) + a[i]);
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  int p, w, g, y;
  p = w = g = y = 0;

  for (int i = 0; i < N; i++) {
    string S;
    cin >> S;
    
    if (S == "P") {
      p = 1;
    } else if (S == "W") {
      w = 1;
    } else if (S == "G") {
      g = 1;
    } else if (S == "Y") {
      y = 1;
    }
  }
  
  if ( p + w + g + y == 3 ) {
      cout << "Three" << endl;
  } else if ( p + w + g + y == 4 ) {
      cout << "Four" << endl;
  }
}


Measured memory_bytes: 3596
package main

import (
	"bufio"
	"fmt"
	"os"
)

var writer = bufio.NewWriter(os.Stdout)

func main() {
	var A, B int
	fmt.Scan(&A, &B)

	if B%A == 0 {
		fmt.Fprintf(writer, "%d\n", A+B)
	} else {
		fmt.Fprintf(writer, "%d\n", B-A)
	}
	writer.Flush()
}


Measured memory_bytes: 640
#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 H,A,ans=0;
  cin >> H >> A;
  while(H > 0){
    H = H - A;
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
let () = Scanf.scanf "%d"
           (fun n ->
             let rec minus2ary_from_10ary quotient ans_l =
               match quotient with
               | 0 -> if ans_l = [] then [0] else ans_l
               | n when n > 0 -> minus2ary_from_10ary (n / -2) ((n mod -2) :: ans_l)
               | n when n mod -2 == 0 -> minus2ary_from_10ary (n / -2) (0 :: ans_l)
               | n ->  minus2ary_from_10ary (n / -2 + 1) (1 :: ans_l)  (* 結果の調整 *)
             in
             let rec print_int_from_l l  =
               match l with
               | [] -> print_string ""
               | x :: xs -> print_int x; print_int_from_l xs
             in
             print_int_from_l (minus2ary_from_10ary (n) []))



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define zeros(arr) memset(arr,0,sizeof(arr))
#define precise(num)  cout<<fixed; cout << std::setprecision(num)
#define nl cout<<"\n";
#define test int t;cin>>t;while(t--) 
int32_t main(){
    int n,k;
    cin>>n>>k;
    
    int va1 = n/k;
    
    n = n - va1*k;
    
    
    int ans = n;
    
    ans = min(ans , abs(n- k));
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int main() {
  int64_t A, B, N; std::cin >> A >> B >> N;
  int64_t x = std::min(B-1, N);
  int64_t ans = A*x/B;
  fin(ans);
  return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,D;
#define Maxn 100010
int x[Maxn][200];
int main(){
	scanf("%d%d",&n,&D);
	for(register int i=1;i<=n;++i)
	    for(register int j=1;j<=D;++j)scanf("%d",&x[i][j]);
	int Ans=0;
	for(register int i=1;i<n;++i)
	    for(register int j=i+1;j<=n;++j){
			int res=0;
			for(register int k=1;k<=D;++k)res=(res+(x[i][k]-x[j][k])*(x[i][k]-x[j][k]));
			int tmp=floor(sqrt(res));
			if(tmp*tmp==res)Ans++;
	    }
	printf("%d\n",Ans);
	return 0;
} 

Measured memory_bytes: 256