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

int main()
{
	int64_t n;
	cin >> n;
	vector<int64_t> as(n);
	for (auto &a : as)
	{
		cin >> a;
	}

	vector<int64_t> ans(n);

	ans[0] = 0;
	for (int64_t i = 1; i < n; i++)
	{
		ans[i] = as[i - 1] - ans[i - 1];
	}

	ans[0] = (as[n - 1] - ans[n - 1]) / 2;
	for (int64_t i = 1; i < n; i++)
	{
		ans[i] = as[i - 1] - ans[i - 1];
	}

	for (int64_t i = 0; i < n; i++)
	{
		assert(as[i] == (ans[i] + ans[(i + 1) % n]));
	}

	for (auto &x : ans)
	{
		x *= 2;
	}

	for (auto &x : ans)
	{
		cout << x << ' ';
	}
	cout << endl;

	return 0;
}

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

int main(){
  int S[13],H[13],C[13],D[13];
  for(int i = 0; i < 13; i++){
    S[i]=0;
    H[i]=0;
    C[i]=0;
    D[i]=0;
  }
  int n = 0;
  string J;
  cin >> n;
  for(int i = 0; i < n; i++){
    int f = 0;
    cin >> J >> f;
    if(J=="S")
      S[f-1]=f;
    if(J=="H")
      H[f-1]=f;
    if(J=="C")
      C[f-1]=f;
    if(J=="D")
      D[f-1]=f;
  }
  for(int i = 0; i < 13; i++){
    if(S[i]==0)
      cout << "S" << " " <<  i + 1 << endl;
  }
  for(int i = 0; i < 13; i++){
    if(H[i]==0)
      cout << "H" << " " << i + 1 << endl;
  }
  for(int i = 0; i < 13; i++){
    if(C[i]==0)
      cout << "C" << " " << i + 1 << endl;
  }
  for(int i = 0; i < 13; i++){
    if(D[i]==0)
      cout << "D" << " " << i + 1 << endl;
  }
}


Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int gcd(int a,int b){
  if(b == 0) return a;
  return gcd(b,a%b);
}

int main(){
  int n;
  cin >> n;
  vector<int> d(1000001,1);
  for(int i=2;i<1000001;i++){
    int j = i;
    while(j<1000001){
      if(d[j] == 1) d[j] = i;
      j += i;
    }
  }
  set<int> totalset;
  bool fail = 0;
  int tmp;
  rep(i,n){
    int a;
    cin >> a;
    if(i == 0) tmp = a;
    else tmp = gcd(tmp,a);
    set<int> localset;
    while(a > 1){
      localset.insert(d[a]);
      a /= d[a];
    }
    for(int l : localset){
      if(totalset.count(l) > 0) fail = 1;
      totalset.insert(l);
    }
  }
  if(!fail) cout << "pairwise coprime" << endl;
  else if(tmp == 1) cout << "setwise coprime" << endl;
  else cout << "not coprime" << endl;
}


Measured memory_bytes: 10912
#!/usr/bin/env python3.4

# abc128_d

import collections
import itertools

def slice_deq(deq, n):
    return itertools.islice(deq, 0, n)

def main():
    # Input
    n, k = [int(s) for s in input().split()]
    vs = (int(s) for s in input().split())
    # Get ans
    vs = collections.deque(vs)
    R = min(n, k)
    def gene_tv():
        for i in range(1, R+1):
            vs.rotate(-1)
            vs.reverse()
            for _ in range(i+1):
                tv = 0
                pps = []
                for v in slice_deq(vs, i):
                    tv += v
                    if v<0:
                        pps.append(v)
                #print(i, vs, tv, pps)
                vs.rotate(-1)
                pps.sort()
                pp = sum(pps[:k-i])
                yield tv-pp
            vs.rotate(-(i-1))
    ans = max(gene_tv())
    ans = max(ans, 0)
    # Output
    print(ans)

if __name__ == '__main__':
    main()



Measured memory_bytes: 3316
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x, a, b = map(int, input().split())
    print("A") if abs(x - a) < abs(x - b) else print("B")


if __name__ == '__main__':
    resolve()


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

