akhauriyash/Code-Regression huggingface dataset:
N, M = map(int, input().split())
MAX = 10000000

memo = [MAX for i in range(10000)]
memo[0] = 0
a = []
c = []
for i in range(M):
	tmpa, tmpb = map(int, input().split())
	tmpc = list(map(int, input().split()))
	bitc = 0
	for tmp in tmpc:
		tmp = tmp - 1
		bitc = bitc | (1<<tmp)
	a.append(tmpa)
	c.append(bitc)

for i in range(M):
	cost = a[i]
	bit = c[i]
	for idx in range(10000 - 1, -1, -1):
		if(memo[idx] < MAX):
			to = idx | bit
			memo[to] = min(memo[to], memo[idx] + cost)
if(memo[2**N - 1] != MAX):
	print(memo[2**N-1])
else:
	print(-1)


Measured memory_bytes: 3316
package main

import (
	"fmt"
	"math"
	"sort"
)

type ByAbs []int
func (a ByAbs) Len() int {return len(a)}
func (a ByAbs) Swap(i, j int) {a[i], a[j] = a[j], a[i]}
func (a ByAbs) Less(i, j int) bool {return (math.Abs(float64(a[i]))) < math.Abs(float64(a[j]))}

func main() {
	var N, L int
	fmt.Scanf("%d", &N)
	fmt.Scanf("%d", &L)

	tastes := make([]int, N)
	for i:=0; i<N; i++ {
		tastes[i] = L+i
	}
	sort.Sort(ByAbs(tastes))
	//fmt.Println(tastes)

	ans := 0
	for _, t := range tastes[1:] {
		ans += t
	}
	fmt.Println(ans)
}


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

main(){
  int H, W;
  char c;
  cin >> W >> H >> c;

  assert(3 <= W && W <= 21);
  assert(3 <= H && H <= 21);
  assert( W%2 && H%2 && 'A' <= c && c <= 'Z' );

  for ( int i = 0; i < H; i++ ){
    for ( int j = 0; j < W; j++ ){
      if ( i == 0 && j == 0 ||
           i == 0 && j == W-1 ||
           i == H-1 && j == 0 ||
           i == H-1 && j == W-1 ){
        cout << '+';
      } else if ( i == 0 || i == H-1 ){
        cout << '-';
      } else if ( j == 0 || j == W-1 ){
        cout << '|';
      } else if ( i == H/2 && j == W/2 ){
        cout << c;
      } else {
        cout << '.';
      }
    }
    cout << endl;
  }
}



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

int N;
int A[20];
int x[20][20];
int y[20][20];

int counter(int x) {
  if(x == 0) return 0;
  return counter(x >> 1) + (x&1);
}

int main() {
  cin >> N;
  for(int i = 1; i <= N; i++) {
    cin >> A[i];
    for(int j = 1; j <= A[i]; j++) {
      cin >> x[i][j] >> y[i][j];
    }
  }

  int ans = 0;
  for(int bits = 1; bits < (1<<N); bits++) {
    bool ok = true;
    for(int i = 1; i <= N; i++) {
      if(!(bits & (1 << (i-1)))) continue;
      for(int j = 1; j <= A[i]; j++) {
        if(((bits >> (x[i][j]-1)) & 1) ^ y[i][j]) ok = false;
      }
    }
    if(ok) ans = max(ans, counter(bits));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
using namespace std;

typedef long long LL;

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

inline void upd(int &x,int y) { x<y?x=y:0; }

int f[1<<15][15];
int sum[1<<15];
int e[15][15];
int main()
{
	int n=gi(),m=gi(),i,a,b,s,t,o,k;
	const int all=(1<<n)-1;
	
	while (m--) {
		a=gi()-1,b=gi()-1;
		e[a][b]=e[b][a]=gi();
		sum[1<<a|1<<b]+=e[a][b];
	}

	for (i=0;i<n;i++)
		for (s=0;s<(1<<n);s++)
			if (!(s>>i&1))
				sum[s|1<<i]+=sum[s];

	memset(f,-0x3f,sizeof(f));
	f[1][0]=0;
	for (s=1;s<(1<<n);s+=2)
		for (i=0;i<n;i++)
			if (f[s][i]>=0) {
				for (o=all^s,t=o;t;(--t)&=o)
					upd(f[s|t][i],f[s][i]+sum[t|1<<i]);
				
				for (k=0;k<n;k++)
					if (!(s>>k&1)&&e[i][k])
						upd(f[s|1<<k][k],f[s][i]+e[i][k]);
			}
	
	printf("%d\n",sum[all]-f[all][n-1]);
	return 0;
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
//BEGIN CUT HERE
int lcs(string X,string Y){
  const int N=max(X.size(),Y.size())+1;
  vector<vector<int> > c(N,vector<int>(N,0));
  int m = X.size();
  int n = Y.size();
  int maxl = 0;
  X = ' ' + X;
  Y = ' ' + Y;
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
      if(X[i]==Y[j]) c[i][j]=c[i-1][j-1]+1;
      else c[i][j]=max(c[i-1][j],c[i][j-1]);
      maxl=max(maxl,c[i][j]);
    }
  }
  return maxl;
}
//END CUT HERE
int main(){
  int q;
  cin>>q;
  while(q--){
    string s,t;
    cin>>s>>t;
    cout<<lcs(s,t)<<endl;
  }
  return 0;
}
/*
verified on 2017/06/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
*/

Measured memory_bytes: 6780
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    const long long INF = 100000000;
    long long N, M, R;
    cin >> N >> M >> R;
    vector<long long>r(R);
    for(long long i = 0; i < R; ++i){
        cin >> r[i];
        --r[i];
    }
    vector<vector<long long>>adj(N, vector<long long>(N, INF));
    for(long long i = 0; i < N; ++i){
        adj[i][i] = 0;
    }
    for(long long i = 0; i < M; ++i){
        long long A, B, C;
        cin >> A >> B >> C;
        --A;
        --B;
        adj[A][B] = adj[B][A] = C;
    }
    for(long long k = 0; k < N; ++k){
        for(long long i = 0; i < N; ++i){
            for(long long j = 0; j < N; ++j){
                if(adj[i][k] != INF && adj[k][j] != INF){
                    adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j]);
                }
            }
        }
    }
    long long ans = 100000000;
    sort(r.begin(), r.end());
    do{
        long long tmp = 0;
        for(int i = 1; i < R; ++i){
            tmp += adj[r[i-1]][r[i]];
        }
        ans = min(ans, tmp);
    }while(next_permutation(r.begin(), r.end()));
    cout << ans << endl;
}


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

