akhauriyash/Code-Regression huggingface dataset:
//Homework
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <map>
#include <stdio.h>
#include <string.h>
#include <initializer_list>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <set>
using namespace std;
const int INF = 1 << 29;
int main ()
{
    int N,M;
    cin >> N >> M;
    vector<int> A(M);
    long long sum = 0;
    for (int i = 0; i < M; i++) {
        cin >> A[i];
        sum += A[i];
    }
    long long result = N - sum;
    cout << (result  >= 0 ? result : -1) << endl;

    return 0;
}

Measured memory_bytes: 3232
#include <iostream>

using namespace std;

int main(void) {
  int i = 0;
  int n;
  cin >> n;
  while(++i <= n) {
    int x = i;
    if(x % 3 == 0) {
      cout << " " << i;
      if(i <= n) continue;
    }
    while(x) {
      if(x % 10 == 3) {
        cout << " " << i;
        if(i <= n) break;
      }
      x /= 10;
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3076
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
 
int main(void)
{
     int N,z=0;
     cin >> N;
     vector<int> a(N);
     for(int i =0;i < N;i++)
        cin >> a[i];
 
    for(int i = 0;true;i++){
        for(int j = 0;j < N;j++){
            if(a.at(j)%2 != 0){
                z=1;
                break;
            }
            a.at(j) /= 2;
        }
        if(z==1){
            cout << i << endl;
            break;
        }  
    }                                                                  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

// エラトステネスの篩[2,n]を列挙 O(nloglogn)
vector<lint> sieve_of_eratosthenes(lint n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (lint i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (lint k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<lint> primes;
    for (lint i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}

int main(void) {
    vector<lint> primes = sieve_of_eratosthenes(55555);
    vector<lint> a;
    int n; cin >> n;
    for (lint p : primes) {
        if (p % 5 == 1) {
            a.push_back(p);
        }
    }
    repeat (i, n) {
        cout << a[i] << " ";
    }
    return 0;
}

Measured memory_bytes: 384
from collections import deque

V, E = list(map(int, input().split()))
edge = [[] for i in range(V)]
in_num = [0] * V

for i in range(E):
    s, t = list(map(int, input().split()))
    edge[s].append(t)
    in_num[t] += 1
    
q = deque()

for i in range(V):
    if in_num[i] == 0: q.append(i)

ans = deque()

while q:
    v = q.popleft()
    
    ans.append(v)
    
    for u in edge[v]:
        in_num[u] -= 1
        if in_num[u] == 0: q.append(u)
        
for a in ans: print(a)


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

#A
def A():
    a, b, c = LI()
    if a + b >= c:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    s = SR(n)
    m = II()
    t = SR(m)
    ans = 0
    for si in s:
        ans = max(ans, s.count(si) - t.count(si))
    print(ans)
    return

#C
def C():
    n = II()
    ab = LIR(n)
    cd = LIR(n)
    ab.sort()
    cd.sort()
    check = [0 for i in range(n)]
    ans = 0
    for _, c in enumerate(cd):
        d = c[1]
        c = c[0]
        maxy = -1
        x = -1
        for k, a in enumerate(ab):
            b = a[1]
            a = a[0]
            if maxy < b and c > a and check[k] == 0 and d > b:
                maxy = b
                x = k
        if x != -1:
            ans += 1
            check[x] += 1
    print(ans)


    return

#D
def D():
    N = II()
    a = LI()
    b = LI()
    ans = 0
    for i in range(29):
        t = 2 ** i
        a2 = [A % (2 * t) for A in a]
        b2 = [B % (2 * t) for B in b]
        a2.sort()
        b2.sort()
        ansb = 0
        r1 = r2 = r3 = 0
        for A in reversed(a2):
            while r1 < N and A + b2[r1] < t:
                r1 += 1
            while r2 < N and A + b2[r2] < 2*t:
                r2 += 1
            while r3 < N and A + b2[r3] < 3*t:
                r3 += 1
            ansb += (r2 - r1) + (N - r3)
        ans += ((ansb %2 ) << i)
    print(ans)
    return

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


Measured memory_bytes: 39920
#include <stdio.h>

int main(void){

	int n,i,x,y;
	char m;
	int c[4][13]={};

	scanf("%d",&n);

	for(i=0;i<n*2;i++){
		//printf("*");
		scanf("%c %d",&m,&y);
		if(m=='S'){
			y--;
			c[0][y]=1;
		}
		else if(m=='H'){
			y--;
			c[1][y]=1;
		}
		else if(m=='C'){
			y--;
			c[2][y]=1;
		}
		else if(m=='D'){
			y--;
			c[3][y]=1;
		}
	}


	for(x=0;x<4;x++){
		for(y=0;y<13;y++){

			// printf("%d ",c[x][y]);

			if(c[x][y]==0){
				switch(x){
					case 0 :
					printf("S %d\n",y+1);
					break;
					case 1:
					printf("H %d\n",y+1);
					break;
					case 2:
					printf("C %d\n",y+1);
					break;
					case 3:
					printf("D %d\n",y+1);
					break;
				}
			}

		}
		// printf("\n");

	}

	return 0;
}


Measured memory_bytes: 2052
import sys
input = sys.stdin.readline
n = int(input())
s = input()
num = []
bl = 0
wh = 0
for i in range(n):
    if s[i] == "#":
        num.append([i,wh])
        bl += 1
    else:
        wh += 1
min = n
if len(num) > 0:
    for i in range(len(num)):
        temp = (num[i][0] - num[i][1]) + (n - bl - num[i][1])
        if temp < min:
            min = temp
    if min > bl:
        min = bl
    print(min)
else:
    print("0")


Measured memory_bytes: 29996
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using ll = long long;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b)a=b;};
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b)a=b;};

Int dfs(Int a,Int b,Int c,Int d,Int k){
  if(c==10) return 0;
  Int res=0;
  Int x=a%10,y=b%10+d;
  if(x<y){
    chmax(res,dfs(a/10,b/10,c+1,1,k)*10+(x+10-y));
    if(k>0) chmax(res,dfs(a/10,b/10,c+1,0,k-1)*10+(x+10-y));
  }else{
    chmax(res,dfs(a/10,b/10,c+1,0,k)*10+(x-y));
  }  
  return res;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int a,b,k;
  cin>>a>>b>>k;
  cout<<dfs(a,b,0,0,k)<<endl;
  return 0;
}



Measured memory_bytes: 3192
#include <stdio.h>

int w,h;
int map[50][50];

void rec(int x, int y){
	int i,j;
	map[x][y]=0;
	for(i=-1;i<2;i++){
		for(j=-1;j<2;j++){
			if(x+i>=0&&x+i<h&&y+j>=0&&y+j<w){
				if(map[x+i][y+j]){
					rec(x+i, y+j);
				}
			}
		}
	}
	return;
}

int main(void){
	int i,j,count;
	while(scanf("%d %d",&w,&h),w||h){
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				scanf("%d",&map[i][j]);
			}
		}
		count=0;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				if(map[i][j]){
					count++;
					rec(i,j);
				}
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 788
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
int main(){
	ll n;cin>>n;
  	ll dp[2001];
  	dp[0]=0;
  	dp[1]=0;
  	dp[2]=0;
  	dp[3]=1;
  	for(ll i=4;i<=n;i++){
    	dp[i]=1;
      	for(ll j=3;j<=i-3;j++){
        	dp[i]+=dp[j];dp[i]%=MOD;
        }
    }
  	cout<<dp[n];
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,sum=0;
    cin>>n>>k;
    int a[n];
    for(int i=0; i<n; i++){cin>>a[i];}

    sort(a,a+n);
    for(int i=0; i<k; i++)
    {
        //cout<<a[i]<<" ";
        sum+=a[i];
    }
    cout<<sum<<endl;

}


Measured memory_bytes: 3632
#include <atcoder/all>

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using namespace atcoder;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  string s; cin >> s;
  auto sa = suffix_array(s);
  lint ans = 1LL * s.size() * (s.size() + 1) / 2;
  for (auto x : lcp_array(s, sa)) {
    ans -= x;
  }

  cout << ans << endl;

  return 0;
}


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


int main() {
	int N;
	long long M;
	cin >> N >> M;
	vector<long long> A;
	for (int i = 0; i < N; i++) {
		long long tmp;
		cin >> tmp;
		A.emplace_back(tmp);
	}
	sort(A.begin(), A.end());
	vector<long long> prefix;
	prefix.push_back(0);
	for (int i = 0; i < N; i++) {
		prefix.push_back(prefix.back() + A[i]);
	}
	long long low = A[0] * 2, high = A[N - 1] * 2;
	while (low < high) {
		long long mid = (low + high + 1) / 2;
		long long counts = 0;
		for (int i = 0; i < N; i++) {
			long long cur = mid - A[i];
			int index = lower_bound(A.begin(), A.end(), cur) - A.begin();
			counts += N - index;
		}
		if (counts >= M) {
			low = mid;
		}
		else {
			high = mid - 1;
		}
	}
	long long tempSum = low;
	low = A[0] * 2, high = A[N - 1] * 2;
	long long finalCount = 0;
	long long finalSum = 0;
	while (low < high) {
		long long mid = (low + high) / 2;
		long long counts = 0;
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			long long cur = mid - A[i];
			int index = lower_bound(A.begin(), A.end(), cur) - A.begin();
			counts += N - index;
			sum += prefix[N] - prefix[index] + A[i] * (N - index);
		}
		if (counts > M) {
			low = mid + 1;
		}
		else {
			high = mid;
			finalCount = counts;
			finalSum = sum;
		}
	}
	// cerr << finalSum << " " << finalCount << " " << tempSum << endl;
	cout << finalSum + (M - finalCount) * tempSum << endl;
}

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

int main() {
  string s;
  cin >> s;
  ll n=s.size();
  vector<ll> cnt(3,0);
  
  rep(i,n){
    if(s[i] == 'a') cnt[0]++;
    else if(s[i] == 'b') cnt[1]++;
    else cnt[2]++;
  }

  if(n==1){
    cout << "YES" << endl;
    return(0);
  }
  
  if(abs(cnt[0]-cnt[1]) <= 1 && abs(cnt[1]-cnt[2]) <= 1 && abs(cnt[2]-cnt[0]) <= 1){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  
  return(0);
}

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

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

	int a[5];

	cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

	for(int i=0;i<5;i++)
	{
		if(a[i]==0)
		{
			cout << i+1 << '\n';
			break;
		}
	}

    return 0;
}

Measured memory_bytes: 3604
L, R = map(int, input().split())

result = 2019

for i in range(2019):
    if L+i > R-1:
        break;
    for j in range(i+1, 2019):
        if(L+j > R):
            break
        else:
            result = min(result,((L+i)*(L+j))%2019)

print(result)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.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); i++)