struct UnionFind {
    //iを頂点として、d[i] := iが子ならば親のID(非負)、iが親ならば-サイズ(負)
    vector<int> d;
    //初期化子リストによる初期化、n=0としているのはデフォルト引数
    //n個の頂点をすべて親として初期化(サイズは全て1なので-1)
    UnionFind(int n=0) : d(n, -1) {}
    //親を見つける
    int find(int x){
        if(d[x] < 0) return x; //親ならばそれ自体を返す
        return d[x] = find(d[x]); //メモ化して経路縮約
    }
    //連結する
    bool unite(int x, int y){
        x = find(x); y = find(y); //親同士を連結する
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y); //yの方がサイズが大きい場合入れ替え
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    //親が同じならtrue
    bool same(int x, int y) { return find(x) == find(y); }
    //連結成分のサイズ
    int size(int x){ return -d[find(x)]; }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    int fre[100005];
    vector<int> block[100005];
    UnionFind uf(N);
    rep(i, M){
        int A, B;
        cin >> A >> B;
        A--; B--;
        fre[A]++;
        fre[B]++;
        uf.unite(A, B);
    }
    rep(i, K){
        int C, D;
        cin >> C >> D;
        C--; D--;
        //隣接リスト
        block[C].push_back(D);
        block[D].push_back(C);
    }
    rep(i, N){
        //iが含まれる連結成分のサイズ - 自分自身(i) - iの友達
        int ans = uf.size(i) - 1 - fre[i];
        //同じ連結成分内でブロック関係があればそれを引く
        for(int u : block[i]){
            if(uf.same(i, u)) ans--;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 9856
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

k = int(input())

tmp = 0
res = ""

for i in range(k):
    res += "ACL"

print(res)


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

int main() {
  int n, t_num, t_min=1000000, cnt=0;
  cin >> n;
  for (int i=0; i<n; i++){
    cin >> t_num;
    if (t_num<=t_min){
      cnt+=1;
      t_min=t_num;
    }
  }
  cout << cnt << endl;
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    unsigned long long N;
    cin >> N;

    unsigned long long ans = N * (N - 1) / 2;

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

def main():
    N,K = map(int,input().split())
    atack = [1] * N
    for  i in range(K):
        d = int(input())
        A = list(map(int,input().split()))
        for k in A:
            atack[k - 1] = 0
    print(sum(atack))
    
if __name__ == '__main__':
    main()


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


public class Main{
    static long MOD = 1000000007;
    static long dp[] = new long[1 << 21];
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        // Start writing your solution here. -------------------------------------
        long MOD = 1000000007;
        //int t = sc.nextInt();
        int t = 1;
        while(t -- > 0)
        {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            out.println(c + " " + a + " " + b);
            //for(int ii = 0; ii <= n; ii++) System.out.println(Arrays.toString(dp[ii]));
        }
        out.close();
    }
    public static int solve(int x, int[] a){
        int max = 0, n = a.length - 1;
        for(int i = 1; i <= n; i++)
            if(a[i] > max) max = a[i];
        return 0;
    }
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;
    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    //--------------------------------------------------------
}

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

/* 大文字を小文字に変換 */
char tolowr(char c) {
  if ((c >= 'A') && (c <= 'Z')) {
    return (c + 0x20);
  } else {
    return c;
  }
}

int main(){
  char w[11];
  int ans=0;
  unsigned int i,k;

  scanf("%s",w);
  
  while(1){
    char t[1001];
    scanf("%s",t);
    
    if(strcmp(t,"END_OF_TEXT")==0) break;
    if(strlen(t) != strlen(w)) continue;
    
    int check = -1;
    for(i=0; i < strlen(t); ++i){
      for(k=0; k < strlen(w); ++k){
	if(i+k >= strlen(t) || tolowr(w[k]) != tolowr(t[i+k])){
	  check=1;
	  break;
	}	
	if(k == strlen(w)-1){
	  ++ans;
	  check = 1;
	  break;
	}
      }
      if(check == 1) break;
    }
  }

  printf("%d\n", ans);
  return 0;
}



Measured memory_bytes: 2088
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  ll dai = 0;
  rep(i, n - 1) {
    if (a[i + 1] < a[i]) {
      dai += a[i] - a[i + 1];
      a[i + 1] = a[i];
    }
  }

  cout << dai << endl;

  return 0;
}

Measured memory_bytes: 4816
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int a,b,c,n,x;
	scanf("%d %d %d %d",&n,&a,&b,&c);
	x=n-(a+b-c);
	printf("%d\n",x);
	return 0;
}


Measured memory_bytes: 2712
#include <stdio.h>
#include <string.h>
int main(){
  char s[7];
  scanf("%s", s);
  if ( strcmp("Sunny", s) == 0 ) printf("Cloudy");
  if ( strcmp("Cloudy", s) == 0 ) printf("Rainy");
  if ( strcmp("Rainy", s) == 0 ) printf("Sunny");
  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>

int cmp1(const void *a, const void *b){
	return *((char *)a) - *((char *)b);
}
int cmp2(const void *a, const void *b){
	return *((char *)b) - *((char *)a);
}

int ff(int a,int b){
	int m,mm;
	int i;
	char s[13]={0};
	/*
	for(i = 5;i >= 0;i--){
		s[i] = a%10 + '0';
		a /= 10;
		if(a==0)break;
	}
	for(;i >= 0;i--)s[i] = '0';
	*/
	sprintf(s,"%d000000",a);
	s[b] = '\0';

	qsort(s,b,sizeof(char),cmp1);
	m = atoi(s);
	qsort(s,b,sizeof(char),cmp2);
	mm = atoi(s);

	return mm-m;
}

int main(){
	int i,j,a[100],l,ii,jj;
	int q,w,e,r,t,y;

	while(scanf("%d%d",&a[0],&l),l){
		for(i = 1;1;i++){
			a[i] = ff(a[i-1],l);
			q = 0;
			for(j = 0;j < i;j++){
				if(a[i] == a[j]){
					ii = i;
					jj = j;
					q = 1;
					break;
				}
			}
			if(q)break;
		}
		printf("%d %d %d\n",jj,a[jj],ii-jj);
	}
	return 0;
}

/*
959000 6
95900 6
9590 6
959 6
950900 6
920097 6
920079 6
919600 6
91960 6
9196 6
919060 6
862632 6
750843 6
55555 5
2 1
782464 6
782457 6
782446 6
779944 6
23 2
23 3
23 4
23 5
23 6
631764 6
6174 4
549945 6
495 3
105 3
104642 6
707813 6
191985 6
27605 5
171941 6
859443 6
188265 6
682092 6
94354 6
9983 6
90499 6
904909 6
904099 6
903980 6
90398 6
903908 6
903890 6
90389 6
903809 6
903098 6
903089 6
831701 6
831699 6
831600 6
83160 6
8316 6
831592 6
831570 6
99989 5
99964 5
999794 6
383342 6
383336 6
887 3
960 3
96 3
96 2
50005 6
500005 6
500 3
50 3
5 3
5 1
499994 6
0 0
*/





			

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

int main() {
	string s;
	cin >> s;
	int a = 0, b = 0;
	int n = s.size();
	rep(i, n) {
		if (s[i] == '0') a++;
		else b++;
	}
	cout << 2 * min(a, b) << endl;
	return 0;
}


Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int a = 100 * A / 8;
        if (((100 * A)%8 != 0)) {
            a++;
        }
        int ap = 100 * (A+1) / 8;
        if ((100 * (A+1))%8 == 0) {
            ap--;
        }
        int b = 10 * B;
        int bp = 10 * (B+1);
        List<Integer> in = new ArrayList<>();
        List<Integer> out = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = a;i <= ap;i++) {
            in.add(i);
        }
        for (int i = b; i < bp;i++) {
            out.add(i);
        }
        for (Integer i :out) {
            if (in.contains(i)) {
                ans.add(i);
            }
        }
        if (ans.isEmpty()) {
            System.out.println(-1);
        } else {
            System.out.println(ans.get(0));
        }
    }
}