tasks = []

for _ in range(N):
    a, b = map(int, input().split(' '))
    tasks.append((b, a))

tasks.sort()

t = 0
for b, a in tasks:
    t += a
    if t > b:
        print('No')
        break
else:
    print('Yes')


Measured memory_bytes: 35112
from collections import defaultdict
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
cost = [0,2,5,5,4,5,6,3,7,6]
dp = defaultdict(lambda:'')
for a in A:
    dp[cost[a]] = str(a)
for i in range(N+1):
    for a in A:
        if dp[i-cost[a]] != '':
            if len(dp[i]) <= len(dp[i-cost[a]]+str(a)):
                dp[i] = dp[i-cost[a]]+str(a)
        ans = dp[N]
ans = list(map(int,list(ans)))
ans.sort(reverse=True)
print(''.join(list(map(str,ans))))

Measured memory_bytes: 30180
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = 0;
		}
		for (int i = 0; i < K; i++) {
			int d = sc.nextInt();
			for (int j = 0; j < d; j++) {
				A[sc.nextInt() - 1] += 1;
			}
		}
		int ans = 0;
		for (int a : A) {
			if (a == 0) {
				ans++;
			}
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 46292
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
N = int(input())

t = 0
x, y = 0, 0

for _ in range(N):
    nt, nx, ny = inpl()
    d = abs(nx - x) + abs(ny - y)
    if d <= (nt-t) and (nt - t)%2 == d%2:
        t, x, y = nt, nx, ny
    else:
        print("No")
        break

else:
    print("Yes")


Measured memory_bytes: 3188
s = []

for i in range(3):
    array = list(map(int, input().split()))
    s.append(array)

sum_num = 0
for i in range(3):
    for j in range(3):
        sum_num += s[i][j]


magic_num = s[0][0] + s[1][1] + s[2][2]

if sum_num % 3 == 0 and magic_num * 3 == sum_num:
    print('Yes')
else:
    print('No')

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

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) i64((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

i64 NUM = 998244353LL;

class SegTree {
public:
  ////////////////////////////////////////////////////////
  // monoid
  using X = long long;
  X X_dot_X(const X &v1, const X &v2) {    
    return (v1 + v2) % NUM;
  }
  const X X_unit = 0;
  ////////////////////////////////////////////////////////
  typedef size_t idx_type;
  
  vector<X> data;

  idx_type n;
	
  SegTree(idx_type n_) {
    n = 1;
    while(n <= size_t(n_)) {
      n *= 2;
    }
    data.resize(n * 2 - 1, X_unit);
  }
  ~SegTree() {}
  
  X query(idx_type a, idx_type b, idx_type k, idx_type l, idx_type r) {
    if(r <= a || b <= l) {
      return X_unit;
    }
		
    if(a <= l && r <= b) {
      return data[k];
    }
    else {
      X vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
      X vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
      return X_dot_X(vl, vr);
    }
  }
  
  X query(idx_type a, idx_type b) {
    return query(a, b, 0, 0, n);
  }
	
  void update(idx_type i, X x) {
    i += n - 1;
    data[i] = x;
    while(i > 0) {
      i = (i - 1) / 2;
      data[i] = X_dot_X(data[i*2+1], data[i*2+2]);
    }
  }
};


int main(int argc, char *argv[]) {
  i64 N, K, i, j;
  cin >> N >> K;
  vi L(N), R(N);
  REP(0, K, i) {
    cin >> L[i] >> R[i];
  }

  SegTree tree(N);
  tree.update(0, 1);
  REP(1, N, i) {
    i64 ans = 0;
    REP(0, K, j) {
      i64 l = max(0LL, i - R[j]);
      i64 r = max(0LL, i - L[j] + 1);
      ans += tree.query(l, r);
      //cout << L[j] << " " << R[j] << " " << l << " " << r << " " << tree.query(l, r) << endl;
      ans %= NUM;
    }
    tree.update(i, ans);
  }
  cout << tree.query(N-1, N) << endl;

  return 0;
}


Measured memory_bytes: 10332
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int H,N;
    cin >> H >> N;
    int A[N];
    int sum=0;
    rep(i,N) {
        cin >> A[i];
        sum+=A[i];
    }
    if(sum>=H) cout << "Yes" << endl;
    else cout << "No" << endl;





}


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

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

	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int x, y;
	if (a > b){
		x = b;
	}
	else {
		x = a;
	}
	if (c > d) {
		y = d;
	}
	else {
		y = c;
	}
	cout << x + y << "\n";

	return 0;
}

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

const int maxn = 110;
double A[maxn];

int main(){
  double N;
  double total = 0;
  cin >> N;
  
  for(int i = 0; i < N; i++){
      cin >> A[i];
      total = (1 / A[i]) + total;
    }
  
    total = 1/total;
    cout << total; 
}


Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<algorithm>
#include <cstdint>
using namespace std;
  