int choose(int a, int b){
    if(a < 2){
        return 0;
    } else {int c = 1;
        int d = 1;
        rep(i,b){
            c *= (a - i);
            d *= (b - i);
        }
        return c / d;
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    int ans;
    ans = choose(n,2) + choose(m,2);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
using namespace std;
#define MM 1000000000
#define MOD MM+7
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
//#define en cout << endl //セミコロンつけろ
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};


template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

long long pow_mod(long long n,long long k,long long m){
    if (k == 0){
        return 1;
    } else if (k % 2 == 1){
        return pow_mod(n,k-1,m)*n % m;
    } else {
        long long t = pow_mod(n,k/2,m);
        return t*t % m;
    }
}

int main(){
    int x,y,z; cin >> x >> y >> z;
    int ans = 1;
    x -= (y+2*z);
    ans += (x / (y+z));
    cout << ans << endl;
}

Measured memory_bytes: 888
#include <stdio.h>

int main(int argc, char const *argv[]) {
  unsigned long a, b, x;
  unsigned long i, numa,numb;
  unsigned long count=0;


  scanf("%lu %lu %lu",&a, &b, &x );

  numa = a / x + 1;//+1は０の分
  numb = b / x + 1;
  //printf("%lu %lu\n", numa,numb);
  count = numb - numa;
  if(a % x == 0)count++;
  printf("%lu\n", count);
  return 0;
}

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

int main() {
 int A,B,K;
 cin >> A >> B >> K;
 int count=0;
 for(int i=100;i >0 ; i--){
   if(A%i==0 && B%i==0){
    count++;
     if(count < K){
     continue;
     }
     if(count == K){
     cout << i << endl;
     break;
     }
   }
  if(A%i !=0 ||B%i !=0){
  continue;
  }
 }
}








Measured memory_bytes: 256
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]

