akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#define MAX 100005
using namespace std;
vector<int> v1[MAX];
int u, v;
int dist[MAX];
int ans = 0;
void dfs1(int x = 0, int y = u, int z = 0){
    dist[y] = z;
    for (int i = 0; i < v1[y].size(); i++)
    {
        if (x == v1[y][i])
            continue;
        dfs1(y, v1[y][i], z+1);
    }
}
void dfs2(int x = 0, int y = v, int z = 0){
    if (dist[y] < z)
    {
        ans = max(ans, z-1);
    }
    
    dist[y] = z;
    for (int i = 0; i < v1[y].size(); i++)
    {
        if (x == v1[y][i])
            continue;
        dfs2(y, v1[y][i], z+1);
    }
}
int main(){
    int n;
    cin >> n >> u >> v;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        v1[a].emplace_back(b);
        v1[b].emplace_back(a);
    }
    dfs1();
    dfs2();
    cout << ans << endl;
}

Measured memory_bytes: 11264
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int H,W;
vec dy(4),dx(4);
vector<vector<char>> S(30,vector<char>(30));

int rev;
void BFS(int sy,int sx){
    mat dist(30,vec(30,-1));
    dist[sy][sx]=0;
    queue<pair<int,int>> que;
    pair<int,int> p={sy,sx};
    que.push(p);
    while(!que.empty()){
        pair<int,int> s=que.front();que.pop();
        for(int i=0;i<4;i++){
            int ty=s.first+dy[i];
            int tx=s.second+dx[i];
            if(S[ty][tx]=='#'){continue;}
            if(ty<=0 || tx<=0 || ty>H || tx>W){continue;}
            if(dist[ty][tx]!=-1){continue;}
            dist[ty][tx]=dist[s.first][s.second]+1;
            rev=max(rev,dist[ty][tx]);
            pair<int,int> q={ty,tx};
            que.push(q);
        }
    }
}

int main(){
    cin>>H>>W;
    dy[0]=0;dx[0]=1;
    dy[1]=1;dx[1]=0;
    dy[2]=0;dx[2]=-1;
    dy[3]=-1;dx[3]=0;
    for(int h=1;h<=H;h++){
        for(int w=1;w<=W;w++){
            cin>>S[h][w];
        }
    }
    int ans=0;
    for(int h=1;h<=H;h++){
        for(int w=1;w<=W;w++){
            if(S[h][w]=='.'){
                rev=0;
                BFS(h,w);
                ans=max(ans,rev);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
///////////////////////////////////////////////////////////
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
///////////////////////////////////////////////////////////
#define ll long long
#define ull unsigned lon long
///////////////////////////////////////////////////////////
int absolute(int n); double absolute(double n);
void input(vector<int>& vec);
void print(vector<int> vec); void print(vector<double> vec);
int sum(vector<int> vec); double sum(vector<double> vec);
void upsort(vector<int>& vec);
void downsort(vector<int>& vec);
int maxvec(vector<int> vec);
int minvec(vector<int> vec);
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
int main()
{
    int a, b, k;
    cin>>a>>b>>k;
    int count=0;
    for (int i=min(a,b);i>0;--i){
        if(a%i==0&&b%i==0){
            ++count;
        }
        if(count==k){
            cout<<i<<endl;
            return 0;
        }
    }
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
int absolute(int n)
{
    if (n < 0) {
        return (-n);
    }
    return n;
}

double absolute(double n)
{
    if (n < 0) {
        return (-n);
    }
    return n;
}

void input(vector<int>& vec)
{
    for (size_t i = 0; i < vec.size(); ++i) {
        cin >> vec.at(i);
    }
}

void print(vector<int> vec)
{
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec.at(i) << " ";
    }
    cout << endl;
}

void print(vector<double> vec)
{
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec.at(i) << " ";
    }
    cout << endl;
}

int sum(vector<int> vec)
{
    int s = accumulate(vec.begin(), vec.end(), 0);
    return s;
}

double sum(vector<double> vec)
{
    double s = accumulate(vec.begin(), vec.end(), 0.0);
    return s;
}

void upsort(vector<int>& vec)
{
    sort(vec.begin(), vec.end());
}

void downsort(vector<int>& vec)
{
    sort(vec.begin(), vec.end(), greater<int>());
}

int maxvec(vector<int> vec)
{
    int m = vec.at(0);
    for (size_t i = 0; i < vec.size(); ++i) {
        m = max(m, vec.at(i));
    }
    return m;
}

int minvec(vector<int> vec)
{
    int m = vec.at(0);
    for (size_t i = 0; i < vec.size(); ++i) {
        m = min(m, vec.at(i));
    }
    return m;
}
///////////////////////////////////////////////////////////

Measured memory_bytes: 256
import copy
import bisect

N = int(input())
L = sorted(list(map(int, input().split())))

triangles = 0

for i in range(N - 2):
    P = L[i]
    for j in range(i + 1, N - 1):
        Q = L[j]
        if P + Q <= L[j + 1]:
            continue
        maxR = P + Q - 1
        triangles += bisect.bisect_right(L, maxR) - (j + 1)

print(triangles)


Measured memory_bytes: 44140
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
#define pb(X) push_back(X)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
using namespace std;

int n, a, b, c, d, q, ans;

int gcd(int a,int b) {
	while(a && b) {
		if (a > b) {
			a %= b;
		} else {
			b %= a;
		}
	}
	return max(a, b);
}
int main() {
	INIT
	cin >> n;
	vector<int> a(n + 1);
	vector<int> g1(n + 2), g2(n + 2);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		g1[i] = gcd(g1[i - 1], a[i]);
	}
	for (int i = n; i > 0; --i) {
		g2[i] = gcd(g2[i + 1], a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, gcd(g1[i - 1], g2[i + 1]));
	}
	cout << ans;
	return 0;
}

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

int main() {
	int n,t;
	cin >> n;
	vector<int> Asort(n);
	vector<int> A(n);
	
	for (int i = 0; i < n; i++)
	{
		cin >> t;

		Asort[i] = t;
		A[i] = t;
		
	}

	sort(Asort.begin(),Asort.end(),std::greater<int>());

	int max = Asort[0];
	int secondMax = Asort[1];


	if(Asort[0] == Asort[1]){
		for (int i = 0; i < n; i++)
		{

			cout << max << endl;


		}


	}else{
		for (int i = 0; i < n; i++)
		{
			if(A[i] == max){
				cout << secondMax << endl;

			}else{
				cout << max << endl;

			}
		}

	}



}


Measured memory_bytes: 3200
S = input()
T = input()
result = "UNRESTORABLE"
b = True
for i in range(len(S) - len(T) + 1):
    for j in range(len(T)):
        if S[i + j] != T[j] and S[i + j] != "?":
            break
        if j == len(T) - 1:
            s = (S[:i] + T + S[i + len(T):]).replace("?", "a")
            if b or s < result:
                result = s
                b = False
print(result)


Measured memory_bytes: 3060
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int  a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e - a > k){
        cout << ":(";
    }
    else
    {
        cout << "Yay!";
    }
    
    
    cout << endl;
}