Measured memory_bytes: 23124
#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<array>
#include<cstring>
using namespace std;
int main(){
string S;
string T;
cin>>S>>T;
int N=S.size();
for (int i = 0; i < N; i++) {
  S=S.back()+S.substr(0,N-1);
  if(S==T){
    cout<<"Yes";
    return 0;
  }
}






cout<<"No";






}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# 157c
n, m = map(int, input().split())
s = []
c = []
for _ in range(m):
  _s, _c = input().split()
  s.append(int(_s))
  c.append(_c)

ret = -1
for i in range(1000):
  x = str(i)
  if len(x) != n:
    continue
  isOk = True
  for _s, _c in zip(s, c):
    #if len(x) < _s or x[_s - 1] != _c:
    if x[_s - 1] != _c:
      isOk = False
      break
  if isOk:
    ret = i
    break
print(ret)


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		String str1;
		while(s.hasNext()){
		str1 = s.nextLine();
		str1=str1.toUpperCase();
		System.out.println(str1);
		}
	}
}

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

#include <ext/pb_ds/assoc_container.hpp> //required
#include <ext/pb_ds/tree_policy.hpp> //required

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
typedef long long  ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define SZ(a) int((a).size())
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(int i=x;i<y;i++)
#define frr(i,x,y) for(int i=x-1;i>=y;i--)
#define inf 1e18+1
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod=1000000007;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;}a=a*a;b>>=1;}return ans;}
ll powerm(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;ans%=mod;}a=a*a;a%=mod;b>>=1;}return ans%mod;}
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

void solve()
{
    ll n,k;
    cin>>n>>k;
    string str;
    cin>>str;
    ll ct=0;
    fr(i,0,n)
    {
        if(str[i]=='R'&&str[i+1]=='R'&&i+1<n)
        {
            ct++;
        }
        if(i-1>=0)
        {
            if(str[i]=='L'&&str[i-1]=='L')
            {
                ct++;
            }
        }
    }
    ct+=k*2;
    ct=min(ct,n-1);
    cout<<ct<<endl;

    return;
}
int main()
{
    IOS;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        //cout<<"Case #"<<pp-t<<":\n";
        solve();
    }
    return 0;
}
/* stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
*/
/*
recursion - matrix exponential

*/
// BITMASK:
// 1)When some constrall is of the order of 15-20, think of bitmask DP.
// 2)When some constrall is around 40, try out meet in the middle
// 3) See Strings,palindromes,prefix,suffix etc -> KMP,Z algorithm

Measured memory_bytes: 3736
n, h = map(int, input().split())
S = [list(map(int, input().split())) for i in range(n)]
S.sort(key=lambda x: x[1], reverse=True)
# print(S)

count = 0
max_rp = max([x[0] for x in S])
idx = 0
while h > 0 and idx < len(S) and S[idx][1] > max_rp:
    h -= S[idx][1]
    count += 1
    # print(idx, h, count)
    idx += 1