a = [list(map(int, input().split())) for _ in range(h)]

#for p in c: print(p)
#for p in a: print(a)

n = 10
dp = [[1000 for _ in range(n)] for _ in range(n)]

for i in range(n):
    dp[0][i] = c[i][1]

#for p in dp: print(p)

for i in range(1, n):
    for j in range(n):
        for k in range(n):
            dp[i][j] = min(dp[i][j], c[j][k] + dp[i - 1][k])

#for p in dp: print(p)

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            ans += dp[n - 1][a[i][j]]

print(ans)

Measured memory_bytes: 3444
#include<stdio.h>
int main(void){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if(a==b)
    printf("%d",c);
  if(b==c)
    printf("%d",a); 
  if(a==c)
    printf("%d",b);
 return 0;
}


Measured memory_bytes: 128
//Keep Working Hard
  // I__Like__Food
  #include<bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp> 
  #include <ext/pb_ds/tree_policy.hpp>
  #pragma comment(linker, "/stack:200000000")
  #define rep(i,a,b) for(int i = a; i <=b; i++)
  #define rep2(i,a,b) for(int i = a; i>=b; i--)
  #pragma GCC optimize("O3")
  #pragma GCC optimize("Ofast") 
  #pragma GCC optimize("unroll-loops")
  using namespace std;
  using namespace __gnu_pbds;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define f first
  #define s second
  #define endl "\n"
  #define int long long
  #define all(v) v.begin(),v.end()
  #define PB push_back
  #define MP make_pair
  #define double long double
  #define trace1(x)                cerr<<#x<<": "<<x<<endl
  #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  #define cases int testcases;cin>>testcases; while(testcases--)
  #define MOD 998244353
  #define N 100005
  #define INF 1e16
  const double PI = acos(-1);


vector<int> toposort;

vector<int> adj[N];
bool vis[N];

void dfs(int s)
{
  if(!vis[s])
  {
    vis[s] = true;
    for(auto i : adj[s])
    {
      if(!vis[i])
      {
        dfs(i);
      }
    }

  }

  toposort.push_back(s);
}

int dp[N+1];
int32_t main()
{






// dp[s] denotes the longest path starting at s



  int n, m;
  cin >> n >> m;

  vector<pair<int,int>> v;



  for(int i = 1; i <= m; i++)
  {
    int x, y;
    cin >> x >> y;
    adj[x].PB(y);
  }

  for(int i = 1; i <= n; i++)
    {
      if(!vis[i])
      {
        dfs(i);
      }
    }

    // for(auto i : toposort)
    // {
    //   cout << i << " ";
    // }

    for(auto &i : toposort)
    {
      for(auto &j : adj[i])
      {
        dp[i] = max(dp[i],1 + dp[j]);
      }
    } 


    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
      ans = max(ans,dp[i]);
    }
    cout << ans;





  return 0;
  
}  

Measured memory_bytes: 9332
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rrep(i, n) for(int i=((int)(n));i>0;i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)	
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define REVSORT(c) SORT(c);REVERSE(c)
#define ALL(x) (x).begin(),(x).end()
#define INF 1e9
const long long MOD = 1000000007;
typedef long long ll;

int main(){
	int N, A, B;
	cin >> N >> A >> B;
	cout << min(A * N, B) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i,n) for(int i = 0;i<n;i++)
#define F first
#define S second
typedef long long ll;
typedef pair<ll, ll> pll;

const int maxn = 300005;

pll a[maxn];