Measured memory_bytes: 256
def solve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    ans = [1 for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if h[a] <= h[b]:
            ans[a] = 0
        if h[b] <= h[a]:
            ans[b] = 0
    print(sum(ans))


if __name__ == '__main__':
    solve()


Measured memory_bytes: 20056
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

int main(){
	string w1;
	string w2;
	string w3;
	while(cin >> w1){
		cin >> w2;
		cin >> w3;
		char a = w1[0];
		char b = w2[0];
		char c = w3[0];
    a += 'A' - 'a';
		b += 'A' - 'a';
		c += 'A' - 'a';
		cout << a << b << c << endl;
	}

	return 0;
}


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

int main(){
    int n,a,b,ab;
    string s;
    cin >> n >> a >> b >> s;
    rep(i,n){
        ab = a+b;
        //cout << ab << endl;
        if (s[i] == 'a' && ab > 0){
            cout << "Yes" << endl;
            if(a > 0)a--;
            else b--;
        }
        else if(s[i] == 'b' && ab >0 && b > 0){
            cout << "Yes" << endl;
            b--;
        }
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 896
#include<iostream>

int a[100005];
int num[100005];
const int mod = 1000000007;

int main() {
    int n;
    std:: cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        num[a[i]]++;
    }
    for (int i = 1; i < n; i++) {
        if(i % 2 == 0) {
            if(num[n - i] != 0) {
                std::cout << 0 << std::endl;
                return 0;
            }
        } else {
            if(num[n - i] != 2) {
                std::cout << 0 << std::endl;
                return 0;
            }
        }
    }
    if(n % 2 == 0 && num[0] != 0) {
        std::cout << 0 << std::endl;
        return 0;
    } else if(n % 2 != 0 && num[0] != 1) {
        std::cout << 0 << std::endl;
        return 0;
    }
    n /= 2;
    long long ans = 1;
    long long two = 2;
    while(n) {
        if(n & 1)
            ans *= two;
        ans %= mod;
        two *= two;
        two %= mod;
        n >>= 1;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner scanner = new Scanner(System.in);

		//入力表示
		int N = scanner.nextInt();
      
		System.out.println(N*N*N);

	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>
#include <set>

static const int INF = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

int main() {
    int n;
    multiset<int> v;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        v.insert(k);
    }
    int ans = 0;
    for (int i = 0; i < 100000; ++i) {
        ans = max(int(v.count(i-1) + v.count(i) + v.count(i+1)), ans);
    }
    cout << ans << "\n";
    return 0;
}


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

int main() {
    int n, x;
    vector<int> m;
    int num = 0;
    int tmp;

    cin >> n >> x;

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        m.push_back(tmp);
        num += m[i];
    }
    int minx = m[0];

    for(int i = 0; i < (int)m.size(); ++i) {
        if( m[i] < minx )
            minx = m[i];
    }

    x -= num;
    while (x >= minx) {
        x -= minx;
        n++;
    }

    cout << n << endl;
}


Measured memory_bytes: 256
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

R = 1000000007

n,m = inm()
b = [0] * (n+2)
b[0] = 1
bad = [False] * (n+2)
for i in range(m):
    bad[inn()] = True

for i in range(1,n+1):
    if bad[i]:
        if bad[i-1]:
            print(0)
            exit()
        else:
            continue
    else:
        b[i] = (b[i-1] + b[i-2]) % R

print(b[n])


Measured memory_bytes: 46568
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=300005;
int p[N];
void GG(){
	puts("No"); exit(0);
}
#define lowbit(i) i&-i
int c[N];
int ask(int pos){
	int ans=0;
	for(int i=pos;i;i-=lowbit(i))ans+=c[i];
	return ans;
}
void change(int pos){
	for(int i=pos;i<N;i+=lowbit(i))c[i]++;
}
void solve(vector<int> v){
	For(i,0,v.size())c[i]=0;
	For(i,0,v.size()-1){
		int t=ask(v[i]);
		t=v[i]-t-1;
		if(t&&i+t>=v[i])GG();
		change(v[i]);
	}
}
int main(){
	int n=read();
	For(i,1,n)p[i]=read();
	For(i,1,n){
		if(p[i]==i)continue;
		else{
			int mn=p[i],mx=p[i];
			int dq=i;
			while(mn!=i||dq!=mx){
				if(dq+2>n)GG(); if(p[dq+1]!=dq+1)GG();
				dq+=2; mx=max(mx,p[dq]); mn=min(mn,p[dq]);
			}
			vector<int> v;
			for(int j=i;j<=dq;j+=2)v.pb((p[j]-mn)/2+1);
			solve(v);
			i=dq;
		}
		//cout<<i<<" fjz "<<" "<<p[i]<<" "<<endl;
	}
	puts("Yes");
}
/*
性质一：不能往回走
*/

Measured memory_bytes: 3316
n = gets.chomp.to_i
s = gets.chomp

b_w = [[0, s.count('.')]]
n.times do |i|
  if s[i] == '.'
    b_w << [b_w[-1][0], b_w[-1][1] - 1]
  else
    b_w << [b_w[-1][0] + 1, b_w[-1][1]]
  end
end
puts b_w.map{|b,w| b+w}.min

Measured memory_bytes: 18172
/**
 *     author: nayakashutosh9
 *     college: National Institute of Technology, Rourkela
 *	   "Winners Never Quit and Quitters Never Win".
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
#define mod 1000000007
#define inf 1e18
const int N = 300005;

/*******************************************************************/



int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	// int t = 1, z = 1;
	// cin >> t;
	// cin.ignore();
	// while (t--) {

	// }
	string s,t;
	cin>>s>>t;
	int ans=0;
	for(int i=0;i<s.length();i++)
		if(s[i]!=t[i]) ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3816
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int n,l[100];
	int i,j,k,c=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&l[i]);
	}
	sort(l,l+n);
	for(i=0;i<n-2;i++){
		for(j=i+1;j<n-1;j++){
			for(k=j+1;k<n;k++){
				if(l[k]<l[i]+l[j]){
					if(l[k]!=l[i]&&l[k]!=l[j]&&l[i]!=l[j]){
					c++;
					}
				}
			}
		}
	}
	printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 1716