if h > 0:
    print(count + (h-1)//max_rp + 1)
else:
    print(count)


Measured memory_bytes: 72052
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <unordered_map>
typedef long long ll;
using namespace std;
const int mod=1e9+7;
ll solve(){
    int n,x,t;
    cin>>n>>x>>t;
    return ((n/x)+(n%x != 0))*t;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while(t--) cout<<solve()<<'\n';
    //while(t--) solve(),cout<<'\n';
    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[(" << __LINE__ << ") " << (#x) << "]: " << x << endl;

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

    int n, k;
    cin >> n >> k;
    int a[n];
    for (int& e: a) cin >> e;
    sort(a, a+n);

    int ans = 0;
    for (int i=0; i<k; i++) ans += a[i];
    cout << ans << "\n";
}


Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <unordered_set>
#include <unordered_map>

using namespace std;
const int MAXN = 200002;
const int MAXK = 100001;
const int MOD = 1e9+7;
int h[MAXN];
int a[MAXN];
long long tree[2*MAXN];
int N;
void update(int i, long long v)
{
    int in = i+N;
    tree[in] = v;
    for(in=in>>1;in>1;in>>=1) tree[in] = max(tree[in*2],tree[in*2+1]);
}
long long query(int l, int r)
{
    long long best = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1)
    {
        if (l&1) best = max(best,tree[l++]);
        if (r&1) best = max(best,tree[--r]);
    }
    return best;
}
int main()
{
    cin >> N;
    for(int i = 0; i < N; i++) cin >> h[i];
    for(int i = 0; i < N; i++) cin >> a[i];
    N++;
    for(int i = 0; i < 2*N; i++) tree[i] = 0;
    long long best = 0;
    for(int i = 0; i < N; i++)
    {
        long long v =  query(1,h[i]) + a[i];
        if(v>best) best = v;
        update(h[i],v);
    }
    cout << best;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define Inf 1LL << 60
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

int N,W;
int w[110],v[110];
long long lists[110][100010] = {0}; 

int main()
{
    cin >> N >> W;
    for(int i = 0;i < N;i++) cin >> w[i] >> v[i];
    for(int i = 0;i < N;i++)
    {
        for(int s = 0;s <= W;s++)
        {
            if(s - w[i] >= 0)
                chmax(lists[i+1][s],lists[i][s - w[i]] + v[i]);
            chmax(lists[i+1][s],lists[i][s]);
        }
        
    }
    cout << lists[N][W] << '\n';
}

Measured memory_bytes: 79360
# A問題
N, A, B, C, D = map(int, input().split())
S = input()

#jumpable
jumpable = 1
for i in range(A, max(D, C)-1):
    if S[i]=="#" and S[i+1]=="#":
        jumpable = 0
        break;

#飛び越える
if(D<C):
    changable = 0
    for i in range(B-2, D-1):
        if S[i]=="." and S[i+1]=="." and S[i+2]==".":
            changable=1
            break
    if(changable==0):
        jumpable=0

if(jumpable==0):
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3572
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;
const int mod = 1e9+7;

int main(){
	int t,n,maxnum;
	cin >> t; cin >> n;
	vector<int> s;
	s.push_back(n);
	maxnum = n;
	while(--t){
        cin >> n;
		if(n == s.back())continue;
		s.push_back(n);
		if(n > maxnum)maxnum = n;
	}
    int dp[s.size()+1];
	int save[maxnum+1];
	memset(save, 0, sizeof(save));
    dp[0] = 1;
    for(int i = 0; i < s.size(); ++i){
		dp[i+1] = (dp[i] + save[s[i]])%mod;
		save[s[i]] = (save[s[i]]+ dp[i])%mod; 
    }
    cout << dp[s.size()];
	return 0;
} 

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

int main(){
  long long a, b, c;
  cin >> a >> b >> c;
  if (c-a-b < 0) cout << "No" << endl;
  else if(4*a*b < (c-a-b)*(c-a-b)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
#define PI (acos(-1))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

#define MAXN 1123456
#define MOD 1000000007

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
typedef vector<vi> vvi;

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

  int n;
  cin>>n;
  vi a(n), b(n);
  rep(i,0,n)cin>>a[i];
  rep(i,0,n)cin>>b[i];

  ll c = 0;
  priority_queue<pii> pq;
  rep(i,0,n) pq.push({b[i], i});

  bool good=true;
  while (!pq.empty()) {
    int wtf = pq.top().fst;
    int m = pq.top().snd;
    pq.pop();
    if (b[m] != wtf) continue;
    if (b[m] == a[m]) continue;

    int y=max(a[m],max(b[(m-1+n)%n], b[(m+1)%n]));
    int sum = b[(m-1+n)%n] + b[(m+1)%n];
    int k = ((b[m] - y + sum - 1) / sum);
    b[m] -= k * sum;
    c += k;

    pq.push({b[m],m});
    
    if (b[m] < a[m]) goto fail;
  }

  rep(i,0,n) {
      if (a[i]!=b[i]) {
        good=false;
        if (b[i] < a[i]) goto fail;
      }
    }
  if (good)cout<<c<<endl;
  else cout<<-1<<endl;

  if(good)return 0;
fail:
  cout<<-1<<endl;

}





Measured memory_bytes: 9584
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <stack>
#include <list>
#include <deque>
using namespace std;
int n, m, i, j, k, t=0, x;
char s[100010];
int main(){
	cin>>s;
	m=strlen(s);
	for(i=0;i<=m-1;i++) if(i%2==0) cout<<s[i];
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define all(a) a.begin(),a.end()
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define dbg_v(v) cout<<#v<<":";for(auto x:v) cout<<" "<<x; cout<<endl;
int power(ll x,ll y){ll res = 1;while(y>0){if(y&1)res = (res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	
	int T=1;
	//cin>>T;
	while(T--){
		string s;
		cin>>s;
		ll ans=0;
		for(int i=0;i<(int)s.length();i++){
			ans=(ans+(s[i]-'0'))%9;
		}
		if(ans==0)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF LLONG_MAX/10
#define rep(i,n) for(int i=0;i<n;i++)
#define krep(i,k,n,m) for(int i=k;i<n;i+=m)
#define erep(i,k,n) for(int i=k;i<n;i++)
#define mod 1000000007
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0,con,kai;
    int b[n+1];
    for(int i=n;i>0;i--){
        con=0;
        kai=2;
        while(1){
            if(i*kai<=n){
                con+=a[i*kai];
                con=con%2;
                kai++;
            }
            else{
                break;
            }
        }
        if(con==0){
            if(a[i]==1){
                b[ans]=i;
                ans++;
            }
        }
        else{
            if(a[i]==0){
                b[ans]=i;
                ans++;
                a[i]=1;
            }
            else{
                a[i]=0;
            }
        }
    }
    if(ans==0){
        cout<<0<<endl;
        return 0;
    }
    cout<<ans<<endl;
    rep(i,ans){
        cout<<b[i]<<" ";
    }
    cout<<endl;
}



Measured memory_bytes: 3456
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

#define ll long long
using vt = int; //ここで数値の型を変えられる
#define rep(i, n) for (vt i = 0; i < (vt)(n); i++)
#define reps(i, s, n) for(vt i = (vt) (s); i < (vt) (n); i++) 
#define MOD 1000000007

int main() {
	int n;
	cin >> n;
	if (n % 2 == 1) {
		cout << "No";
		return 0;
	}
	string s;
	cin >> s;
	rep(i, n / 2) {
		if (s.at(i) != s.at(n / 2 + i)) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int A, B;
    char op;
    cin >> A >> op >> B;
    if (op == '+') {
        cout << A + B << endl;
    }
    else if (op == '-') {
        cout << A - B << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n;
    cin >> n;
    vector<ll> a(n), b(n);
    vector<vector<ll>> g(n);
    REP(i, n-1) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }

    ll dmax;
    vector<ll> x;
    function<void(ll,ll,ll)> dfs = [&](ll v, ll p, ll d) {
        chmax(dmax, d);
        ll num = 0;
        for(auto to: g[v]) if(to != p) {
            dfs(to, v, d+1);
            num++;
        }
        chmax(x[d], num);
    };

    ll ans = INF, leaf = INF;
    REP(i, n) {
        dmax = 0;
        x.assign(n, 1);
        dfs(i, -1, 1);
        ll t = 1;
        REP(i, n) t *= x[i]; 
        if(ans > dmax || (ans == dmax && leaf > t)) {
            dump(i);
            ans = dmax;
            leaf = t;
        }
    }
    REP(i, n-1) {
        dmax = 0;
        x.assign(n, 1);
        dfs(a[i], b[i], 1);
        dfs(b[i], a[i], 1);
        ll t = 2;
        REP(i, n) t *= x[i];
        if(ans > dmax || (ans == dmax && leaf > t)) {
            dump(a[i], b[i]);
            ans = dmax;
            leaf = t;
        }
    }

    cout << ans << " " << leaf << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"log"
	"os"
	"strconv"
	"strings"
)

type node struct {
	value  int
	parent *node
	left   *node
	right  *node
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	var root *node
	m := eGetInt(reader)
	for i := 0; i < m; i++ {
		line := eGetline(reader)
		if line[0] == 'i' {
			elements := strings.Fields(line)
			val := eAtoi(elements[1])
			root = insert(root, val)
		} else {
			// print
			buffer := bytes.NewBufferString("")
			printInOrder(root, buffer)
			fmt.Println(buffer.String())
			buffer.Reset()
			printPreOrder(root, buffer)
			fmt.Println(buffer.String())
			buffer.Reset()
		}
	}
}

func insert(root *node, value int) *node {
	var y *node
	x := root
	for x != nil {
		y = x // 親を覚えておく
		if value < x.value {
			x = x.left
		} else {
			x = x.right
		}
	}
	x = &node{value, y, nil, nil}
	if y == nil {
		return x
	} else if x.value < y.value {
		y.left = x
	} else {
		y.right = x
	}
	return root
}

func printInOrder(root *node, buf *bytes.Buffer) {
	if root.left != nil {
		printInOrder(root.left, buf)
	}
	buf.WriteString(fmt.Sprintf(" %d", root.value))
	if root.right != nil {
		printInOrder(root.right, buf)
	}
}
func printPreOrder(root *node, buf *bytes.Buffer) {
	buf.WriteString(fmt.Sprintf(" %d", root.value))
	if root.left != nil {
		printPreOrder(root.left, buf)
	}
	if root.right != nil {
		printPreOrder(root.right, buf)
	}
}

func eGetInt(reader *bufio.Reader) int {
	return eAtoi(eGetline(reader))
}

func eGetline(o *bufio.Reader) string {
	s, err := o.ReadString(byte('\n'))
	if err != nil {
		if err == io.EOF {
			return s
		}
		log.Fatal(err.Error())
	}
	return strings.TrimRight(s, "\r\n")
}
func eAtoi(s string) int {
	v, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err.Error())
	}
	return v
}



Measured memory_bytes: 42660
while True:
    n,m = map(int,input().split())
    if n==0 and m==0:
        break
    step = 0
    if n >= m:
        X = n
        Y = m
        while True:
            X = X % Y
            X,Y = Y,X
            step +=1
            if Y == 0:
                ans = X
                break
    else:
        X = m
        Y = n
        while True:
            X = X % Y
            X,Y = Y,X
            step +=1
            if Y == 0 :
                ans = X
                break
    print(ans,step)


Measured memory_bytes: 5604
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
	int A,B,C,K;
	int i,j;
	char str[100000];
 
	fgets(str, sizeof(str), stdin);
	A=atoi(strtok(str," "));
	B=atoi(strtok(NULL," "));
	C=atoi(strtok(NULL," "));
	K=atoi(strtok(NULL," "));

	if(K<A){
		printf("%d\n",K);
	}else if( K < (A+B) ){
		printf("%d\n",A);
	}else{
		printf("%d\n",(2*A+B-K));
	}

	return 0;
}


Measured memory_bytes: 2140
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<utility>
#include<bitset>
#include<complex>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<stack>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;

const int maxn = 2e5;
const int P = 1e9+7;

int n, ci[maxn+5], pa[maxn+5];
int vi[maxn+5];
LL f[maxn+5];

inline void Add(LL &a, LL b) { a+=b; if(a>=P) a-=P; }

int main() {
    scanf("%d", &n);
    REP(i,1,n) scanf("%d", ci+i);
    PER(i,n,1) {
        pa[i] = vi[ci[i]];
        vi[ci[i]] = i;
    }
    LL now = 1;
    for(int i = 1; i <= n; ++i) {
        Add(now, f[i]);
        if(pa[i]!=0 && pa[i]-i>1) Add(f[pa[i]], now);
    }
    printf("%lld\n", now);
    return 0;
}


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

using namespace std;

int main() {
	int ans = 0;
	string a;
	cin >> a;
	for (int i = 0; i < a.size(); ++i)
		if (a[i] == '+')
			++ans;
		else
			--ans;
	cout << ans << '\n';
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N,x;
    int a[210];
    cin>>N;
    for(int i=0; i<N; i++) cin>>a[i];
    int count =0;
    bool flag=true;
    while(flag==true){
        for (int i=0; i<N; i++){
            x=a[i];
            if (x%2==0) a[i] /=2;
            else flag=false;
            
        }
        if (flag==true) count +=1;
    }
    cout<<count<<endl;
}


Measured memory_bytes: 504
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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

#define v vector
#define ALL(x) x.begin(),x.end()
#define rALL(x) x.rbegin(),x.rend()
#define endl '\n'
#define DEBUG

template<typename T> void DBG(const char* name, T&& H) {
	cerr << name << " = " << H << ')' << endl;
}

template<typename T, typename... Args> void DBG(const char* names, T&& H, Args&&... args) {
	const char* NEXT = strchr(names+1, ',');
	cerr.write(names, NEXT-names) << " = " << H << " |";
	DBG(NEXT+1, args...);
}

#ifdef DEBUG
	#define dbg(...) cerr << __FUNCTION__ << ' ' <<__LINE__ << " : (", DBG(#__VA_ARGS__, __VA_ARGS__)
#else
	#define dbg(...)
#endif

using ll = long long;
using ld = long double;

const ll mod = 1e9 + 7;
const ld PI = acos(-1.0);
const ll maxN = 2e5+1;

int n;
vector<vector<int>> graph(maxN);
vector<vector<int>> mark(2);
vector<vector<int>> modulo(3);

void dfs(int node, int parent, int M) {
	mark[M].push_back(node);
	for(auto i : graph[node]) {
		if(i == parent) continue;
		dfs(i, node, M^1);
	}
}

void Solve() {
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		modulo[i%3].push_back(i);
	}
	for(int i = 0; i < n-1; i ++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	vector<int> ans(n+1);
	dfs(1, 1, 0);
	int f = 0, s = 1;
	if(mark[f].size() > mark[s].size()) swap(f, s);
	if(mark[f].size() <= n/3) {
		while(mark[f].size()) {
			ans[mark[f].back()] = modulo[0].back();
			mark[f].pop_back();
			modulo[0].pop_back();
		}
		while(mark[s].size()) {
			for(int i = 0; i < 3; i ++) {
				if(modulo[i].size() == 0) continue;
				ans[mark[s].back()] = modulo[i].back();
				mark[s].pop_back();
				modulo[i].pop_back();
				break;
			} 
		}
	}
	else {
		while(mark[f].size()) {
			if(modulo[1].size()) {
				ans[mark[f].back()] = modulo[1].back();
				mark[f].pop_back();
				modulo[1].pop_back();
			}
			else {
				ans[mark[f].back()] = modulo[0].back();
				mark[f].pop_back();
				modulo[0].pop_back();
			}
		}
		while(mark[s].size()) {
			if(modulo[2].size()) {
				ans[mark[s].back()] = modulo[2].back();
				mark[s].pop_back();
				modulo[2].pop_back();
			}
			else {
				ans[mark[s].back()] = modulo[0].back();
				mark[s].pop_back();
				modulo[0].pop_back();
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		cout << ans[i] << " ";
	}
	cout << endl;
}	

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int tt = 1;
	while(tt --) {
		Solve();
	}
	
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

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; }

const ll INF = 1LL<<60;
int MAX_N = 110;
int MAX_V = 100100;

int main()
{   
    int N;
    ll W;
    vll w(N), v(N);

    cin >> N >> W;
    rep(i, N) cin >> w[i] >> v[i];

    vvll dp(N+10, vll(100100, INF));
    dp[0][0] = 0;

    rep(i, N) rep(j, 100100) {
        chmin(dp[i+1][j], dp[i][j]);
        if(dp[i][j] + w[i] <= W) chmin(dp[i+1][j+v[i]], dp[i][j] + w[i]);
    }

    int ans = 0;
    rep(i, 100100) if(dp[N][i] <= W) ans = i;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 90836
#include <iostream>
using namespace std;
 
int main() {
	int m,f,r;
	while(1){
		cin >> m >> f >> r;
		if(m == -1 && f == -1 && r == -1)break;
 
		if(m == -1 || f == -1)cout << "F" << endl;
		else if(m + f >= 80)cout << "A" << endl;
		else if(m + f < 80 && 65 <= m +f)cout << "B" << endl;
		else if(m + f < 65 && 50 <= m + f)cout << "C" << endl;
		else if(m + f < 50 && 30 <= m + f){
			if(r >= 50)cout << "C" << endl;
			else  cout << "D" << endl;
		}
		else if(m + f < 30)cout << "F" << endl;
	}
	return 0;
}

Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  int n,k;
  cin>>n>>k;
  int x[n],y[n];
  vector<int> xs(n),ys(n);
  for(int i=0;i<n;i++){
    cin>>x[i]>>y[i];
    xs[i]=x[i];
    ys[i]=y[i];
  }
  sort(xs.begin(),xs.end());
  sort(ys.begin(),ys.end());
  ll c=(ll)(xs[n-1]-xs[0])*(ll)(ys[n-1]-ys[0]);
  for(int xi=0;xi<n-1;xi++){
    for(int xj=xi+1;xj<n;xj++){
      for(int yi=0;yi<n-1;yi++){
        for(int yj=yi+1;yj<n;yj++){
          int cnt=0;
          for(int i=0;i<n;i++){
            if(x[i]>=xs[xi]&&x[i]<=xs[xj]&&y[i]>=ys[yi]&&y[i]<=ys[yj]) cnt++;
          }
          if(cnt>=k) c=min(c,(ll)(xs[xj]-xs[xi])*(ll)(ys[yj]-ys[yi]));
        }
      }
    }
  }
  cout<<c;
}

Measured memory_bytes: 256
//
// Created by Hideaki Imamura on 2020-03-20.
//
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N, M;
priority_queue<int> que;
vector<i_i> ps;

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        ps.push_back(make_pair(a, b));
    }
    sort(ps.begin(), ps.end());


    ll ans = 0;
    int idx = 0;
    for (int i = 1; i <= M; ++i) {
        while (idx < N && ps[idx].first <= i) {
            que.push(ps[idx].second);
            idx++;
        }
        if (!que.empty()) {
            ans += que.top();
            que.pop();
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1908
function readline_STDIN()
    return Base.readline(Base.STDIN)
end

function exawizards2019_A(A::Base.Int64, B::Base.Int64, C::Base.Int64)

    if Base.isequal(A, B) && Base.isequal(B, C)
        return "Yes"
    else
        return "No"
    end

end

A, B, C = Base.parse.(Base.split(readline_STDIN()))
Base.println(Base.STDOUT, Main.exawizards2019_A(A, B, C))

Measured memory_bytes: 173616
#include<iostream>
#include<string>

using namespace std;

int main(void)
{
	int count[26]={};
	string s;
	cin >> s;
	for(int i=1;i<=s.size();i++)
		count[s[i-1]-'a']++;
	for(int i=1;i<=26;i++)
		if(count[i-1]%2!=0)
		{
			cout << "No" << endl;
			return 0;
		}

	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
long long N, A[87], CurrentMoney = 1000;
int main() {
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> A[i];
  for (int i = 1; i <= N - 1; i++) {
  long long Stocks = 0;
  if (A[i] < A[i + 1]) Stocks = CurrentMoney / A[i];
  CurrentMoney += (A[i + 1] - A[i]) * Stocks;
  }
  cout << CurrentMoney << endl;
}


Measured memory_bytes: 3600
#include<cstdio>
#include<algorithm>
const int MaxN=3010;
int N,A[MaxN],V[MaxN];
struct edge{int to;edge*next;}E[MaxN*2],*ne=E,*fir[MaxN];
void link(int a,int b){*ne=(edge){b,fir[a]};fir[a]=ne++;}
bool cmp(int i,int j){return A[i]<A[j];}
bool del[MaxN],vs[MaxN];
int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++)scanf("%d",A+i),V[i-1]=i;
	for(int i=1,a,b;i<N;i++)scanf("%d%d",&a,&b),link(a,b),link(b,a);
	std::sort(V,V+N,cmp);
	for(int*i=V,*j=V;j<V+N;i=j){
		for(;j<V+N&&A[*i]==A[*j];j++)if(!del[*j]){
			del[*j]=1;
			for(edge*e=fir[*j];e;e=e->next)if(!del[e->to]&&A[e->to]>A[*j]){
				del[e->to]=vs[e->to]=1;
			}
		}
	}
	for(int i=1,fl=1;i<=N;i++)if(vs[i]){
		fl?fl=0:putchar(' ');
		printf("%d",i);
	}
	puts("");
}

Measured memory_bytes: 256
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let mut vec: Vec<usize> = vec![];
    for _ in 0..N {
        vec.push(read());
    }
    let mut sum = 0;
    for i in 0..N {
        for j in i + 1..N {
            sum += vec[i] * vec[j];
        }
    }
    println!("{}", sum);
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		sc.close();
		
		if(A >= B)
			System.out.println("delicious");
		else if(A + X >= B)
			System.out.println("safe");
		else
			System.out.println("dangerous");
	}
}


Measured memory_bytes: 23380
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

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

    vector<string> v(n), b(m);
    for(int i = 0; i < n; i++)cin >> v[i];
    for(int i = 0; i < m; i++)cin >> b[i];

    for(int i = 0; i + m - 1< n; i++){
        for(int j = 0; j + m - 1< n; j++){
            bool fl = true;
            for(int k = i; k < i + m; k++){
                for(int l = j; l < j + m; l++){
                    if(v[k][l] != b[k - i][l- j])fl = false;
                }
            }
            if(fl){
                cout << "Yes";
                return ;
            }
        }
    }
    cout << "No";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


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

using namespace std;
#define ll long long

int main()
{
    int a,b,r;
    cin >> a >> b >> r;
    int cnt=0;
    for(int i=a;i<=b;i++)
        if(i%r==0)cnt++;
    cout<< cnt;
    return 0;
}


Measured memory_bytes: 3620
import math
import collections

n=int(input()) 
c = []
m = int(math.sqrt(n))

for x in range(1,m+1):
    for y in range(1,m+1):
        for z in range(1,m+1):
            tmp = x*x + y*y + z*z + x*y + y*z + z*x
            c.append(tmp)

cc = collections.Counter(c)
#print(cc)

for i in range(1,n+1):
    if i in cc:
        print(cc[i])
    else:
        print(0)

Measured memory_bytes: 50544
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
const long long INF = 1LL<<60;
#define pairint pair<int,int>
bool compare_by_b(pair<string, int> a, pair<string, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first < b.first;
    }
}
signed main(){
  int x=0,y=0,z=0,w=0,n=0;
std::cin >> x;
int a[x][3];
rep(i,x)std::cin >> a[i][0]>>a[i][1]>>a[i][2];
std::vector<std::vector<int> > dp(x+1,std::vector<int>(3,0));
for (size_t i = 0; i < x; i++) {
  for (size_t j = 0; j < 3; j++) {
    for (size_t k = 0; k < 3; k++) {
      if(j!=k)dp[i+1][k]=max(dp[i+1][k],dp[i][j]+a[i][k]);
    }
  }
}

rep(i,3){
  if(dp[x][i]>y)y=dp[x][i];
}
std::cout << y << '\n';
}


Measured memory_bytes: 8064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(2*b >= a) {
			System.out.println(0);
		}else {
			System.out.println(a-2*b);
		}

		sc.close();
	}
}

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