int main() {
	ios;
	int n;
	cin >> n;
	rep(i, n) cin >> a[i].S >> a[i].F;
	sort(a, a + n);

	ll t = 0;
	rep(i, n) {
		t += a[i].S;
		if (t > a[i].F) {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n" ;
	return 0;
	return 0;
}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N;
    cin>>N;
    vector<ll> A(N);
    rep(i,N){
        cin>>A.at(i);
    }
    vector<vector<ll>> dp(2,vector<ll>(N));
    dp[0][0]=A.at(0);
    dp[1][0]=-A.at(0);
    rep(i,N-2){
        chmax(dp[0][i+1],dp[0][i]+A.at(i+1));
        chmax(dp[0][i+1],dp[1][i]-A.at(i+1));
        chmax(dp[1][i+1],dp[0][i]-A.at(i+1));
        chmax(dp[1][i+1],dp[1][i]+A.at(i+1));
    }
    cout<<max(dp[0][N-2]+A.at(N-1),dp[1][N-2]-A.at(N-1))<<endl;
}

Measured memory_bytes: 3328
n, m = map(int, input().split())
T = []
A = [str(0) for _ in range(n)]
for i in range(m):
  s, t = map(int, input().split())
  T.append([s, t])
f = True
for i in range(m):
  for j in range(i, m):
    if (T[i][0] == T[j][0] and T[i][1] != T[j][1]) or (T[i][0] == 1 and T[i][1] == 0 and n > 1):
      f = False
      break
  A[T[i][0]-1] = str(T[i][1])
if n == 1 and m == 0:
  print(0)
  exit()
elif A[0] == "0" and len(A) > 1:
  A[0] = "1"
if f: print("".join(A))
else: print(-1)

Measured memory_bytes: 3064
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int[] a = new int[n + 2];
			a[0] = a[n + 1] = 0;
			IntStream.rangeClosed(1, n).forEach(i -> a[i] = scanner.nextInt());
			int sum = IntStream.rangeClosed(0, n).map(i -> Math.abs(a[i] - a[i + 1])).sum();
			IntStream.rangeClosed(1, n).map(
					i -> sum - Math.abs(a[i] - a[i - 1]) - Math.abs(a[i] - a[i + 1]) + Math.abs(a[i - 1] - a[i + 1]))
					.forEach(System.out::println);
		}
	}
}


Measured memory_bytes: 81176
/* ex 9_2
   riverstone */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100001

//リストのノード（スタック内の各データ）の定義
typedef struct node{
    char elem;
    struct node *next;
} node;

//スタックにデータを追加
//先頭を示すノードと追加するデータを引数にする
void push(node **first, char elem){
    //追加する分の領域を確保
    node *new = calloc(1, sizeof(node));
    if(new == NULL) exit(1);
    new->elem = elem;
    new->next = *first;
    *first = new;
}

//スタックからデータを取り出す
char pop(node **first){
    char elem;
    node *tmp = *first;
    if(tmp == NULL) exit(1);
    elem = tmp->elem;
    *first = tmp->next;
    //取り出したノードのメモリを解放
    free(tmp);
    return elem;
}

int main(void){
    //最初のノードの指す先
    node *first = NULL;
    int i,ret = 0;
    //入力する配列を定義
    char cube_input[SIZE];
    scanf("%s", cube_input);
    
    for (i=0;i<strlen(cube_input);i++){
        //最初のキューブ、及び赤色のキューブと青色のキューブが隣り合っている時
        if (first == NULL || cube_input[i] == first -> elem){
            push(&first, cube_input[i]);
        }

        //隣り合っていない場合はそのまま追加
        else{
            //スタックからデータを取り出す。
            pop(&first);
            //2つキューブを取り除けたことになる
            ret += 2;
        }
    }
    printf("%d\n", ret);
    return 0;
}

Measured memory_bytes: 4840
#144_D
import math
a, b, x = map(int, input().split())
if 2 * x > (a ** 2) * b:
    k = 2 * ((a ** 2) * b - x) / (a ** 3)
    print(math.degrees(math.atan(k)))
else:
    k = a * (b ** 2) / (2 * x)
    print(math.degrees(math.atan(k)))

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

int main() {
    int N; cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; ++i) cin >> H[i];
    
    int res = 0;
    int current_max = 0;
    for (int i = 0; i < N; ++i) {
        // i 番目が、i-1 番目以前の最大値以上だったらカウント
        if (H[i] >= current_max) ++res;

        // これまでの最大値を新たに更新する
        if (current_max < H[i]) current_max = H[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 384
#include<stdio.h>
int h,w;
int map[50][50];
void func(int ,int);
int main(void){
	while(1){
		scanf("%d %d",&w,&h);
		if(h==0 && w==0){
			break;
		}
		int i,j;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				scanf("%d",&map[i][j]);
			}
		}
		/*for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				printf("%d ",map[i][j]);
			}
			printf("\n");
		}*/
		int cnt=0;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				if(map[i][j]==1){
					map[i][j]=0;
					func(i,j);
					cnt++;
				}
			}
		}
		printf("%d\n",cnt);
		cnt=0;
	}
	return 0;
}
void func(int y,int x){
	int dy[8]={1,0,0,-1,-1,-1,1,1},dx[8]={0,1,-1,0,-1,1,-1,1};
	int i,j,xx,yy;
	for(i=0;i<8;i++){
		yy=y+dy[i];
		xx=x+dx[i];
		if(yy>=0 && yy<h && xx>=0 && xx<w && map[yy][xx]==1){
			map[yy][xx]=0;
			func(yy,xx);
		}
	}
}

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

int main() {
  int N;
  cin >> N;
  vector<int> h(N);
  rep (i, N) cin >> h[i];//h[i]は足場i+1の高さ。
  vector<int> dp(N);
  //vector dp[i]には、足場i+1まで到達した場合の最小コストを記入する。
  rep(i,N){
    if(i==0)dp[0]=0;//足場1にいるとき(i=0)、コストは0
    else if(i==1)dp[1]=abs(h[1]-h[0]);//足場2にいるとき、足場1からくることだけを考える
    else dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]));//足場3以上の時は両方計算して小さいほう
  }
  cout << dp[N-1] << endl;
  return 0;
}


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