"""ABC073D joisino's travel
"""
from itertools import permutations
N,M,R=map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))
INF = float("inf")
D = [[INF]*(N) for _ in range(N)]
for _ in range(M):
    a,b,c=map(int, input().split())
    D[a-1][b-1]=c
    D[b-1][a-1]=c
    
def warshall_floyd(adj_mat: list):
    """
    ワーシャルフロイド
    隣接行列を受け取る(隣接していないノードはINF、自身へのコストは0)
    全点の間の最短距離をあらわす行列を返す(V * V)
    O(|V|**3)
    ネスト深くならないバージョン
    """
    V = len(adj_mat)
    for k in range(V): # 経由点
        for i in range(V): # 出発点
            for j in range(V): # 終点
                adj_mat[i][j] = min(
                    adj_mat[i][j],
                    adj_mat[i][k] + adj_mat[k][j]
                )
    return adj_mat
D = warshall_floyd(D)
ans = INF
for tpl in permutations(r, len(r)):
    tmp = 0
    for i in range(len(tpl)-1):
        tmp += D[tpl[i]][tpl[i+1]]
    ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 75628
#include <stdio.h>

int Euclid(int a,int b){
    if(a<b){
   int tmp = a;
    a = b;
    b = tmp;

    }
    int   r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
    return b;
}

int main(void){
    int N,K;
    scanf("%d %d",&N,&K);
    int max=0;
    int euc;
    scanf("%d",&euc);
    max=euc;
    int kari;
    for(int i=1;i<N;i++){
        scanf("%d",&kari);
        euc=Euclid(euc,kari);
        if(max<kari)max=kari;
    }
    if(max>=K&&K%euc==0)printf("POSSIBLE");
    else printf("IMPOSSIBLE");
    return 0;
}