X, Y = MAP()

memo = list2d(1007, 1007, -1)
def rec(x, y):
    if memo[x][y] != -1:
        return memo[x][y]
    if x < 2 and y < 2:
        memo[x][y] = 0
        return 0
    res = 0
    for i in range(2, x+1):
        if not rec(x - i, y + i//2):
            res = 1
    for i in range(2, y+1):
        if not rec(x + i//2, y - i):
            res = 1
    memo[x][y] = res
    return res

# for i in range(X+1):
#     for j in range(Y+1):
#         rec(i, j)
# for i in range(X+1):
#     print(memo[i][:Y+1])

if abs(X - Y) >= 2:
    print('Alice')
else:
    print('Brown')


Measured memory_bytes: 11124
#include <bits/stdc++.h>
using namespace std;
char M[1005][1005];
int n, m, dp[1005][1005], MOD = 1e9 + 7;
long long f(int y, int x){
	if(y == n - 1 && x == m - 1) return 1;
	if(M[y][x] != '.') return 0;
	if(dp[y][x] != -1) return dp[y][x];
	if(y == n - 1) return dp[y][x] = f(y, x + 1)%MOD;
	if(x == m - 1) return dp[y][x] = f(y + 1, x)%MOD;
	
	return dp[y][x] = (f(y, x + 1) + f(y + 1, x))%MOD;
}
int main() {
	cin >> n >> m;
	memset(dp, -1, sizeof(dp));
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++) cin >> M[i][j];
	cout << f(0,0);
	return 0;
}

Measured memory_bytes: 5248
from collections import deque
n = int(input())
lists = deque()
A = deque() 
ans = 0
for _ in range(n):
    a = int(input())
    A.append(a)
    tmp = [list(map(int, input().split())) for _ in range(a)]
    lists.append(tmp)

for bit in range(1<<n):
    flag = True
    is_honest = [(bit>>i)&1 for i in range(n)]
    for i in range(n):#i人目の証言を検証する
        if is_honest[i] == 0:#i人目が「不親切」ならその人の証言は無視
            continue
        for k in range(A[i]):#i人目のk個目の証言を検証する
            x,y = lists[i][k]
            x -= 1
            #番号xとyが一致しているかどうか
            if is_honest[x] != y:
                flag = False
    if flag:
        ans = max(ans, sum(is_honest))
print(ans)
    


Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define PI 3.1415926536
#define MOD 1000003
using namespace std;
int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string s;
	cin>>s;
	if(s[0]!='A'){
		cout<<"WA";
		return 0;
	}
	int flagc = 0, flag = 0, in=-1;
	for(int i=2;i<=s.length()-2;i++){
		if(s[i]=='C'){
			flagc++;
			in = i;
		}
	}
	if(flagc!=1){
		cout<<"WA";
		return 0;
	}
	for(int i=1;i<s.length();i++){
		if(s[i]>='A'&&s[i]<='Z'&&i!=in){
			cout<<"WA";
			return 0;
		}
	}
	cout<<"AC";
	return 0;
}

Measured memory_bytes: 256