int main(){
  int H,W; cin >> H >> W;
  int Ch,Cw,Dh,Dw; cin >> Ch >> Cw >> Dh >> Dw;
  Ch--; Cw--; Dh--; Dw--;
  vector<string> S(H);
  for(int i=0; i<H; i++) cin >> S[i];
  
  vector<vector<bool>> visited(H,vector<bool>(W,false));
  int count_warp=0;
  queue<pair<int,int>> q,w;
  w.emplace(Ch,Cw);
  
  while(!w.empty()){
    while(!w.empty()){
      pair<int,int> t=w.front();
      if(visited[t.first][t.second]==false){
        q.push(t);
        visited[t.first][t.second]=true;
      }
      w.pop();
    }
    while(!q.empty()){
      pair<int,int> t=q.front();
      int tf=t.first, ts=t.second;
      
      if(tf-1>=0){
        if(visited[tf-1][ts]==false && S[tf-1][ts]=='.'){
          q.emplace(tf-1,ts);
          visited[tf-1][ts]=true;
        }
      }
      if(ts-1>=0){
        if(visited[tf][ts-1]==false && S[tf][ts-1]=='.'){
          q.emplace(tf,ts-1);
          visited[tf][ts-1]=true;
        }
      }
      if(tf+1<H){
        if(visited[tf+1][ts]==false && S[tf+1][ts]=='.'){
          q.emplace(tf+1,ts);
          visited[tf+1][ts]=true;
        }
      }
      if(ts+1<W){
        if(visited[tf][ts+1]==false && S[tf][ts+1]=='.'){
          q.emplace(tf,ts+1);
          visited[tf][ts+1]=true;
        }
      }
      
      for(int i=-2; i<=2; i++){
        for(int j=-2; j<=2; j++){
          if(0<=tf+i && tf+i<H && 0<=ts+j && ts+j<W){
            if(visited[tf+i][ts+j]==false&&S[tf+i][ts+j]=='.'){
              w.emplace(tf+i,ts+j);
            }
          }
        }
      }
      
      q.pop();
    }
    if(visited[Dh][Dw]==true){
      cout << count_warp << endl;
      return 0;
    }else{
      count_warp++;
    }
  }
  cout << "-1" << endl;
}

Measured memory_bytes: 6016
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin >> N;
    int A[N], B[N];
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        B[i] = A[i] - (i + 1);
    }

    sort(B, B + N);

    int b = (N % 2 == 0)?B[N / 2 - 1]:B[(N + 1) / 2 - 1];

    long long sum = 0;
    for (int i = 0; i < N; ++i) sum += abs(B[i] - b);

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1792
a = (1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51)
K = int(input())
print(a[K-1])

Measured memory_bytes: 3060
house = [[[0 for i in range(10)]for j in range(3)]for k in range(4)]
n = int(input())
for i in range(n):
	b,f,r,v = map(int,input().split())
	house[b-1][f-1][r-1] += v

for i in range(4):
	for j in range(3):
		for k in range(10):
			print(' ',end='')
			if k != 9:
				print(house[i][j][k],end='')
			else:
				print(house[i][j][k])
	if i<3:
		print('####################')


Measured memory_bytes: 5636
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a;
    string s;
    cin >> a >> s;
    if(a >= 3200) cout << s << endl;
    else cout << "red" << endl;
}

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