int main(){
  string s;
  cin>>s;
 int n=s.size();
 string ans;
  for(int i=0;i<n;i+=2){
      ans += s.at(i);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
#define lint long long
static const int INF = 1 << 22;
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
/*******source code below********/
int main() {
	long long D; cin >> D;
	long long G; cin >> G;

	vector<int> p(D);
	vector<int> c(D);

	for (int i = 0; i < D; i++)
	{
		cin >> p[i] >> c[i];
	}
	vector<lint> bonus(D);
	for (int i = 0; i < D; i++)
	{
		bonus[i] = (i+1) * 100 * p[i] + c[i];
	}
	vector<string> S(1 << D); //2進数にした文字列を格納するstring
	for (int i = 0; i < 1 << D; i++)
	{
		for (int j = 0; j < D; j++)
		{
			int x = 1 << j;
			x &= i;
			S[i].push_back('0' + (x >> j));
		}
	}

	
	lint countmin = INF;

	for (int i = 0; i < 1 << D; i++)
	{
		string b = S[i]; 
		lint sum = 0;
		lint count = 0;


		for (int j = 0; j < D; j++)
		{
			if (b[j] == '1') {
				sum += bonus[j];
				count+=p[j];
			}
		}

		if (sum >= G) { //bonusのみを足し合わせた点数がDより高ければそれで終わり
			if (count < countmin) countmin = count;
			continue;
		}

		else {
			for (int j = D - 1; j >= 0; j--) {
				if (b[j] == '0') {
					for (int k = 0; k < p[j]-1; k++) {
						sum += 100 * (j+1);
						count++;
						if (sum >= G) {
							if (count < countmin) countmin = count;
							break;
						}
					}
				}
			}
		}
	}

	cout << countmin << endl;
	return 0;
}


Measured memory_bytes: 256
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
def gau(n):
    return (n-1)*(n-2)//2

def main():
    N,K = list(map(int,input().split()))
    S = str(input().rstrip())
    LS = len(S)
    SS = "R" + S + "L"
    ans = 0
    for i in range(1,LS+1):
        if SS[i] == "L" and SS[i-1] == "R":
            ans += 1
        elif SS[i] == "R" and SS[i+1] == "L":
            ans += 1
    print(min(N-1,N-ans+2*K))

if __name__ == "__main__":
    main()


Measured memory_bytes: 42304
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	string s;
	cin>>s;
	for(int i=0;i<s.length()-1;i++){
		if(s.substr(i,1)=="A"&&s.substr(i+1,1)=="C"){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}



Measured memory_bytes: 256
#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;

ll gosen = 5000000000000000;

int main() {
    string S; cin >> S;
    ll K; cin >> K;
    ll s = S.size();
    ll cnt = 0;
    ll a;
    rep(i, s){
        cnt++;
        a = S[i] - '0';
        if(a != 1){
            break;
        }
    }
    if(K < cnt){
        cout << 1 << endl;
    } else {
        cout << a << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
N = int(input())
list_AB = []
time = 0
flag = False
for i in range(N):
    list_AB.append(list(map(int, input().split())))
list_AB.sort(key=lambda x: (x[1], x[0]))
for i in range(N):
    time += list_AB[i][0]
    if time > list_AB[i][1]:
        flag = True
        break
if flag == False:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 66316
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
#define dcml(n) fixed<<setprecision(n)
//CONST
//------------------------------------------
const ll INF=1010000000000000017LL;
const ll MOD=1000000007LL;
const ld EPS=1e-12;
const ld PI=3.14159265358979323846;
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define  FORS(i,m,n) for(ll (i)=(m);   (i)<=(n); (i)++)
#define  RFOR(i,m,n) for(ll (i)=(n)-1; (i)>=(n); (i)--)
#define RFORS(i,m,n) for(ll (i)=(n);   (i)>(n);  (i)--)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
#define WREPS(i,in,j,jn) REPS(i,in)REPS(j,jn)
//-----------------------------------------
//namespace
using namespace std;
//ライブラリはここに
//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
vector<ll> G[220000];
//ll x[220000];
ll val[220000];
//-----------------------------------------
void dfs(ll p, ll a=0, ll z=-1){
    val[p]+=a;
    a=val[p];
    for(auto e:G[p]){
        if(e==z)continue;
        dfs(e,a,p);
    }
}

int main(void){
    ll N,Q;cin>>N>>Q;
    REP(i,N-1){
        ll a,b;cin>>a>>b;a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    REP(i,Q){
        ll p,x;cin>>p>>x;p--;
        val[p]+=x;
    }
    /*cout<<"-----------\n";
    REP(i,N){
        cout<<val[i]<<"\n";
    }
    cout<<"----------------\n";*/
    dfs(0);
    REP(i,N){
        cout<<val[i]<<"\n";
    }
}

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


int main(){
  vector<int> A(4);
  for(int i=0;i<4;i++)cin>>A.at(i);
  int t1=A.at(1)-A.at(0),t2=A.at(3)-A.at(2);
  int tot=t1+t2;
  sort(A.begin(),A.end());
  int time = A.at(3)-A.at(0);
  if(tot-time<=0)cout<<0<<endl;
  else cout<<tot-time<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<sstream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iostream>
int main()
{
	int h, n, sum = 0;
	std :: cin >> h >> n;
	int a[n];
	for(int i = 0; i < n; i++)
	{
		std :: cin >> a[i];
		sum = sum + a[i];
	}
	if(sum >= h)
		std :: cout << "Yes";
	else
		std :: cout << "No";
}

Measured memory_bytes: 3416
#include <iostream>
//#include <vector>
//#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <assert.h>
/*
#include <map>
#include <functional>
#include <set>
#include <iterator>
*/

using namespace std;
typedef long long ll;
ll N;

ll pwl(int val, int m) {
   ll retval = 1;
   for (int i=0;i<m;i++) {
      retval *= val;
   }
   return retval;
}

ll saiki_generate(ll val, int remain) {
   if (remain == 0) {
      if (val <= N) {
         char ptrval[20];
         char* ptr = ptrval;
         sprintf(ptrval, "%lld", val);
         int has3 = 0;
         int has5 = 0;
         int has7 = 0;
         while (*ptr != '\0') {
            switch(*ptr) {
               case '3':
                  has3 = 1; break;
               case '5':
                  has5 = 1; break;
               case '7':
                  has7 = 1; break;
            }
            ptr++;
         }
         if (has3 > 0 && has5 > 0 && has7 > 0) {
            return 1;
         } else {
            return 0;
         }
      } else {
         return 0;
      }
   } else {
      ll val10 = val * 10;
      return (saiki_generate(val10 + 3, remain-1)
       + saiki_generate(val10 + 5, remain-1)
        + saiki_generate(val10 + 7, remain-1));
   }
}

int main() {
   cin >> N;
   int keta = (int)(log10l(N)) + 1;
   //cout << keta << endl;
   if (keta <= 2) {
      cout << "0" << endl;
      return 0;
   }
   /*int m = (keta - 1);
   int val1 = pwl(3, m) - 3 * pwl(2,m) + 3;
   //int val2 = pwl(10, m);
   //cout << val1 << " " <<val2 << endl;*/
   ll retval = 0;
   for (int l=3;l<=keta;l++) {
      retval += saiki_generate(0, l);
   }
   cout << retval << endl;
   //cout << saiki_generate(0, keta) + val1 << endl;
}

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

const double pi  = 2 * acos(0.0);
const double eps = 1e-8;

#define REP(i,a,b) for(int i=(a); i<(b);++i)
#define rep(i,n) REP(i,0,n)
#define INF (1<<29)
#define INFLL (1LL<<62)

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

typedef int Cost;
struct Edge {
  int src, dst; Cost cost;
  Edge(int s, int d, Cost c) : src(s), dst(d), cost(c) {}
};

typedef vector<Edge>  Edges;
typedef vector<Edges> Graph;
typedef vector<Cost>  Array;
typedef vector<Array> Matrix;

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

int main(void) {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n, r = 0, maxi = r;
  string s;
  cin >> n >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'I') r++;
    else r--;
    maxi = max(r, maxi);
  }
  cout << maxi << endl;
  return 0; 
}


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v).begin(),(v).end()
#define COUT(x) cout<<(x)<<"\n"

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    priority_queue<int>que;
    int n,m,a;
    cin >> n >> m;
    REP(i,n){
        cin>>a;
        que.push(a);
    }
    REP(i,m){
        int num = que.top();
        que.pop();
        num /= 2;
        que.push(num);
    }
    ll ans = 0;
    while(!que.empty()){
        int num = que.top();
        que.pop();
        ans += num;
    }
    COUT(ans);
    return 0;
}


Measured memory_bytes: 892
from sys import stdin
from collections import deque


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ipt = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
    MOD = 100100100100100100

    pl = [0] * (N + 1)

    for a, b in ipt:
        if pl[a] == 0:
            pl[a] = [b]
        else:
            pl[a].append(b)
        if pl[b] == 0:
            pl[b] = [a]
        else:
            pl[b].append(a)

    que = deque([1])
    deep = [MOD] * (N + 1)
    deep[1] = 0
    deep[0] = 0
    arrow = [0] * (N + 1)
    cnt = 1

    while not not que:
        q = que.popleft()
        for i in pl[q]:
            if deep[i] != MOD:
                continue
            deep[i] = deep[q] + 1
            arrow[i] = q
            cnt += 1
            que.append(i)

    if N != cnt:
        print("No")
    else:
        print("Yes")
        for i in arrow[2:]:
            print(i)


if __name__ == "__main__":
    main()


Measured memory_bytes: 58204
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct fk{int id,val;}stk[N<<1],p[N<<1];
int n,m,q,top;
bool on(int x,int y){return (x==n||y==m||x==0||y==0);}
int get(int x,int y){
    if(!x)return y;
    if(y==m)return m+x;
    if(x==n)return m+n+m-y;
    if(!y)return 2*m+2*n-x;
    return 0;
}
bool cmp(fk a,fk b){return a.val<b.val;}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1,x,y,xx,yy;i<=q;i++){
        scanf("%d%d%d%d",&x,&y,&xx,&yy);
        if(!on(x,y)||!on(xx,yy)){--i;--q;continue;}
        p[(i<<1)-1]=(fk){i,get(x,y)};
        p[(i<<1)]=(fk){i,get(xx,yy)};
    }
    sort(p+1,p+2*q+1,cmp);
    for(int i=1;i<=2*q;i++)
        if(!top||p[i].id!=stk[top].id)stk[++top]=p[i];
        else --top;
    puts(top?"NO":"YES");
}


Measured memory_bytes: 2432
s = gets.chomp.chars
cnt_e = cnt_o = 0

s.each_with_index do |c,i|
  if i.even?
    cnt_e += 1 if c == "1"
    cnt_o += 1 if c == "0"
  else
    cnt_e += 1 if c == "0"
    cnt_o += 1 if c == "1"
  end
end
puts [cnt_e,cnt_o].min



Measured memory_bytes: 9468
//2019.8.3 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
typedef pair<int,LL> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define gc getchar
//inline char gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
//inline int read() {
//    res s=0,ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
inline int read() {
    res s=0,ch=gc(),w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
inline LL Read() {
    RG LL s=0;
    res ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s;
}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
//    if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=1e5+10;
namespace MAIN {
    int A,B,C;
    inline void MAIN() {
        A=read(),B=read(),C=read();
        if(B+C<=A)printf("%d\n",0);
        else printf("%d\n",B+C-A);
    }
}
int main() {
//    srand((unsigned)time(NULL));
//    freopen("nothard.in","r",stdin);
//    freopen("nothard.out","w",stdout);
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#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;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
const long long MOD = 1000000007;


ll gcd (ll a, ll b){ return b == 0? a : gcd(b, a % b); }
ll lcm (ll a, ll b){ return a * (b / gcd(a, b));}

ll extgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

//* calculate a^-1 mod m
ll mod_inverse(ll a, ll m){
    ll x, y;
    extgcd(a, m, x, y);
    return(m + x%m) % m;
}

void solve(long long N, std::vector<long long> A){
    ll sum = 0, sum2 = 0;
    REP(i, N){
        sum = (sum + A[i]) % MOD;
        sum2 = (sum2 + (A[i]*A[i]) % MOD) % MOD;
    }
    ll ans = ( (sum * sum) % MOD - sum2) % MOD;
    if(ans < 0) ans += MOD;
    ll fac = mod_inverse(2, MOD);
    ans = (ans * fac) % MOD;
    cout<<ans<<endl;

}
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 4468
#include <iostream>
using namespace std;
 
int main()
{
    int r;
    cin >> r;
    if(r < 1200){
        cout << "ABC" << endl;
    }else if(r < 2800){
        cout << "ARC" << endl;
    }else{
        cout << "AGC" << endl;
    }
    
    return 0;
}

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

    struct node{
        long int counter;
        bool visited;
        vector<long int> neighbours;
    };

    void dfs(vector<node> &graph, long int subtree){
        // cout << "A" << endl;
        graph[subtree].visited = true;
        for (auto it  = graph[subtree].neighbours.begin(); it != graph[subtree].neighbours.end(); ++it){
            // cout << "A";
            if(!graph[(*it)].visited){
                graph[(*it)].counter += graph[subtree].counter;
                dfs(graph,(*it));
            }
        }
    }

    int main(){
        long int n, q;
        cin >> n >> q;
        node a;
        a.counter = 0;
        a.visited = false;
        vector<node> graph(n+1,a);
        long int source, dest;
        for(long int i = 0; i < n-1; i++){
            cin >> source >> dest;
            graph[source].counter = 0;
            graph[dest].counter = 0;
            graph[source].neighbours.push_back(dest);
            graph[dest].neighbours.push_back(source);
        }
        long int p = 0,x = 0 ;
        for (int i = 0; i < q; i++){
            cin >> p >> x;
            graph[p].counter += x;
        }

        dfs(graph,1);

        for (auto it = graph.begin()+1 ; it != graph.end(); it++){
            cout << (*it).counter << " ";
        }cout << "\n";

        return 0;
    }

Measured memory_bytes: 22656
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, s, n) for(int i = s; i < n; i++)
#define rRep(i, n) for(int i = n - 1; i >= 0; i--)
#define pii pair<int, int>
#define vii vector<pair<int, int>>
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define endl "\n"



int32_t main() {
	FAST
	//ofstream fout ("test.out");
    //ifstream fin ("test.in");
 	int n;
 	cin >> n;
 	vi vec(n);
 	REP(i, 0, n)
 		cin >> vec[i];
 	map<int, int> ma;
 	ma[1 + vec[0]]++;
 	int count = 0;
 	REP(i, 1, n) {
 		count += ma[i + 1 - vec[i]];
 		ma[i + 1 + vec[i]]++;
 	}
 	cout << count << endl;
}

Measured memory_bytes: 27428
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,a,m) for(int i=a;i<n;i++)
using namespace std;
const int INF=INT_MAX,MOD=1e9+7;

int a[10000]; int cnt=0;

//nまでの素数を列挙
void Sieve_of_Eratosthenes(int n){
	n++;
    bool list[n]; rep(i,n) list[i]=1; //全数にフラグ
	//2の倍数,3の倍数…と削っていく
    for(int i=2;i*i<n;i++){
        if(list[i]){
            for(int j=2;i*j<n;j++) list[i*j]=0;
        }
    }
	//フラグが立っていれば素数
    for(int i=2;i<n;i++){
        if(list[i]&&i%5==1){
            a[cnt]=i; cnt++;
        }
    }
}

int main(){
    int n; cin>>n;
    Sieve_of_Eratosthenes(55555);
    rep(i,n){
        cout<<(i?" ":"")<<a[i];
    }
    cout<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define gec getchar
#define puc putchar
#define File(S) (freopen(S".in","r",stdin),freopen(S".out","w",stdout))
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&a){
	static char ch;
	static bool fg;
	for(ch=gec(),fg=0;ch<'0'||ch>'9';ch=gec())fg^=(ch=='-');
	for(a=0;ch>='0'&&ch<='9';ch=gec())a=((a+(a<<2))<<1)+(ch^'0');
	if(fg)a=-a;
}
template <typename T>
inline void print(T x){
	static int Buf[30],PS=0,BUF;
    if(x<0)puc('-'),x=-x;
    for(;x>=10;x=BUF){
    	BUF=(x/5)>>1;
    	Buf[++PS]=x-((BUF+(BUF<<2))<<1);
    }
    Buf[++PS]=x;
    while(PS)puc('0'^Buf[PS--]);
}
bool Check(int n,int Dis,int a,int b){
	int count=0;
	n--;
	for(int i=0;i<=n;i++){
		ll l=(ll)i*a-(ll)(n-i)*b,r=(ll)i*b-(ll)(n-i)*a;
    	if(l<=Dis&&Dis<=r)return 1;
	}
	return 0;
}
int n,a,b,c,d;
int main()
{
	read(n);read(a);read(b);read(c);read(d);
	printf("%s",Check(n,b-a,c,d)?"YES":"NO");
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

typedef long long ll;

int main(){
    int n;
    cin >> n;
    int rate[8], any = 0;
    FOR(i,0,8) rate[i] = 0;
    FOR(i,0,n){
        int in;
        cin >> in;
        if(in>=3200) any++;
        else rate[in/400]++;
    }
    int MIN = 0 ,MAX;
    FOR(i,0,8) if(rate[i] != 0) MIN++;
    MAX = MIN + any;
    if(MIN == 0) MIN = 1;
    cout << MIN << " " << MAX << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

const li inf = 1LL << 50;

li dp[2000][2000];
li dp_maxx[2000];
li dp_maxy[2000];
li dp_max = -inf;

void update(const li x, const li y, const li v) {
    dp[x][y] = max(dp[x][y], v);
    dp_maxx[y] = max(dp_maxx[y], v);
    dp_maxy[x] = max(dp_maxy[x], v);
    dp_max = max(dp_max, v);
};

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

    li n;
    cin >> n;
    vector<li> xs(3 * n);
    for (int i = 0; i < 3 * n; ++i) {
        cin >> xs[i];
        xs[i]--;
    }

    for (int i = 0; i < n; ++i) {
        dp_maxx[i] = -inf;
        dp_maxy[i] = -inf;
        for (int j = 0; j < n; ++j) {
            dp[i][j] = -inf;
        }
    }

    update(xs[0], xs[1], 0);

    li offset = 0;
    for (int itr = 0; itr < n - 1; ++itr) {
        const li p = xs[2 + itr * 3];
        const li q = xs[2 + itr * 3 + 1];
        const li r = xs[2 + itr * 3 + 2];

        // add, use 3
        if (p == q && q == r) {
            offset++;
            continue;
        }

        vector<tuple<li, li, li>> updates;

        // add, use 2
        if (p == q || q == r || p == r) {
            li pair, rem;
            if (p == q) {
                pair = p;
                rem = r;
            } else if (q == r) {
                pair = q;
                rem = p;
            } else {
                pair = r;
                rem = q;
            }
            for (int k = 0; k < n; ++k) {
                updates.emplace_back(k, rem, dp[k][pair] + 1);
                updates.emplace_back(k, rem, dp[pair][k] + 1);
            }
        }

        // add, use 1
        updates.emplace_back(q, r, dp[p][p] + 1);
        updates.emplace_back(p, r, dp[q][q] + 1);
        updates.emplace_back(p, q, dp[r][r] + 1);

        // no-add, use 3
        // reusing the dp table to avoid O(n^2) updates.

        // no-add, use 2
        for (int k = 0; k < n; ++k) {
            updates.emplace_back(k, p, dp_maxx[k]);
            updates.emplace_back(k, p, dp_maxy[k]);
            updates.emplace_back(k, q, dp_maxx[k]);
            updates.emplace_back(k, q, dp_maxy[k]);
            updates.emplace_back(k, r, dp_maxx[k]);
            updates.emplace_back(k, r, dp_maxy[k]);
        }

        // no-add, use 1
        updates.emplace_back(p, q, dp_max);
        updates.emplace_back(p, r, dp_max);
        updates.emplace_back(q, r, dp_max);

        for (auto &upd: updates) {
            update(get<0>(upd), get<1>(upd), get<2>(upd));
        }
    }

    li ans = dp_max;
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            if (x == y && y == xs[3 * n - 1]) {
                ans = max(ans, dp[x][y] + 1);
            }
        }
    }

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

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

namespace ABC085A
{
    class Program
    {
        static void Main(string[] args)
        {
            String s;

            s = Console.ReadLine();

            char[] cs = s.ToCharArray();

            cs[3] = '8';

            Console.WriteLine(cs);

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<char> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

ll my_gcd(ll a,ll b){
    if(a%b==0){
        return b;
    }
    return my_gcd(b,a%b);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vl A(N);
    vl cnt(1000001);
    rep(i,N){
        cin >> A[i];
        cnt[A[i]]++;
    }
    bool b=false;
    FOR(i,2,1000001){
        ll res=cnt[i];
        ll j=i;
        while(j+i<1000001){
            j+=i;
            res+=cnt[j];
        }
        if(res>1){
            b=true;
        }
    }
    if(!b){
        cout << "pairwise coprime" << endl;
        return 0;
    }
    vl acc0(N,A[0]);
    rep(i,N-1){//setwise
        acc0[i+1]=my_gcd(acc0[i],A[i+1]);
    }
    if(acc0[N-1]==1){
        cout << "setwise coprime" << endl;
        return 0;
    }
    cout << "not coprime" << endl;
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 26664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll a[200010];
int main() {
	ll n;
	cin>>n;
	for(ll i=0;i<n-1;i++){
		ll now;
		cin>>now;
		now--;
		a[now]++;
	}
	for(ll i=0;i<n;i++){
		cout << a[i]<<endl;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 5160
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
using namespace std;
 

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define pb push_back
#define forn(i, n) for (int i = 0; i < n; ++i)
#define int long long

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

 
const int MAXN = 3e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = INT64_MAX;


random_device rd;
mt19937 rnd(rd());


signed main() {
	FAST_IO;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int x = 1; x * x <= n; x++) {
			for (int y = x; x * x + y * y + x * y <= n; y++) {
				for (int z = y; z * z + x * x + y * y + x * y + y * z + z * x <= n; z++) {
					// cout << x << " " << y << " " << z  << " : " << z * z + x * x + y * y + x * y + y * z + z * x << "\n";
					if (z * z + x * x + y * y + x * y + y * z + z * x == i) {
						set<int> kek;
						kek.insert(x); kek.insert(y); kek.insert(z);
						if (kek.size() == 1) {
							cnt++;
						}
						if (kek.size() == 2) {
							cnt += 3;
						}
						if (kek.size() == 3) {
							cnt += 6;
						}
					}
				}
			}
		}
		cout << cnt << "\n";
	}
 	return 0;
}

Measured memory_bytes: 3644
program prob2
    implicit none

    integer(8)::i,ans,disc,AA,BB,M
    integer(8), allocatable::A(:),B(:), C(:,:)
    read(*,*) AA, BB, M
    allocate(A(AA))
    allocate(B(BB))
    allocate(C(3,M))
    read(*,*) A
    read(*,*) B
    read(*,*) C

    ans = minval(A) + minval(B)

    do i = 1, M
        disc = A(C(1,i)) + B(C(2,i)) - C(3,i)
        if(disc < ans) then
            ans = disc
        end if
    end do

    write(*,*) ans

    deallocate(A)
    deallocate(B)
    deallocate(C)

    stop
end program prob2

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 2;
typedef tuple<int, int, int> TQuery;

int color[N][11], n, m, Q, u, v, d, c;
TQuery q[N];
vector<int> a[N];

void Paint(int u, int d) {
    if(color[u][d]) return;
    color[u][d] = c;
    if(d == 0) return;
    Paint(u, d - 1);
    for(int v: a[u]) Paint(v, d - 1);
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> u >> v;
        a[u].pb(v), a[v].pb(u);
    }
    cin >> Q;
    for(int i = 1; i <= Q; ++i) {
        cin >> v >> d >> c;
        q[i] = make_tuple(v, d, c);
    }
    for(int i = Q; i >= 1; --i) {
        tie(v, d, c) = q[i];
        Paint(v, d);
    }
    for(int i = 1; i <= n; ++i) cout << color[i][0] << '\n';
}


Measured memory_bytes: 12024
#include <cstdio>
#include <utility>
#include <algorithm>

using LL = long long;
const int MAXN = (int)1e5;

struct Clue {
  int u, v, c;
  Clue(int u = 0, int v = 0, int c = 0) : u(u), v(v), c(c) {}
  bool operator<(const Clue &other) {
    return c < other.c;
  }
}; 
Clue clues[MAXN];

// 需要2个并查集,一个判断点是不是在同一棵树，一个判断点是否在同一个环
int tree_rt[MAXN], tree_size[MAXN];
int cycle_rt[MAXN], cycle_size[MAXN];

int find_rt(int u, int *rt, int *size) {
  if (rt[u] == u) return u;
  int fa = find_rt(rt[u], rt, size);
  size[fa] += size[u];
  size[u] = 0;
  rt[u] = fa;
  return fa;
}

void union_rt(int u, int v, int *rt, int *size) {
  int u_rt = find_rt(u, rt, size);
  int v_rt = find_rt(v, rt, size);
  if (u_rt == v_rt) return;
  size[v_rt] += size[u_rt];
  size[u_rt] = 0;
  rt[u_rt] = v_rt;
}

bool construct_graph(int n, int clues_num) {
  for (int i = 0; i < n; ++i) {
    tree_rt[i] = cycle_rt[i] = i;
    tree_size[i] = cycle_size[i] = 1;
  }
  std::sort(clues, clues + clues_num);
  int pos = 0;
  for (; pos < clues_num && clues[pos].c == 0; ++pos) {
    union_rt(clues[pos].u, clues[pos].v, tree_rt, tree_size);
  }
  int tree_num = 0;
  for (int i = 0; i < n; ++i) {
    if (find_rt(i, tree_rt, tree_size) == i) ++tree_num;
  }
  bool can_have_cycle = tree_num > 2;

  for (; pos < clues_num && clues[pos].c == 1; ++pos) {
    int u_rt = find_rt(clues[pos].u, tree_rt, tree_size);
    int v_rt = find_rt(clues[pos].v, tree_rt, tree_size);
    if (u_rt == v_rt || !can_have_cycle) return false;
    union_rt(u_rt, v_rt, cycle_rt, cycle_size);
  }
  return true;
}

std::pair<LL, LL> calc_graph_edge_limit(int n, int m) {
  LL lower_limit = 0, upper_limit = 0;
  int can_in_cycle_num = 0;
  for (int i = 0; i < n; ++i) {
    if (find_rt(i, tree_rt, tree_size) == i) {
      lower_limit += tree_size[i] - 1;
      upper_limit += tree_size[i] - 1;
      ++can_in_cycle_num;
      if (find_rt(i, cycle_rt, cycle_size) == i) {
        if (cycle_size[i] == 2) lower_limit += 3;
        else if (cycle_size[i] > 2) lower_limit += cycle_size[i];
      }
    }
  }
  upper_limit += (LL)can_in_cycle_num * (can_in_cycle_num - 1) / 2;
  return std::make_pair(lower_limit, upper_limit);
}

bool solve(int n, int m, int clues_num) {
  bool can_construct_graph = construct_graph(n, clues_num);
  if (!can_construct_graph) return false;
  
  std::pair<LL, LL> limit = calc_graph_edge_limit(n, m);
  LL edge_lower_limit = limit.first;
  LL edge_upper_limit = limit.second;
  if (edge_lower_limit <= m && m <= edge_upper_limit) return true;
  return false;
}

int main() {
  int n, m, clues_num;
  scanf("%d %d %d", &n, &m, &clues_num);
  for (int i = 0, u, v, c; i < clues_num; ++i) {
    scanf("%d %d %d", &u, &v, &c);
    clues[i] = Clue(u, v, c);
  }
  if (solve(n, m, clues_num)) puts("Yes");
  else puts("No");
  return 0;
}


Measured memory_bytes: 2944
{-# LANGUAGE ScopedTypeVariables #-}
import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.DeepSeq
import Data.Array
import Data.Bits
import Data.Char
import Data.Functor.Identity
import Data.List
import Data.Ord
import Data.Maybe
import Data.Tree
import Data.Tuple
import qualified System.IO
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.Sequence as Q
import qualified Data.ByteString.Char8 as B
import Data.Array.IO

main = do
  (n,l) <- getIntPair
  as <- getInts
  maybe (putStrLn "Impossible") (\ is -> putStrLn "Possible" >> mapM_ print is) $ solve n l as

solve :: Z -> Z -> [Z] -> Maybe [Z]
solve n l as = do
  let bs = zipWith (+) as (tail as)
  i <- (+1) <$> findIndex (>= l) bs
  return $ [1..i-1] ++ reverse [i+1 .. n-1] ++ [i]


 
type Z = Int
type Q = Rational
type R = Double
type S = String

fint :: (Integral a, Num b) => a -> b
fint = fromIntegral

getInt = fst . fromJust . B.readInt <$> B.getLine
getIntPair = (\[a,b]->(a,b)) <$> getInts
getInts = map (fst . fromJust . B.readInt) . B.words <$> B.getLine
getStr = B.unpack <$> B.getLine

yesNo :: Bool -> String
yesNo True = "YES"
yesNo False = "NO"

printList :: (Show a) => [a] -> IO ()
printList = putStrLn . unwords . map show

readLnList :: (Read a) => IO [a]
readLnList = map read . words <$> getLine


-----  Union-find
type UnionFindT v m a = StateT (M.Map v (UnionFindVal v)) m a
newtype UnionFindVal v = UnionFindVal v

runUnionFindT :: (Monad m) => UnionFindT v m a -> m a
runUnionFindT = flip evalStateT $ M.empty

runUnionFind = runIdentity . runUnionFindT

ufFresh :: (Monad m, Ord v) => v -> UnionFindT v m ()
ufFresh v = modify $ M.insert v (UnionFindVal v)

ufClass :: (Monad m, Ord v) => v -> UnionFindT v m v
ufClass v = do
  (UnionFindVal pv) <- gets (M.! v)
  if v == pv
    then return v
    else do
      c <- ufClass pv
      modify $ M.insert v (UnionFindVal c)
      return c

ufUnify v w = do
  cv <- ufClass v
  cw <- ufClass w
  modify $ M.insert cw (UnionFindVal cv)
  return $ cv /= cw


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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 3005, MOD = 998244353;
ll dp[N][N][2];

void add(ll &a, ll b) {
	a = (a + b) % MOD;
}

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

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	dp[a][b][1] = 1;

	for (int i = a; i <= c; i++) {
		for (int j = b; j <= d; j++) {
			if (i < c) {
				add(dp[i + 1][j][0], dp[i][j][0] * j);
				add(dp[i + 1][j][0], dp[i][j][1] * j);
			}
			if (j < d) {
				add(dp[i][j + 1][1], dp[i][j][0]);
				add(dp[i][j + 1][1], dp[i][j][1] * i);
			}
		}
	}

	cout << (dp[c][d][0] + dp[c][d][1]) % MOD;

	return 0;
}

Measured memory_bytes: 144356
N = int(input())
P = list(map(int,input().split()))

ans = "NO"

if sorted(P) == P:
    ans = "YES"

for i in range(N):
    for j in range(i+1,N):
        tmp = P[:]
        tmp[i],tmp[j] = tmp[j],tmp[i]
        if sorted(tmp) == tmp:
            ans = "YES"
            break

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(m,i,n) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back

typedef pair<ll,ll> point;

int main() {
  int k,n;
  cin >> n >> k;

  vector<int> x(n), y(n);
  vector<int> xary, yary;

  rep(i,n) {
    cin >> x[i] >> y[i];
    xary.pb(x[i]), yary.pb(y[i]);
  }

  sort(begin(xary), end(xary));
  sort(begin(yary), end(yary));

  ll ans = 1LL * (xary[n-1] - xary[0]) * (yary[n-1] - yary[0]);

  rep(xi,n)rep_r(xi+1,xj,n)rep(yi,n)rep_r(yi+1,yj,n) {
    int num = 0;
    ll lx = xary[xi], rx = xary[xj];
    ll by = yary[yi], uy = yary[yj];

    rep(i,n) if (lx <= x[i] and x[i] <= rx and by <= y[i] and y[i] <= uy) num++;

    if (num >= k) ans = min(ans, 1LL * (rx - lx) * (uy - by));
  }

  cout << ans << endl;
}


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

int N, M;
vector<vector<int> > G;

int s, t;

vector<bool> seen;
bool rec(int v, int p = -1) {
    if (v == s && p != -1) return true;
    if (v != s) seen[v] = true;
    for (auto nv :  G[v]) {
        if (nv == p || nv == t || seen[nv]) continue;
        if (rec(nv, v)) return true;
    }
    return false;
}
        

bool solve() {
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    map<int,int> degs;
    for (int v = 0; v < N; ++v) degs[(int)G[v].size()]++;

    for (auto it : degs) if (it.first % 2 != 0) return false;
    if (degs[6] > 0) return true;
    if (degs[4] > 2) return true;
    if (degs[4] <= 1) return false;

    vector<int> four;
    for (int v = 0; v < N; ++v) {
        if (G[v].size() == 4) four.push_back(v);
    }
    s = four[0], t = four[1];
    seen.assign(N, 0);
    bool ok1 = rec(s);
    s = four[1], t = four[0];
    seen.assign(N, 0);
    bool ok2 = rec(s);

    if (ok1 && ok2) return true;
    else return false;
}

int main() {
    if (solve()) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 6912