Measured memory_bytes: 128
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>
#include <map>

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		LL n = -1, ans = 0;
		cin >> n;
		if (n <= 0) return 0;
		string s;
		cin >> s;
		char charToIndex[256];
		const char chars[3] = { 'R', 'G', 'B' };
		vector<LL> counts[3];
		for (int i = 0; i < 3; ++i) {
			charToIndex[chars[i]] = i;
			counts[i].resize(n + 1);
			for (int j = n - 1; j >= 0; --j) {
				counts[i][j] = counts[i][j + 1] += (s[j] == chars[i]);
			}
		};
		for (LL i = 0; i < n - 2; ++i) {
			for (LL j = i + 1; j < n - 1; ++j) {
				if (s[i] != s[j]) {
					int k = 3 ^ charToIndex[s[i]] ^ charToIndex[s[j]];
					ans += counts[k][j + 1];
					if (2 * j - i < n && s[2 * j - i] == chars[k]) {
						--ans;
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3668
n = int(input())
lista = list(map(int, input().split()))
limitNumber = 10**18
ans = 1

if 0 in lista:
    ans = 0
else:
    lista.sort(reverse=True)
    for i in range(n):
        ans *= lista[i]
        if(ans > limitNumber):
            ans = -1
            break

print(ans)


Measured memory_bytes: 21656
// AOJ ALDS1_5_C Koch Curve
// 2018.4.30 bal4u

#include <stdio.h>
#include <math.h>

#define PI 3.1415926535897932384626433832795

double d; int a;
double vcos[6], vsin[6];
double x, y;

void koch_curve(int k)
{
	if (k == 0) {
		x += d*vcos[a % 6], y += d*vsin[a%6];
		printf("%.8lf %.8lf\n", x, y);
	} else {
		d /= 3;
		koch_curve(k-1), a++, koch_curve(k-1);
		a += 4;
		koch_curve(k-1), a++, koch_curve(k-1);
		d *= 3;
	}
}

int main()
{
	int n, i;
	
	for (i = 0; i < 6; i++) vcos[i] = cos(i*PI/3), vsin[i] = sin(i*PI/3);

	scanf("%d", &n);

	d = 100;		// (0,0) - (100,0);

	a = 0, x = 0, y = 0; puts("0.00000000 0.00000000");
	koch_curve(n);
	return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define MAXN 200000
using namespace std;

int arr[MAXN];

int main() {
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i=0; i<n; i++) {
		if (i == 0 || arr[i] > arr[i-1]) arr[i]--;
	}
	for (int i=1; i<n; i++) {
		if (arr[i] < arr[i-1]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}



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

using namespace std;

const int mod = 998244353;

int add() { return 0; }
template<typename... M> int add(int a, M... b) {
  int x = add(b...);
  return a + x - mod * (a + x >= mod);
}

int mul() { return 1; }
template<typename... M> int mul(int a, M... b) {
  return int(1ll * a * mul(b...) % mod);
}

int pwr(int a, long long x) {
  return (x ? mul(pwr(mul(a, a), x >> 1), (x & 1 ? a : 1)) : 1);
}

int dvd(int a, int b) {
  return mul(a, pwr(b, mod - 2));
}

int sub(int a, int b) {
  return a - b + mod * (a < b);
}

void inc(int& a, int b) {
  a = add(a, b);
}

void dec(int& a, int b) {
  a = sub(a, b);
}

vector<int> fact = {1}, invf = {1};
int C(int n, int k) {
  if (n < k or 0 > k) return 0;
  while (fact.size() <= n) {
    fact.push_back(mul(fact.back(), fact.size()));
    invf.push_back(dvd(1, fact.back()));
  }
  return mul(fact[n], invf[k], invf[n - k]);
}

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

  int n, k;
  cin >> n >> k;
  vector<int> l(k), r(k);
  for (int i = 0; i < k; ++i) {
    cin >> l[i] >> r[i];
  }
  vector<int> dp(n + 1), a(n + 1);
  dp[0] = 1;
  for (int i = 0; i < n; ++i) {
    inc(a[i + 1], a[i]);
    inc(dp[i], a[i]);
    for (int j = 0; j < k; ++j) {
      int L = min(n, i + l[j]), R = min(n, i + r[j] + 1);
      inc(a[L], dp[i]);
      dec(a[R], dp[i]);
    }
  }
  cout << dp[n - 1];

  return 0;
}


Measured memory_bytes: 4776
//
// author  : Abhishek
//
#include <bits/stdc++.h>
#include<chrono>

#define ll long long
#define db double
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)

using namespace std;
using namespace chrono;

const ll MOD = 1000000007;
const ll N = 300005;  // array size
const ll inf = 10000000000000000;
const db PI = 3.14159265358979323846264338327950288419716939937510;

void print(vector<ll> v) {
    ll i;
    fo(i, v.size())cout << v[i] << " ";
    cout << "\n";
}

void print(vector<pair<ll, ll> > v) {
    ll i;
    fo(i, v.size()) {
        cout << v[i].first << " " << v[i].second << "\n";
    }
}

vector<ll> read(ll n) {
    ll i;
    vector<ll> arr(n, 0);
    fo(i, n)cin >> arr[i];
    return arr;
}

vector<ll> read(ll n, ll k) {
    ll i;
    vector<ll> arr(n + k, 0);
    Fo(i, k, n + k)cin >> arr[i];
    return arr;
}

bool isEven(ll n) {
    return n % 2 == 0;
}

bool isOdd(ll n) {
    return n % 2 != 0;
}

ll n, m;

vector<ll> adj[N];
vector<ll> vis(N + 1);
vector<ll> dp(N + 1, 0);

void dfs(ll cur) {
    vis[cur] = 1;
    ll mx = -1;
    for (auto next: adj[cur]) {
        if (!vis[next]) {
            dfs(next);
            mx = max(mx, dp[next]);
        } else {
            mx = max(mx, dp[next]);
        }
    }

    dp[cur] = mx + 1;
}

void solve() {
    ll t = 1;
//    cin >> (t);
    while (t--) {

        ll i, j, k, p, q, x, y, a, b, l, r;
        cin >> n >> m;
        fo(i, m) {
            cin >> x >> y;
            adj[x].push_back(y);
        }

        Fo(i, 1, n + 1) {
            if (!vis[i])
                dfs(i);
        }

        ll ans = -1;
        Fo(i, 1, n + 1) {
            ans = max(ans, dp[i]);
        }
        cout << ans;

    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    auto start = high_resolution_clock::now();

    solve();

    ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
#ifndef ONLINE_JUDGE
    cerr << "Time: " << duration.count() / 1000.0 << endl;
#endif


    return 0;
}




Measured memory_bytes: 21308
#define _USE_MATH_DEFINES

#include <iostream>	//cin, cout
#include <vector>	//vector
#include <algorithm> //sort,min,max,count
#include <string>	//string,getline
#include <ios>		//fixed
#include <iomanip>	//setprecision
#include <utility> //swap
#include <cstdlib>	//abs(int)
#include <cmath>	//sqrt
#include <sstream>	//stringstream,getline
#include <cmath>	//ceil,M_PI
#include <numeric>	//gcd
#include <deque>	//deque

using namespace std;

int main() {

	string S, T;
	cin >> S >> T;

	int ans = 0;
	for (int i = 0; i < 3; i++) {
		if (S[i] == T[i]) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;

}

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

int main() {

	for (;;) {
		int n, x;
		cin >> n >> x;
		if (n == 0 && x == 0) {
			break;
		}

		int count = 0;
		for (int a = 1; a <= n; a++) {
			for (int b = a + 1; b <= n; b++) {
				int c = x - a - b;
				if (b < c && c <= n) {
					count++;
				}
			}
		}
		cout << count << endl;
	}

	return 0;
}



Measured memory_bytes: 3092
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

map<long long, int> factorization(long long N) {
	map<long long, int> re;
	while (true) {
		if (N % 2 == 0) {
			N /= 2;
			re[2]++;
			if (N == 1) break;
		}
	}
	if (N > 1) re[N]++;
	for (int loop = 3; (long long)loop * (long long)loop <= N; loop += 2) {
		if (N % loop == 0) {
			N /= loop;
			re[loop]++;
			loop -= 2;
			if (N == 1) break;
		}
	}
	if (N > 1) re[N]++;
	return re;
}

struct Memo {
	long long fact = 0;
	long long fact_inv = 0;
	long long inv = 0;
};
class Combination1 {
private:
	int m_module = 1000000007;
	vector<struct Memo> memo;
public:
	int calculate(int, int);
	Combination1(int, int);
};
int Combination1::calculate(int n, int k) {
	return ((memo[n].fact * memo[k].fact_inv) % m_module * memo[n - k].fact_inv) % m_module;
}
Combination1::Combination1(int memo_max, int module = 1000000007) {
	m_module = module;
	memo.push_back({ 1,1,0 });
	memo.push_back({ 1,1,1 });
	for (int loop = 2; loop <= memo_max; loop++) {
		struct Memo temp;
		temp.fact = (memo[loop - 1].fact * loop) % m_module;
		temp.inv = m_module - (memo[m_module % loop].inv * int(m_module / loop)) % m_module;
		temp.fact_inv = (memo[loop - 1].fact_inv * temp.inv) % m_module;
		memo.push_back(temp);
	}
}

class Combination2 {
private:
	int size = 0;
	bool add(int);
public:
	vector<int> sequence;
	bool next_combination(void);
	Combination2(int, int);
};
bool Combination2::add(int index) {
	if (index == (int)sequence.size() - 1 && sequence[index] == size - 1
		|| index < (int)sequence.size() - 1 && sequence[index] == sequence[index + 1] - 1) {
		if (index == 0) {
			return false;
		}
		else {
			bool re = add(index - 1);
			sequence[index] = sequence[index - 1] + 1;
			return re;
		}
	}
	else {
		sequence[index]++;
		return true;
	}
}
bool Combination2::next_combination(void) {
	return (sequence.size() == 0) ? false : add(sequence.size() - 1);
}
Combination2::Combination2(int n, int r) {
	size = n;
	for (int loop = 0; loop < r; loop++) sequence.push_back(loop);
	return;
}

void A_Circle(void) {

	int r; cin >> r;
	cout << r * r << flush;
	return;
}

void B_Echo(void) {

	int N; string S; cin >> N >> S;

	cout << ((N % 2 == 0 && S.substr(0, N / 2) == S.substr(N / 2, N / 2)) ? "Yes" : "No") << flush;
	return;
}

int main(void) {
	
	//A_Circle();
	B_Echo();
	return 0;
}


Measured memory_bytes: 256
// I'm a f*cking looser
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fasino ios_base::sync_with_stdio(false); cin.tie(0);
#define asc(A) sort(A.begin(),A.end())
#define dsc(A) sort(A.begin(),A.end(),greater<ll>())
#define input(A,N) for(ll i=0;i<N;i++) cin>>A[i];
int main()
{
    fasino
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin); 
    #endif
    ll n,k,count =0;
    cin>>n>>k;
    bool A[n];
    memset(A,false,sizeof A);
    for(ll i=0;i<k;i++){
        ll tm ,tmp;
        cin>>tm;
        for(ll j=0;j<tm;j++){
            cin>>tmp;
            if(!A[tmp-1])
                A[tmp-1]=true;
        }
    }
    for(ll i=0;i<n;i++) 
        if(A[i]==false)
            count++;
    cout<<count;
    return 0;
}

Measured memory_bytes: 3600
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

/*-----<Defines>-----*/
#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)size(x))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)-1)/(x)+1)
#define     flush           fflush(stdout)

using ull=unsigned long long;
using ll=long long;
using ld=long double;
/*-----</Defines>-----*/

/*-----<Debugging Stuff>-----*/
string to_string(char s)
{   string res="'''";res[1]=s;return res; }

string to_string(string s)
{   return '"'+s+'"'; }

string to_string(const char* s)
{   return to_string((string)s); }

string to_string(bool b)
{   return (b?"true":"false"); }

template<typename A, typename B>
string to_string(pair<A, B> p)
{   return "("+to_string(p.F)+", "+to_string(p.S)+")"; }

template<typename A>
string to_string(A v)
{
    bool first=1; string res="{";
    for(const auto &x:v)
    {
        if(!first)  res+=", ";
        first=0;
        res+=to_string(x);
    }
    res+="}";
    return res;
}

void debug() { cout<<"\n"; }
template<typename Head, typename... Tail>
void debug(Head H, Tail... T)
{
    cout<<" "<<to_string(H);
    debug(T...);
}

#define show(...) cout << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
/*-----</Debugging Stuff>-----*/

/*-----<Mod Operations>-----*/
const int M=1e9+7;
inline int add(int a,int b,int p=M){ a=a+b; if(a>=p) a-=p; return a; }
inline int sub(int a,int b,int p=M){ a=a-b; if(a<0) a+=p; return a; }
inline int mul(int a,int b,int p=M){ a=(a*1ll*b)%p; return a; }
/*-----</Mod Operations>-----*/

/*-----<Constants>-----*/
const ld pi=acos(-1),eps=1e-9;
const ll inf=1e18;
const int N=1e5+10;
/*-----</Constants>-----*/

int a[N];

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

    vi v(n);
    for(auto &c:v)
        cin>>c;

    mem(a,0);
    for(auto c:v)
        ++a[c];

    int sum=accumulate(all(v),0ll);

    int q;
    cin>>q;

    for(;q;--q)
    {
        int x,y;
        cin>>x>>y;

        sum-=x*a[x];
        a[y]+=a[x];
        sum+=y*a[x];
        a[x]=0;

        cout<<sum<<"\n";
    }
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 4740
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

defeated = 0

for i in range(N):
    if B[i] >= A[i]:
        B[i] -= A[i]
        defeated += A[i]
        
        if B[i] <= A[i+1]:
            A[i+1] -= B[i]
            defeated += B[i]
        else:
            B[i] -= A[i+1]
            defeated += A[i+1]
            A[i+1] = 0
    else:
        A[i] -= B[i]
        defeated += B[i]
        B[i] = 0
        
print(defeated)

Measured memory_bytes: 18476
#include <cstdio>
using namespace std;
int n;
int a[200005];
long long ans=0;
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;++i)scanf("%d",a+i);
	for(int i=1;i<n;++i){
		if(a[i-1]>a[i]){
			ans+=a[i-1]-a[i];
			a[i]=a[i-1];
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2508
#include<bits/stdc++.h>
using namespace std;
int dp[810][810];
int main(void)
{
	int d,n,i,j,k,sel[810],a[810],b[810],c[810],data,mx=-1;
	cin>>d>>n;
	for(i=1;i<=d;i++) cin>>sel[i];
	for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
	for(i=1;i<=d;i++) for(j=1;j<n;j++) dp[i][j]=0;
	for(i=1;i<=d;i++) {
		for(j=1;j<=n;j++) {
			if(a[j]<=sel[i]&&sel[i]<=b[j]) {
				for(k=1;k<=n;k++) {
					if(a[k]<=sel[i+1]&&sel[i+1]<=b[k]) {
						data=abs(c[j]-c[k]);
					}
					dp[i+1][k]=max(dp[i][j]+data,dp[i+1][k]) ;
				}
			}
		}
	}
	for(i=1;i<=n;i++) mx=max(mx,dp[d][i]);
	cout<<mx<<endl;
}

Measured memory_bytes: 3736
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;$n:expr) => {
        (0..$n).map(|_| scan!()).collect::<Vec<_>>()
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let n = scan!(i64);
    let a = scan!(i64);

    println!("{}", n * n - a)
}


Measured memory_bytes: 4352
/// Solution to https://atcoder.jp/contests/abc144/tasks/abc144_b
/* ------
    Atcoder.jp @betuyash
    -------
    */
#include<bits/stdc++.h>
using namespace std;
void Solve_Case()
{
    double n;
    cin >> n;
    for(double i=1;i<=9;i++)
    {
        double j = n/i;
        if(  ceil(j) == floor(j) &&  j <= 9)
        {
            cout << "Yes";
            return ;
        }
    }
    cout << "No";
}
int main()
{
    int TestCases = 1;
    /// cin >> TestCases;
    while(TestCases--)
    {
        Solve_Case();
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

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

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

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);


  lint n,k;
  cin>>n>>k;
  lint max=0;
  lint v=1;
  lint count=0;
  while(max<n){
    max+=v*(k-1);
    count++;
    v*=k;
  }
  cout<<count<<endl;




  return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define make_unique(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define Sort(vec) sort(vec.begin(),vec.end())
#define RSort(vec) sort(vec.rbegin(),vec.rend())
#define endl "\n"
#define tr1(i) cout<<i<<endl;
#define tr2(i,j) cout<<i<<" "<<j<<endl;
#define tr3(i,j,k) cout<<i<<" "<<j<<" "<<k<<endl;
#define vvi vector<vector<int> > 
#define vvl vector<vector<ll> >
#define all(st) st.begin(),st.end()
#define vpl vector<pair<ll,ll> >
#define vpi vector<pair<int,int> >
#define pi pair<int,int>
#define pl pair<ll,ll>
#define al vector<list<int> >
#define vs vector<string>
#define vb vector<bool>
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define repit(st) for(auto it=st.begin();it!=st.end();it++)
#define ull unsigned long long int
#define eb emplace_back
#define pb push_back
#define ll long long int
#define minf -(1e18)
#define inf 1e18
#define f first
#define se second
#define mod 1000000007
#define mx 200000
using namespace std;
ll mi(ll n,ll m){ll pw=n%m;ll ex=m-2;ll ans=1;while(ex){if(ex&1) ans = ans*pw%m;pw = pw*pw%m;ex>>=1;}return ans%mod;}
ll pw(ll a,ll n){ll pw=a%mod;ll ex=n;ll ans=1;while(ex){if(ex&1) ans = ans*pw%mod;pw = pw*pw%mod;ex>>=1;}return ans%mod;}
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }
void show(ll x){cout<<x<<" ";}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll Abs(ll x){return x>0?x:(-x);}
ll Ceil(ll a,ll b){return a/b+(a%b!=0);}
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define mkp make_pair
//#define d double
void solve(){
	string str;
	cin>>str;
	ll d;cin>>d;
	ll n=str.length();
	vector<vector<ll>> dp(d,vector<ll>(2));
	dp[0][0]=1;
	for(int i=0;i<n;i++){
		vvl tdp(d,vl(2));
		int v=str[i]-'0';
		for(int rk=0;rk<d;rk++){
			for(bool is_smaller:{true,false}){
				for(int k=0;k<=9;k++){
					if(k>v && !is_smaller) break;
					tdp[(rk+k)%d][is_smaller||k<v]=(tdp[(rk+k)%d][is_smaller||k<v]+dp[rk][is_smaller])%mod;
				}
			}
		}
		dp=tdp;
	}
	cout<<(dp[0][0]+dp[0][1]-1+mod)%mod;
 
}
int32_t main(){
int t=1;
//cin>>t;
while(t--){
	solve();
}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using VI = vector<int>;
using VVI = vector<VI>;

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int n, m, r; cin >> n >> m >> r;
  VI t(r); for (int i = 0; i < r; i++) { cin >> t[i]; t[i]--; }
  sort(t.begin(), t.end());
  VVI d(n, VI(n, 1e9));
  for (int i = 0; i < m; i++) {
    int a, b, c; cin >> a >> b >> c;
    a--; b--;
    d[a][b] = d[b][a] = c;
  }
  for (int i = 0; i < n; i++) {
    d[i][i] = 0;
  }
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  int res = 2e9;
  do {
    int tmp = 0;
    for (int i = 0; i < t.size() - 1; i++) {
      tmp += d[t[i]][t[i + 1]];
    }
    res = min(res, tmp);
  } while (next_permutation(t.begin(), t.end()));
  cout << res << '\n';
  return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin >> a[i];
  int ma=0,id=0;
  for(int i=0;i<n;i++){
    if(abs(a[i])>=ma){
      ma=abs(a[i]),id=i;
    }
  }
  if(a[id]==0){
    cout << 0 << endl;
    return 0;
  }
  if(a[id]>0){
    if(id>0){
      cout << 2*n << endl;
      cout << id+1 SP 1 << endl;
      cout << id+1 SP 1 << endl;
      for(int i=1;i<n;i++){
        cout << i SP i+1 << endl;
        cout << i SP i+1 << endl;
      }
    }else{
      cout << 2*n-2 << endl;
      for(int i=1;i<n;i++){
        cout << i SP i+1 << endl;
        cout << i SP i+1 << endl;
      }
    }
  }else{
    if(id<n-1){
      cout << 2*n << endl;
      cout << id+1 SP n << endl;
      cout << id+1 SP n << endl;
      for(int i=n-1;i>=1;i--){
        cout << i+1 SP i << endl;
        cout << i+1 SP i << endl;
      }
    }else{
      cout << 2*n-2 << endl;
      for(int i=n-1;i>=1;i--){
        cout << i+1 SP i << endl;
        cout << i+1 SP i << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int H, W;
int sy, sx, gy, gx;
string S[1000];

int cost[1000][1000];
priority_queue<pair<int, pair<int, int>>> pq;

signed main(){
    cin >> H >> W;
    cin >> sy >> sx >> gy >> gx;
    sy--; sx--; gy--; gx--;
    rep(i, H) cin >> S[i];

    rep(i, H){
        rep(j, W){
            cost[i][j] = 2e9;
        }
    }
    cost[sy][sx] = 0;
    pq.push({ 0,{sy,sx} });
    while(!pq.empty()){
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        pq.pop();
        for(int i=-2; i<=2; i++){
            for(int j=-2; j<=2; j++){
                if(0 <= y+i && y+i < H && 0 <= x+j && x+j < W && S[y+i][x+j] == '.'){
                    if(cost[y+i][x+j] > cost[y][x] + (abs(i) + abs(j) == 1 ? 0 : 1)){
                        cost[y+i][x+j] = cost[y][x] + (abs(i) + abs(j) == 1 ? 0 : 1);
                        pq.push({ -cost[y+i][x+j] ,{y+i,x+j} });
                    }
                }
            }
        }
    }
    if(cost[gy][gx] == 2e9) cout << -1 << endl;
    else cout << cost[gy][gx] << endl;
}

Measured memory_bytes: 9512
#include <stdio.h>

int main(void){

  int a,b;
  char op;

  do{

    scanf("%d %c %d",&a,&op,&b);
  
    switch(op){
    case '+':printf("%d\n",a+b);break;
    case '-':printf("%d\n",a-b);break;
    case '*':printf("%d\n",a*b);break;
    case '/':printf("%d\n",a/b);break;
    case '?':break;
    defalt:break;
    }
  
  }while(op != '?');
  
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    int brr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    brr[i]=arr[i];
    }
    sort(brr,brr+n);
    int mx=brr[n-1];
    int mx2=brr[n-2];
    for(int i=0;i<n;i++)
    {
        if(arr[i]!=mx)
        cout<<mx<<"\n";
        else
        cout<<mx2<<"\n";
    }
}

Measured memory_bytes: 3200
n, k = map(int, input().split())
p = list(map(int, input().split()))

x = [0] * (n-k+1)
x[0] = sum([(i+1)/2 for i in p[:k]])
for i in range(1, n-k+1):
    x[i] = x[i-1] + (-p[i-1] + p[i+k-1])/2

print(max(x))

Measured memory_bytes: 25060
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <atcoder/dsu>

using namespace std;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    int n, m;
    cin >> n >> m;
    atcoder::dsu d(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        d.merge(a, b);
    }
    cout << d.groups().size() - 1 << endl;
}


Measured memory_bytes: 8988
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define io  ios_base::sync_with_stdio(false); cin.tie(NULL); 
    int main() 
    { 
        io
       int  n, k,s=0;
       int c=0;
       cin>>n>>k;
       while(n>k)
       {
          // p=n%k;  
           n=n/k;
       // cout<<n;
        c++;
           
           }   
             
         if(n==k){
               c=c+2;
              
       }
     else{
         c++;
     }
           cout<<c<<endl;
    }

Measured memory_bytes: 256
//参考
//https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int MOD = 1000000007;

vector<vector<int> > calcNext(const string &S)
{
    int n = S.size();
    //
    vector<vector<int>> res(n+1,vector<int>(10,n));

    for(int i = n-1; i >= 0; --i)
    {
        for(int j = 0; j < 10; ++j)
        {
            //iは後ろからなので、直近のres[i][j]が取得できる
            //i番目から見たときの最初に現れる j (0 <= res[i][j] < n)
            res[i][j] = res[i+1][j];
        }
        //該当文字をi番目に指定
        res[i][S[i] - '0'] = i;
    }

    return res;

}

// mod 1000000007 の世界で a += b する関数
void add(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int main() {
    int n;
    cin >> n;
    // 入力
    string S;
    cin >> S;

    // 前処理配列
    vector<vector<int> > next = calcNext(S);

    long long res = 0;

    for (int j = 0; j < 10; ++j) {
      if (next[0][j] >= n) continue; // 次の文字 j がもうない場合はスルー
      ll tugi1 = next[0][j] + 1;
      //cout << tugi1 <<endl;
      for(int k = 0; k < 10; ++k)
      {
        if (next[tugi1][k] >= n) continue; // 次の文字 j がもうない場合はスルー
        ll tugi2 = next[tugi1][k] + 1;
        //cout << tugi2 << endl;
        for(int l = 0; l < 10; ++l)
        {
          if (next[tugi2][l] >= n) continue; // 次の文字 j がもうない場合はスルー
          ++res;
        }
      }
    }

    cout << res << endl;
}

Measured memory_bytes: 2432
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

const int MAX = 2000001;
const int MOD = 1e9+7;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  COMinit();
  ll x,y;
  cin >> x >> y;
  ll ans=0;
  if((x+y)%3!=0){
    cout << 0 << endl;
    return 0;
  }
  ll n=(x+y)/3;
  ll k=(-x+2*y)/3;
  ans=COM(n,k);
  cout << ans << endl;
return 0;}

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

#define all(x)        (x).begin(),(x).end()
#define eb            emplace_back
#define mp            make_pair
#define pb            push_back
#define fi            first
#define se            second
#define sz(x)         ((int)(x).size())
#define rep(x,y,z)    for(int x=y;x<z;x++)
#define per(x,z,y)    for(int x=z-1;x>=y;x--)
#define trav(y,x)     for(auto& y:x)
#define pii           pair<int, int>
#define pll           pair<ll, ll>
#define vi            vector<int>
#define vpi           vector<pii>

int dbg = 0;
#define cri           if(0)
#define shame         cri cerr<<(++dbg)<<"\n\n";

const int MAX = 1e5;
vi adj[2][MAX];

// aaaaaaaaaaaaaaaa
void solve() {
  int N, u, v, w;
  scanf("%d", &N);
  rep(i, 1, N) {
    scanf("%d%d%d", &u, &v, &w);
    --u; --v; w &= 1;
    adj[w][u].pb(v);
    adj[w][v].pb(u);
  }
  
  int ptr = 0;
  vi col(N, -1);
  col[0] = 0;
  vi q; q.pb(0); q.pb(0);
  while (ptr < sz(q)) {
    int x = q[ptr++];
    int c = q[ptr++];
    rep(i, 0, 2) trav(y, adj[i][x]) {
      if (col[y] != -1) continue;
      col[y] = c ^ i;
      q.pb(y); q.pb(col[y]);
    }
  }

  trav(c, col) printf("%d\n", c);
}

int main() {
  // int _; scanf("%d", &_); while (_--)
  solve();
	return 0;
}



Measured memory_bytes: 10744
#include <bits/stdc++.h>
#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}

bool graph[100][100]={false};
int d[100],f[100];
bool visited[100]={false};
int t=0;
void dfs(int gsize,int now){
    if(visited[now]==false)d[now]=++t;
    visited[now]=true;

    for(int i=0;i<gsize;i++){
        if(graph[now][i]==true && visited[i]==false){
            dfs(gsize,i);
        }
    }
    f[now]=++t;
}
int main(void){
    int n;
    cin>>n;
    rep(i,0,n){
        int u,k;
        cin>>u>>k;
        u--;
        rep(j,0,k){
            int v;
            cin>>v;
            v--;
            graph[u][v]=true;
        }
    }
    rep(i,0,n){
        if(visited[i]==false)
            dfs(n,i);
    }
    rep(i,0,n){
        cout<<i+1<<" "<<d[i]<<" "<<f[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3088