int main() {
    int N;
    cin >> N;
    int64_t ans = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 3 && i % 5) {
            ans += i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
from collections import deque
def _flip(a, swap_pair):
    for i, j in zip(*swap_pair):
        a[i], a[j] = a[j], a[i]
    return a

swap_pair = (
    [[1, 2, 3, 15, 21], [28, 29, 30, 16, 19]],
    [[7, 8, 9, 13, 10], [22, 23, 24, 18, 12]],
    [[1, 4, 7, 10, 16], [24, 27, 30, 21, 18]],
    [[3, 6, 9, 12, 15], [22, 25, 28, 19, 13]]
)
def flip(a):
    for pair in swap_pair:
        yield _flip(a[:], pair)

for _ in [0]*int(input()):
    puzzle = [0]+list(map(int, input().split()))
    dq = deque([(puzzle, 0, -1)])
    popleft, append = dq.popleft, dq.append

    while dq:
        p, cnt, i = popleft()
        if len(set(p[1:10])) == len(set(p[10:13])) == len(set(p[13:16])) == len(set(p[16:19])) == len(set(p[19:22])) == 1:
            print(cnt)
            break
        cnt += 1
        for j, _p in enumerate(flip(p)):
            if i == j:
                continue
            append((_p, cnt, j))


Measured memory_bytes: 9508
#include<bits/stdc++.h>
	using namespace std;
	#define int long long int
	#define double long double
	#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#define mod 1000000009
	#define endl "\n"

	vector<int> v(5001);

	int func(int st, int e, string &s, int n)
	{
		if(st>e)
			return -1;
		unordered_map<int, vector<int>> m;
		int c=0;
		int mid=(st+e)/2;
		vector<int> v1;
		for(int i=n-mid;i<n;i++)
		{
			c=(c+(((s[i]-96)*v[i-n+mid])%mod))%mod;
		}
		// cout<<mid<<' '<<c<<endl;
		m[c].push_back(n-mid);
		v1.push_back(c);
		for(int i=n-mid-1;i>=0;i--)
		{
			c=(c-((s[i+mid]-96)*v[mid-1])%mod)%mod;
			if(c<0)
				c+=mod;
			c=(c*31)%mod;
			c=(c+s[i]-96)%mod;
			m[c].push_back(i);
			if(m[c].size()==1)
				v1.push_back(c);
			// cout<<mid<<' '<<i<<' '<<c<<endl;
		}
		int f=0;
		for(int i=0;i<v1.size();i++)
		{
			int x=m[v1[i]][0];
			int s=m[v1[i]].size();
			int y=m[v1[i]][s-1];
			if(x-y>=mid)
			{
				f=1;
				break;
			}
		}
		if(f)
		{
			int x=func(mid+1, e, s, n);
			if(x==-1)
				return mid;
			return x;
		}
		return func(st, mid-1, s, n);
	}
	 
	int32_t main()
	{
		fast;
		int x=1;
		v[0]=1;
		for(int i=1;i<=5000;i++)
		{
			x=(x*31)%mod;
			v[i]=x;
		}
		int n;
		cin>>n;
		string s;
		cin>>s;
		int x1=func(1, n/2, s, n);
		if(x1==-1)
		{
			cout<<0<<endl;
		}
		else
		{
			cout<<x1<<endl;
		}
		return 0;
	}

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

int n, a[100005];

double iabs(double x) {return x > 0 ? x : -x;}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    double T = a[n] / 2.0;
    int t = 1;
    for (int i = 1; i <= n; i++) {
        if (iabs(a[i] - T) < iabs(a[t] - T)) t = i;
    }
    printf("%d %d\n", a[n], a[t]);
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main(int argc, char const *argv[])
{
	ll n;
	vector<ll> a;
	cin >> n;
	for (ll i = 0; i < n; ++i)
	{
		ll ai;
		cin >> ai;
		a.push_back(ai);
	}
	sort(a.begin(), a.end());
	ll ans = 0;
	if (n%2==0) {
		for (int i = 0; i < n; ++i)
		{
			if (i<n/2) ans -= a[i];
			else ans += a[i];
		}
		ans *= 2;
		ans += a[n/2-1] - a[n/2];
	}
	else {
		ll sum0 = 0, sum1 = 0;
		for (int i = 0; i < n; ++i)
		{
			if (i<n/2) sum0 -= a[i];
			else sum0 += a[i];
		}
		sum0 *= 2;
		sum0 -= a[n/2+1] + a[n/2];
		for (int i = 0; i < n; ++i)
		{
			if (i<(n+1)/2) sum1 -= a[i];
			else sum1 += a[i];
		}
		sum1 *= 2;
		sum1 += a[(n+1)/2-1] + a[(n+1)/2-2];
		ans = max(sum0, sum1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1400
#include<stdio.h>


bool solve(int i,int m,int A[],int n){
    if(m == 0){
        return true;
    } 
    if(i >= n || m < 0){
        return false;
    }
    bool res = solve(i+1,m,A,n) || solve(i+1,m - A[i],A,n);
    return res;
}
int main(){
    int n,q,m;
    scanf("%d",&n);
    int A[n];
    for(int i = 0;i < n;i++){
        scanf("%d",&A[i]);
    }
    scanf("%d",&q);
    for(int i = 1;i <= q;i++){
        scanf("%d",&m);
        if(solve(0,m,A,n)){
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }
}



Measured memory_bytes: 2700
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  ios_base::sync_with_stdio(false);
 string s;
 cin >> s;
 bool flag = true;
 for(int i =1 ; i < s.size() ; i++){
 	if(s[i]==s[i-1]){
      flag = false;
      break ;
    }
 }
 cout << (flag?"Good":"Bad") << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>

using namespace std;

long long MOD = 1000000007;

long long we_love_abc(string s) {
  long long dp[100001][4];
  memset(dp, 0, sizeof(dp));

  dp[0][0]  = 1;
  if(s[0] == 'A') {
    dp[0][1] = 1;
  } else if(s[0] == '?') {
    dp[0][0] = 3;
    dp[0][1] = 1;
  }
  for(int i=1;i<s.size();i++) {
    // j==0 && s[i] == 'a';
    if(s[i] == 'A') {
      dp[i][0] = dp[i-1][0];
      dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD;
      dp[i][2] = dp[i-1][2];
      dp[i][3] = dp[i-1][3];
      continue;
    }
    if(s[i] == 'B') {
      dp[i][0] = dp[i-1][0];
      dp[i][1] = dp[i-1][1];
      dp[i][2] = (dp[i-1][2] + dp[i-1][1]) % MOD;
      dp[i][3] = dp[i-1][3];
      continue;
    }
    if(s[i] == 'C') {
      dp[i][0] = dp[i-1][0];
      dp[i][1] = dp[i-1][1];
      dp[i][2] = dp[i-1][2];
      dp[i][3] = (dp[i-1][3] + dp[i-1][2]) % MOD;
      continue;
    }
    // s[i] == '?'
    for(int j= 0;j<4;j++) {
      dp[i][j] = (dp[i-1][j]*3) % MOD;
    }
    dp[i][1] = (dp[i][1] + dp[i-1][0]) % MOD;
    dp[i][2] = (dp[i][2] + dp[i-1][1]) % MOD;
    dp[i][3] = (dp[i][3] + dp[i-1][2]) % MOD;
  }
  return dp[s.size()-1][3];
}


int main() {
  string s;
  cin >> s;
  cout << we_love_abc(s);
}


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

int main()
{
    std::string str;
    std::cin >> str;

    if(str[2]==str[3] && str[4]==str[5]){
     std::cout << "Yes" << std::endl;
    }
    else{
        std::cout << "No" << std::endl;
    }
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
using tii = tuple<int, int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF (ll)1E9
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}

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

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

class CompareDist
{
public:
	bool operator()(tii n1, tii n2) {
		return get<1>(n1) > get<1>(n2);
	}
};

void solve(int n) {
	vi hasi(n-1), cost(n-1);
	int sum = 0,sumscr=0,st=-1,en;
	vector<vector<tuple<int, int>>> g(n);
	rep(i, n - 1) {
		cin >> hasi[i];
	}
	rep(i, n - 1) {
		cin >> cost[i];
		sum += cost[i];
	}
	rep(i, n - 1) {
		tuple<int, int> t = make_tuple(hasi[i] - 1, cost[i]);
		g[i + 1].push_back(t);
		t = make_tuple(i + 1, cost[i]);
		g[hasi[i] - 1].push_back(t);
	}
	rep(i, n - 1) {
		if (g[i + 1].size() >= 2 && g[hasi[i] - 1].size() >= 2) {
			sumscr += cost[i];
		}
	}
	rep(i, n) {
		if (g[i].size() >= 2 && st == -1)en=st = i;
	}

	//cout << sum << " " << sumscr << endl;

	priority_queue<tii, vector<tii>, CompareDist> q;
	vi d = vector<int>(n, INT_MAX);
	d[st] = 0;
	q.emplace(st, 0);
	while (!q.empty()) {
		tii p = q.top(); q.pop();
		int v = get<0>(p);
		if (d[v]< get<1>(p))continue;
		for (int i = 0; i<g[v].size(); i++) {
			tii t = g[v][i];
			if (g[get<0>(t)].size() >= 2 && d[get<0>(t)]>d[v] + get<1>(t)) {
				d[get<0>(t)] = d[v] + get<1>(t);
				q.emplace(get<0>(t), d[get<0>(t)]);
				//en = get<0>(t);
			}
		}
	}
	int maxx = -1;
	rep(i, d.size()) {
		if (d[i] != INT_MAX&&d[i] > maxx) {
			maxx = d[i];
			en = i;
		}
	}
	d = vector<int>(n, INT_MAX);
	d[en] = 0;
	q.emplace(en, 0);
	while (!q.empty()) {
		tii p = q.top(); q.pop();
		int v = get<0>(p);
		if (d[v]< get<1>(p))continue;
		for (int i = 0; i<g[v].size(); i++) {
			tii t = g[v][i];
			if (g[get<0>(t)].size() >= 2 && d[get<0>(t)]>d[v] + get<1>(t)) {
				d[get<0>(t)] = d[v] + get<1>(t);
				q.emplace(get<0>(t), d[get<0>(t)]);
				//cout << get<0>(t) << endl;
				//st = get<0>(t);
			}
		}
	}
	maxx = -1;
	rep(i, d.size()) {
		if (d[i] != INT_MAX&&d[i] > maxx) {
			maxx = d[i];
			st = i;
		}
	}
	//cout << d << endl;
	//cout << en << "   " << st << endl;
	//cout << d[st] << endl;

	cout << sum + sumscr * 2 - d[st] << endl;
}

int main(void) {
	int n;
	while (cin >> n,n) {
		solve(n);
		//cout << "////////////////" << endl;
	}
}




Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int maxn = 1e5+5;
int n,x[maxn],d[maxn],l[maxn],r[maxn],bt[2*maxn];
vector<int> ids;
vector<pair<int,int> > dd;
void up(int u,int  v)
{
	for(int i=u;i<2*maxn;i+=i&(-i))
	{
		bt[i]=max(bt[i],v);
	}
}
int query(int u)
{
	int re=0;
	for(int i=u;i>0;i-=i&(-i))
	{
		re=max(re,bt[i]);
	}
	return re;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>d[i];
		l[i]=max(0,x[i]-d[i]);
		r[i]=x[i]+d[i];
		ids.pb(l[i]);
		ids.pb(r[i]);
		dd.pb({x[i],i});
	}
	sort(ids.begin(),ids.end());
	ids.resize(unique(ids.begin(),ids.end())-ids.begin());
	sort(dd.begin(),dd.end());
	for(int i=0;i<n;i++)
	{
		r[i]=lower_bound(ids.begin(),ids.end(),r[i])-ids.begin()+1;
		l[i]=lower_bound(ids.begin(),ids.end(),l[i])-ids.begin()+1;
	}
	int re=0;
	for(int i=0;i<n;i++)
	{
		int j=dd[i].second;
		int t=1+query(l[j]);
		re=max(re,t);
		up(r[j],t);
	}
	cout<<re;
	return 0;
}

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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N;
vector<ll> A;

int main()
{
	scanf("%d",&N);
	A.assign(N,0ll);
	FOR(i,0,N){
		scanf("%lld",&A [i]);
	}
	ll sumAll = accumulate(A.begin(),A.end(),0ll);
	FOR(i,0,N) A [i] %= (N + 1);
	sort(A.begin(),A.end());
	
	for(ll i = min(sumAll,ll(N - 1) * N);i >= 0;i--){
		FOR(j,0,N + 1){
			ll sum = 0;
			bool ok = true;
			FOR(k,0,N){
				(++A [k]) %= (N + 1);
				ok &= A [k] < N;
				sum += A [k];
			}
			ok &= sum == i;
			if(ok){
				printf("%lld\n",sumAll - i);
				return 0;
			}
		}
	}

	return 0;
}


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

using namespace std;

int main()
{
  int n, count=0;
  scanf("%d", &n);

  int t[n];
  char s[n][101], x[101];

  for(int i=0; i<n;i++) {
    scanf("%s %d", s[i], &t[i]);
  }

  //printf("%s %d\n", s[0], t[0]);
  scanf("%s", x);

  bool sleep = false;
  for(int i=0; i<n; i++) {
    if(sleep == true)
      count += t[i];

    if(strcmp(x, s[i]) == 0)
      sleep = true;

  } 

  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
//https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_a
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
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;}
int main() {
    ll m1,d1; cin>>m1>>d1;
    ll m2,d2; cin>>m2>>d2;
    if(m1!=m2){
        cout<<1<<endl;
    } else{
        cout<<0<<endl;
    }   
    return 0;
}

Measured memory_bytes: 256
/*
ID: barish21
LANG: C++14
TASK: test
*/

/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();

const intt max1 = 11;
const intt max2 = 102;
const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;
const intt lg2 = 7;
const intt lg3 = 10;
const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;
const intt lg7 = 24;
const intt lg8 = 27;
const intt lg9 = 30;
const intt lg18 = 60;
const intt INF = 2LL * 1000000000;
/***************/

/***Additional Functions***/
intt powmod(intt a,intt b,intt mod){intt res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
intt gcd(intt a, intt b) { while(b) b ^= a ^= b ^= a %= b; return a;}
intt lcm(intt a,intt b){return a*b/gcd(a,b);}
intt is_prime(intt n){if(n==1)return 0;if(n==2)return 1;if(n%2==0)return 0;for(intt i=3;i<=sqrt(n);i+=2)if(n%i==0)return 0;return 1;}
intt is_integer(double n){if(floor(n)==ceil(n))return 1;return 0;}

intt sto_int(string s){stringstream ss(s);intt n;ss>>n;return n;}
string to_string(intt n){stringstream ss;ss<<n;string s=ss.str();return s;}
/**************************/

intt arr[777][777], x[77777];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    IO;
    intt n, m, k;
    cin >> n >> m >> k;
    for (intt i = 1; i <= k; i++)
        cin >> x[i];
    bool right = 1;
    intt cnt = 1, idx = 1, c = 0;
    for (intt i = 1; i <= n; i++) {
        if (c == x[idx] + 1)
            cnt ++, idx ++, c = 0;
        if (right == true) {
            for (intt j = 1; j <= m; j++) {
                arr[i][j] = cnt;
                c ++;
                if (c == x[idx])
                    cnt ++, idx ++, c = 0;
                right = 0;
            }
        } else {
            for (intt j = m; j >= 1; j--) {
                arr[i][j] = cnt;
                c ++;
                if (c == x[idx])
                    cnt ++, idx ++, c = 0;
                right = 1;
            }
        }
    }
    for (intt i = 1; i <= n; i++)
        for (intt j = 1; j <= m; j++)
            cout << arr[i][j] << (j == m ? "\n" : " ");
    return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
	ll n,m,d;
	double ans;
	scanf("%lld%lld%lld",&n,&m,&d);
	if(n == 1)
		printf("%.10lf\n",(double)(m-1));
	else
	{
		ans = (m-1)*1.0/n;
		if(d == 0)
			printf("%.10lf\n",ans);
		else
			printf("%.10lf\n",ans*(2.0/n)*(n-d));
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  int n;
  cin>>n;
  long long a[n];
  REP(i, n) cin>>a[i];
  long long money = 1000;
  long long stocks = 0;
  REP(i, n){
    if(i < n - 1){
      if(a[i] <= a[i + 1]){
        long long new_stocks = money / a[i];
        money -= new_stocks * a[i];
        stocks += new_stocks;
      }else{
        money += stocks * a[i];
        stocks = 0;
      }
    }else{
      money += stocks * a[i];
      stocks = 0;
    }
  }
  cout << money << endl;
  return 0;
}


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

using namespace std;

template<typename T>
long long modpow(const T n,const T p,const T mod);
template<typename T>
long long modinv(const T n,const T mod);
template<typename T>
bool chmax(T &a,const T &b);
template<typename T>
bool chmin(T &a,const T &b);

long long inf=1000000007;

int main(){
	long long n,x,m;
	cin>>n>>x>>m;
	long long ans=0;
	long long roop=0;
	long long inroop=0;
	long long cnt=0;
	vector<long long> num;
	map<long long,long long> zisyo;

	for(long long i=0;i<n;i++){
		zisyo[x]++;
		if(zisyo[x]==2){
			roop=1;
		}
		if(zisyo[x]==3){
			n-=i;
			ans+=inroop*(n/cnt)+inroop;
			for(long long j=0;j<n%cnt;j++){
				ans+=num.at(j);
			}
			break;
		}

		if(roop==0){
			ans+=x;
		}else{
			inroop+=x;
			num.push_back(x);
			cnt++;
		}
		x*=x;
		x%=m;
	}

	cout<<ans<<endl;

	return 0;
}

template<typename T>
long long modpow(const T n,const T p,const T mod){
	if(p==0) return 1;
	if(p%2==0){
		long long a=modpow(n,p/2,mod);
		return a*a%mod;
	}
	if(p%2==1) return (modpow(n,p-1,mod)*n)%mod;
	cerr<<"ERROR"<<endl;
	return 1;
}

template<typename T>
long long modinv(const T n,const T mod){
	return modpow(n,mod-2,mod);
}

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

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


Measured memory_bytes: 7044
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_end().parse().ok().unwrap()
}

fn main() {
    let mut a: String = read();
    let v: Vec<char> = a.chars().collect();
    if v[v.len() - 1] == 's' {
        a.push('e');
        a.push('s');
    } else {
        a.push('s');
    }
    println!("{}", a);
}


Measured memory_bytes: 2136
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
 
int main() {
  string s;
  string t;
  
  cin >> s;
  
  t = "x";
  
  rep(i, s.length() - 1) t += "x"; 
  
  cout << t << endl;
}

Measured memory_bytes: 256