akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll x,y;
    cin >> x >> y;
    cout << x + y/2 << endl;

    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 256
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


N, X = LI()
X_list = LI()

#  N = 10**5
#  X = 10**9
#  X_list = [i for i in range(1, 10**5, 5)]

#  if N == 1:
#      print(abs(X_list[0] - 1))
#      exit()
X_list.sort()

bisect.insort_left(X_list, X)
#  print(X_list)
X_diff = [abs(j-i) for i, j in zip(X_list[:-1], X_list[1:])]
X_diff = list(set(X_diff))
#  result = min(X_diff)
# 全部行けない場合がある
# 1 4 9 など
# すべてステップ幅-1で割り切れなければ不可

def gcd(a,b):
    if b == 0: return a
    return gcd(b, a%b)

for i in range(len(X_diff)):
    #  print(i)
    if i == 0:
        result = X_diff[i]
        continue
    
    result = gcd(X_diff[i], result)
#  while True:
#      if all(x % result == 0 for x in X_diff):
#          result = i
#      else:
#          result = [i for i in range(result, 0, -1) if ]

print(result)


Measured memory_bytes: 16656
#include <iostream>

using namespace std;

struct Node {
    int key;
    Node *parent;
    Node *left;
    Node *right;
};

Node *root, *NIL;

Node* newNode(int key) {
    Node *node = new Node();
    node->key = key;
    node->parent = NIL;
    node->left = NIL;
    node->right = NIL;
    return node;
}

void insert(int key) {
    Node *x = root, *y = NIL;
    while (x != NIL) {
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    Node *z = newNode(key);
    z->parent = y;
    if (y == NIL)
        root = z;
    else if (key < y->key)
        y->left = z;
    else
        y->right = z;
}

Node* find(int key) {
    Node *x = root;
    while (x != NIL) {
        if (key == x->key)
            return x;
        else if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    return NIL;
}

Node* nextNode(Node *node) {
    Node *par;
    node = node->right;
    while (node != NIL) {
        par = node;
        node = node->left;
    }
    return par;
}

void nodeDelete(Node *node) {
    if (node == NIL)
        return;
    if (node->left == NIL) {
        if (node->parent->left == node)
            node->parent->left = node->right;
        else
            node->parent->right = node->right;
        if (node->right != NIL)
            node->right->parent = node->parent;
    }
    else if (node->right == NIL) {
        if (node->parent->left == node)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
        if (node->left != NIL)
            node->left->parent = node->parent;
    }
    else {
        Node *next = nextNode(node);
        node->key = next->key;
        nodeDelete(next);
    }
}

void inorder(Node *t) {
    if (t == NIL)
        return;
    inorder(t->left);
    cout << " " << t->key;
    inorder(t->right);
}

void preorder(Node *t) {
    if (t == NIL)
        return;
    cout << " " << t->key;
    preorder(t->left);
    preorder(t->right);
}

int main() {
    int n, v;
    string s;
    root = NIL;
    cin >> n;
    while (n--) {
        cin >> s;
        if (s == "insert") {
            cin >> v;
            insert(v);
        }
        if (s == "find") {
            cin >> v;
            if (find(v) != NIL)
                cout << "yes" << endl;
            else
                cout << "no" << endl;
        }
        if (s == "delete") {
            cin >> v;
            nodeDelete(find(v));
        }
        if (s == "print") {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }

    return 0;
}


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

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;

#define mp make_pair
#define pb push_back
#define pf push_front
#define ss second
#define ff first
#define sz(x) (int)x.size()
#define newl "\n"
#define mem(x, val) memset(x, val, sizeof(x))
#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define all(v) (v).begin(), (v).end()

const ld pi = 3.14159265359;
ll INF = 1e18 + 10;
ll MOD = 998244353;
ll mod = 1e9 + 7;

inline ll add(ll a, ll b, ll m)
{
    if ((a + b) >= m)
        return (a + b) % m;
    return a + b;
}

inline ll mul(ll a, ll b, ll m)
{
    if ((a * b) < m)
        return a * b;
    return (a * b) % m;
}

ll power(ll x,ll y,ll m) {
    ll res = 1; 
    x = x % m;                
    if (x == 0)
        return 0; 
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % m;
        y = y >> 1;
        x = (x * x) % m;
    }
    return res;
}

void solve()
{
    int n,m;
    cin>>n>>m;
    if(m>=n) {
        cout<<"unsafe";
    }
    else {
        cout<<"safe";
    }

}

int main()
{
    fastio;
    int t=1;
    //cin >> t;
    while (t-- > 0)
    {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3652
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int x;

  cin >> x;

  if(x == 3 || x == 5 || x == 7)
    cout << "YES";
  else
  {
    cout << "NO";
  }
  

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 256
r = ['y', 'u', 'i', 'o', 'p', 'h', 'j', 'k', 'l', 'n', 'm']

s = input()
while s != '#':
    cnt = 0
    for i in range(1, len(s)):
        prev = s[i - 1] in r
        cur = s[i] in r

        if prev != cur:
            cnt += 1

    print(cnt)

    s = input()




Measured memory_bytes: 5564
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b){if(a < b){ a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b){if(a > b){ a = b; return 1;} return 0;}

const int INF = 100000; 

int main(){
    string s;
    cin >> s;

    vector<int> alph(26, 0);
    for(int i = 0; i < s.size(); i++){
        alph[s[i] - 'a']++;
    }

    for(int i = 0; i < 26; i++){
        if(alph[i] == 0){
            printf("%c\n", 'a' + i);
            return 0;
        }
    }

    cout << "None" << endl;

    return 0;
}


Measured memory_bytes: 512
def solve(xv_sorted):
    x = [False for _ in range(n)]
    y = [False for _ in range(n)]

    s = 0
    buf = (- 1) * float('inf')
    for i in range(n):
        s += xv_sorted[i][1]##cal 
        x[i] = max(buf, s - 2 * xv_sorted[i][0])##pos
        buf = x[i]

    ##print(x)

    s = 0
    buf = (- 1) * float('inf')
    for i in sorted(range(n), reverse=True):
        s += xv_sorted[i][1]##cal 
        y[i] = max(buf, s - (c - xv_sorted[i][0]))##pos
        buf = y[i]

    ##print(y)

    ans = max(x[n - 1], y[0])
    for i in range(n - 1):
        ans = max(ans, x[i] + y[i + 1])

    return ans

if __name__ == '__main__':
    n, c = map(int, input().split())
    xv = []
    for i in range(n):
        xv.append(list(map(int, input().split())))
    xv_sorted = sorted(xv, key=lambda x:x[0])
    ans = 0
    ans = max(ans, solve(xv_sorted))

    for i in range(n):
        xv_sorted[i][0] = abs(c - xv_sorted[i][0]) 
    xv_sorted = sorted(xv, key=lambda x:x[0])
    ans = max(ans, solve(xv_sorted))
    print(ans)

Measured memory_bytes: 40772
// C - Together
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int solve(int N, vi &A){
	sort(all(A));
	vi C(100000+1);
	rp(i, 0, N) C[A[i]]++;
	int a = C[0], b = C[1], c = C[2];
	int ans = a + b + c;
	rp(i, 3, C.size())
		if(C[i] != 0){
			a = b; b = c; c = C[i];
			ans = max(ans, a+b+c);
		}
	return ans;
}

int main(){
	int N; cin>>N;
	vi A(N); rp(i, 0, N) cin>>A[i];
	cout<< solve(N, A) <<endl;
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n,n){
        string st,en;
        int table[100000]={};
        REP(i,n){
            cin >> st>>en;
            int stim=0;
            stim+=(st[0]-'0')*10+(st[1]-'0');
            stim*=60;
            stim+=(st[3]-'0')*10+(st[4]-'0');
            stim*=60;
            stim+=(st[6]-'0')*10+(st[7]-'0');
            int etim=0;
            etim+=(en[0]-'0')*10+(en[1]-'0');
            etim*=60;
            etim+=(en[3]-'0')*10+(en[4]-'0');
            etim*=60;
            etim+=(en[6]-'0')*10+(en[7]-'0');

            table[stim]+=1;
            table[etim]+=-1;
        }
        int res=0,sum=0;
        for(int i=0;i<100000;i++){
//            if(table[i])cout << i/3600 <<" "<<table[i]<<endl;
            sum+=table[i];
            res=max(res,sum);
        }
        cout << res << endl;
    }
}



Measured memory_bytes: 3584
N=int(input())
ab=[list(map(int,input().split())) for i in range(N-1)]
M=int(input())
uv=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
node=[[-1]*(N+1) for i in range(N-1)]
for i in range(N-1):
    a,b=ab[i]
    flag=[0]*(N+1)
    flag[a]=1
    flag[b]=1
    node[i][a]=0
    que=[a]
    while que:
        u=que.pop()
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                node[i][v]=0
                que.append(v)
    node[i][b]=1
    que=[b]
    while que:
        u=que.pop()
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                node[i][v]=1
                que.append(v)
dp=[[0]*2**M for i in range(N)]
dp[0][0]=1
for i in range(N-1):
    h=node[i]
    num=0
    for j in range(M):
        u,v=uv[j]
        if h[u]==h[v]:
            continue
        else:
            num+=2**j
    dp[i+1]=dp[i][:]
    for j in range(2**M):
        dp[i+1][j|num]+=dp[i][j]
print(dp[-1][-1])

Measured memory_bytes: 657908
n = int(input())

j = list(map(int, input().split()))
k = [j[0]]
for i in range(1, len(j)):
    k.append(k[i-1] + j[i])
mi = 9999999999
for m in range(len(k)-1):
    mi = min(abs(k[n - 1] - 2 * k[m]), mi)
print(mi)

Measured memory_bytes: 24824
import heapq
N, M = map(int, input().split())
jobs = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    jobs[M-A].append(B)
ans = 0
q = []
heapq.heapify(q)
for i in range(M-1, -1, -1):
    for item in jobs[i]:
        heapq.heappush(q, item * (-1))
    if q:
        ans += heapq.heappop(q) * (-1)
print(ans)

Measured memory_bytes: 18388
S = input()

res_list = []

for i in range(2**(len(S)-1)):
    temp_s = ''
    for j in range(len(S)):
        temp_s += S[j]
        if ((i >> j) & 1):
            temp_s += '+'
    # print(temp_s)
    res_list.append(temp_s)

temp_S_list = [eval(item) for item in res_list]

print(sum(temp_S_list))

Measured memory_bytes: 9144
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<n; i++) a[i]--;
    int cnt=0,now=0;
    for(int i=0; i<n; i++){
        if(now==1){
            cout<<cnt<<endl;
            return 0;
        }else{
            cnt++;
            now=a[now];
        }
    }
    cout<<-1<<endl;
}


Measured memory_bytes: 640
// ITP1_11_D
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
template <class T>
ostream &operator<<(ostream &o, const vector<T> &v)
{
    o << "{";
    for (int i = 0; i < (int)v.size(); i++)
        o << (i > 0 ? ", " : "") << v[i];
    o << "}";
    return o;
}
namespace you
{
std::string to_string(char val)
{
    return std::string(1, val);
    // return std::string{val};
    // you::to_string(char)
}
} // namespace you

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    string order = "EEEENEEEENEEEENEEEEENEEEENNEEEE"; //全パターン
    int num;
    cin >> num;
    vector<vector<int>> di(num, vector<int>(6));

    for (int i = 0; i < num; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            int s;
            cin >> s;
            di[i][j] = s;
        }
    }

    struct local
    {
        static tuple<int, int, int, int> c_sn(vector<vector<int>> di, int x)
        {
            return forward_as_tuple(di[x][0], di[x][1], di[x][4], di[x][5]);
        }
        static tuple<int, int, int, int> c_we(vector<vector<int>> di, int x)
        {
            return forward_as_tuple(di[x][0], di[x][2], di[x][3], di[x][5]);
        }
    };

    bool flag1 = false; //一組でも同じやつあればダメ。
    int count = 0;
    for (int i = 0; i < num - 1; i++)
    {
        for (int j = i + 1; j < num; j++)
        {
            bool flag2 = false; //i,jが違うと仮定。
            for (int k = 0; k < order.size(); k++)
            {
                // if(i==0 and j==1){
                //     cout<<di[i];
                //     cout<<di[j]<<endl;
                // }
                //count++;
                int a, b, c, d;
                if (order[k] == 'N')
                {
                    tie(a, b, c, d) = local::c_sn(di, j);
                    di[j][0] = b;
                    di[j][1] = d;
                    di[j][4] = a;
                    di[j][5] = c;
                }
                else
                {
                    tie(a, b, c, d) = local::c_we(di, j);
                    di[j][0] = c;
                    di[j][2] = a;
                    di[j][3] = d;
                    di[j][5] = b;
                }
                bool flag_ = true;
                for (int l = 0; l < 6; l++)
                {
                    if (di[i][l] != di[j][l])
                    {
                        flag_ = false;
                    }
                }
                if (flag_)
                {
                    //cout<<di<<endl;
                    flag2 = true;
                    break;
                }
            }
            if (flag2)
            {
                flag1 = true;
                break;
            }
        }
        if (flag1)
        {
            break;
        }
    }
    if (flag1)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
    //cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3228
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,child,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

int h[100];
int main(){
  int N;
  cin >> N;
  rep(i, N) cin >> h[i];
  int ans = 0;
  rrep(H, 101, 1){
    rep(i, N){
      if((i == 0 || h[i - 1] < H) && h[i] >= H) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int d[60][3010]={1};
int main(){
  int a,b,c,i,j,k;
  while(scanf("%d %d %d",&a,&b,&c),a){
    for(i=0;i<50*3000;i++)d[i/3000][i%3000]=0;
    d[0][0]=1;
    for(j=1;j<=b;j++){
      for(i=a*a;i;i--){
	for(k=0;k<c;k++){
	  //printf("%3d ",d[i-1][k]);
	  if(k+j<=c)d[i][k+j]=(d[i][k+j]+d[i-1][k])%100000;
	}//printf("\n");
      }//printf("\n\n");
    }
    printf("%d\n",d[a*a][c]);
  }
  return 0;
}
  

Measured memory_bytes: 1192
n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
d={}
for i in range(n):
  d[s[i]] = d.get(s[i],0) + 1
for j in range(m):
  d[t[j]] = d.get(t[j],0) - 1
print(max(d.values()) if max(d.values())>0 else 0)

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

#define ll long long
 
ll dp[3001][3001][2];
ll solve(vector<int>& v, int i, int j, bool turn)
{
    if(i > j)
        return 0;
    
    if(dp[i][j][turn] != -1)
        return dp[i][j][turn];
    
    if(turn == 1)
        return dp[i][j][turn] = max(v[i] + solve(v, i+1,j,0), v[j] + solve(v, i,j-1, 0));
    else return dp[i][j][turn] = min(solve(v, i+1,j,1), solve(v, i,j-1, 1));
}
 
int main() {
   int n;
   cin >> n ;
   vector<int> v(n+1);
   memset(dp, -1, sizeof dp);
   ll sum = 0;
   for(int i = 1; i <= n; i++)
    {
        cin>>v[i];
        sum += v[i];
    }
   ll scoreX = solve(v, 1, n, 1);
   ll scoreY = (sum - scoreX);
   cout << scoreX - scoreY;
   return 0;
}

Measured memory_bytes: 144592
<?php
$str1 = trim(fgets(STDIN));
$str2 = trim(fgets(STDIN));
$array = explode(" ", $str2);
$d2 = $array[1];
 
if($d2 < 2){
  $answer = 1;
} else {
  $answer = 0;
}
 
echo "$answer".PHP_EOL;

Measured memory_bytes: 3828
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int N,H,pre=0,maxL=0,ans[100000]={0};
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>H;
		if(pre>=H){
			ans[i]=ans[i-1]+1;
			maxL=max(ans[i],maxL);
		}
		pre=H;
	}
	cout<<maxL;
	return 0;
}

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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORTASC(c) sort((c).begin(),(c).end())
#define SORTDESC(c,t) sort((c).begin(),(c).end(), std::greater<t>());
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define OUT(a) cout << (a) << endl;
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double PI  = acos(-1.0);
const long long MOD = 1000000007;

template <class T, class S>
using umap = std::unordered_map<T, S>;
using ll = long long;
using namespace std;

int main() {
    ll n, x, y;
    umap<ll, ll > mp;

    cin >> n >> x >> y;

    REP(i, n+1){
        REP(j, n+1){
            if (i >= j || i == 0 || j == 0){
                continue;
            }

            ll dist = min(min(abs(j-i), abs(x-i)+1+abs(j-y)), abs(y-i)+1+abs(j-x));
            mp[dist]++;
        }
    }

    REP(i, n-1){
        cout << mp[i+1] << endl;
    }

    return 0;
}

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

typedef long long int lli;

lli n, s;

vector<lli> divisors;

bool checkValid(lli n, lli s, lli b) {
	lli actual = 0;
	while(n) {
		actual += (n%b);
		n /= b;
	}
	return (actual == s);
}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n >> s;

	if(n < s) {
		cout << -1 << endl;
		return 0;
	} else if(n == s) {
		cout << n+1 << endl;
		return 0;
	}

	lli m = n - s;

	for(lli i = 1; i < (lli)(sqrt(m)+1.5); i++) {
		if(m%i == 0) {
			divisors.push_back(i);
			divisors.push_back(m/i);
		}
	}

	sort(divisors.begin(), divisors.end());

	for(lli d: divisors) {
		if(checkValid(n, s, d+1)) {
			cout << d+1 << endl;
			return 0;
		}
	}

	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;
signed main(){
    int N; cin>>N;
    double ans = 1;
    ans = N*2*3.14159265358979;
    cout << fixed << setprecision(10);
    cout<<ans<<endl;
}

Measured memory_bytes: 3792
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7
    N,K = map(int, input().split())
    s = list(input().rstrip())
    l = []
    for k,v in groupby(s):
        l.append(len(list(v)))

    res = 0
    if s[0]=='1':
        start = 0
        stop = 2*K+1
        res = sum(l[:stop])
        ans = res
        while start<len(l):
            res += sum(l[stop:stop+2])-sum(l[start:start+2])
            ans = max(ans, res)
            start += 2
            stop += 2
    else:
        start = 1
        stop = 2*K+2
        res = sum(l[start:stop])
        ans = res
        while start<len(l):
            res += sum(l[stop:stop+2])-sum(l[start:start+2])
            ans = max(ans, res)
            start += 2
            stop += 2
        ans = max(ans, sum(l[:2*K]))
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 5432
// E - Divisible Substring
#include <bits/stdc++.h>
using namespace std;
#define c2d(c) ((c)-'0') // char to digit

int main() {
	int N,P; string S; cin>>N>>P>>S;
	long long total = 0;
	if(10%P == 0){ // P={2,5}
		for(int i=0; i<N; ++i)
			if(c2d(S[i]) % P == 0) total += i+1;
	}
	else{
		reverse(S.begin(), S.end());
		vector<int> cnt(P, 0);
		int r = 0, ten = 1;
		cnt[r]++; // for half-open section
		for(char si:S){
			// n=count(r), nC2 = {n-1}C2 + {n-1}
			// {n-1} = count(r): previous of count up
			// ∴ total = total + {count of previous of count up}
			r = (r + c2d(si)*ten) % P;
			total += cnt[r];
			cnt[r]++;
			ten = ten * 10 % P;
		}
	}
	cout << total << endl;
}

Measured memory_bytes: 644
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define mk make_pair
#define fi first
#define se second
#define N 300010
#define M 100010
int n, m;
pii a[N];

int q[M],  rt[M], L[M * 100], R[M * 100], t[M * 100], len = 0;
void add(int pre, int &now, int l, int r, int x) {
	now = ++ len; t[now] = t[pre] + 1;
	if (l == r) return ;
	int mid = (l + r) >> 1;
	if (x <= mid) add(L[pre], L[now], l, mid, x), R[now] = R[pre];
	else add(R[pre], R[now], mid + 1, r, x), L[now] = L[pre];
}
int query(int p, int l, int r, int ql, int qr) {
	if (!p) return 0;
	if (ql <= l && r <= qr) return t[p];
	int mid = (l + r) >> 1;
	int res = 0;
	if (ql <= mid) res += query(L[p], l, mid, ql, qr);
	if (mid < qr) res += query(R[p], mid + 1, r, ql, qr);
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i].fi >> a[i].se;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++ i) {
		if (i > 1) {
			for (int j = a[i - 1].fi + 1; j < a[i].fi; ++ j) rt[j] = rt[a[i - 1].fi];
		}
		add(rt[a[i - 1].fi], rt[a[i].fi], 1, m, a[i].se);
	}
	for (int j = a[n].fi + 1; j <= m; ++ j) rt[j] = rt[a[n].fi];
	for (int d = 1; d <= m; ++ d) {
		int ans = 0;
		for (int i = 1; i * d <= m; ++ i) {
			// l : [(i - 1) * d + 1, i * d] r : [i * d, m]
			ans += query(rt[i * d], 1, m, i * d, m);
			ans -= query(rt[(i - 1) * d], 1, m, i * d, m);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 72064
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class ABC
	{
		static int mod = 1000000007;  // 10^9+7

		static void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });


			//int n = int.Parse(Console.ReadLine());
			//string s = Console.ReadLine();
			long[] vs = Console.ReadLine().Split().Select(long.Parse).ToArray();
			long n = vs[0];
			long x = vs[1];

			long[,] burger = new long[n + 1, 2];
			burger[0, 0] = 1;   // 全体の厚さ
			burger[0, 1] = 1;   // パティの数
			for (int i = 1; i < n + 1; i++) {
				burger[i, 0] = burger[i - 1, 0] * 2 + 3;
				burger[i, 1] = burger[i - 1, 1] * 2 + 1;
			}

			long ans = 0;
			long lv = n;
			while (x > 0) {
				lv--;
				if (x >= 1) {
					x--;
				}
				if (x < burger[lv, 0]) {
					continue;
				} else {
					x -= burger[lv, 0];
					ans += burger[lv, 1];
				}
				if (x >= 1) {
					x--;
					ans++;
				}
				if (x < burger[lv, 0]) {
					continue;
				} else {
					x -= burger[lv, 0];
					ans += burger[lv, 1];
				}
				if (x >= 1) {
					x--;
				}
			}
			Console.WriteLine(ans);


			Console.Out.Flush();
		}
	}
}


Measured memory_bytes: 13396
// CONTEST

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

// Utility
#define ALL(X) (X).begin(), (X).end()
#define FOR(I, X, Y) for (int I = (X); I < (Y); I++)
using ll = int64_t;
using ull = uint64_t;
template<typename T> struct is_container {
template<typename C> static char test(typename C::const_iterator*); template<typename> static int test(...);
static bool const value = sizeof(test<T>(nullptr)) == sizeof(char) && !std::is_same<std::string, T>::value;
};
namespace std {
template<class ...Ts>        istream& operator>>(istream& i, tuple<Ts...>& x) { apply([&](auto&&... ys){ ((i >> ys), ...); }, x); return i; }
template<class T1, class T2> istream& operator>>(istream& i, pair<T1, T2>& x) { i >> x.first >> x.second; return i; }
template<class T, enable_if_t<is_container<T>::value, int> = 0>
istream& operator>>(istream& i, T& x) { for (auto& y : x) { i >> y; } return i; }
}

// Debugging
#ifndef DEBUG
#define DEBUG 0
#endif
#define dbg(X) do { if (DEBUG) { cout << #X ": " << (X) << endl << flush; } } while (0)
#define dbg2(X) do { if (DEBUG) { cout << #X ":" << endl; for (auto& __x : (X)) { cout << __x << endl << flush; } } } while (0)
#define dbgv(...) do { if (DEBUG) { cout << "(" #__VA_ARGS__ "): " << make_tuple(__VA_ARGS__) << endl << flush; } } while (0)
namespace std {
template<class ...Ts>        ostream& operator<<(ostream& o, const tuple<Ts...>& x) { o << "("; apply([&](auto&& y, auto&&... ys){ o << y; ((o << ", " << ys), ...); }, x); o << ")"; return o; }
template<class T1, class T2> ostream& operator<<(ostream& o, const pair<T1, T2>& x) { o << tie(x.first, x.second); return o; }
template<class T, enable_if_t<is_container<T>::value, int> = 0>
ostream& operator<<(ostream& o, const T& x) { o << "{"; for (auto it = x.begin(); it != x.end(); it++) { if (it != x.begin()) { o << ", "; } o << *it; } o << "}"; return o; }
}

// DSU
struct Dsu {
  vector<int> data_;
  Dsu(int n) { data_.resize(n); iota(ALL(data_), 0); }
  int find(int a) {
    if (data_[a] == a) { return a; }
    return data_[a] = find(data_[a]);
  }
  void merge(int dst, int src) {
    data_[find(src)] = find(dst);
  }
};

// Main
void mainCase() {
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int>> edges(m, {0, 0});
  cin >> edges;

  Dsu dsu(n);
  for (auto [x, y] : edges) {
    x--; y--;
    dsu.merge(x, y);
  }

  map<int, int> compos;
  FOR(i, 0, n) {
    compos[dsu.find(i)]++;
  }

  int res = 0;
  for (auto [k, v] : compos) {
    res = max(res, v);
  }
  cout << res << endl;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  // [ Single case ]
  mainCase();
  return 0;
  // [ Multiple cases ]
  // int t;
  // cin >> t;
  // FOR(i, 0, t) { mainCase(); }
  // return 0;
}

/*
python misc/run.py atcoder/abc177/d/main.cpp --check

%%%% begin
5 3
1 2
3 4
5 1
%%%%
3
%%%% end
*/


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

int main() {
  string s;
  cin>>s;
  int cnt = 0;
  for (int i=0; i<s.length(); i++) {
    if (i % 2 == 0) {
      if (s[i] == 'p') {
        --cnt;
      }
    } else {
      if (s[i] == 'g') {
        ++cnt;
      }
    }
  }
  cout<<cnt<<endl;
}

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

int main() {
	long long n;
	cin >> n;
	long long a[n + 1], b[n + 1];
	long long ans1 = 0, ans2 = 0;
	for (long long i = 1; i <= n; i++) cin >> a[i];
	for (long long i = 1; i <= n; i++) cin >> b[i];
    for (long long i = 1; i <= n; i++) {
        if(a[i] > b[i]) ans1 += (a[i] - b[i]);
        if(a[i] < b[i]) ans2 += (b[i] - a[i]) / 2;
	}
	if (ans1 <= ans2) cout << "Yes";
    else cout << "No";
	return 0;
}
/**
 *                    _ooOoo_
 *                   o8888888o
 *                   88" . "88
 *                   (| -_- |)
 *                    O\ = /O
 *                ____/`---'\____
 *              .   ' \\| |// `.
 *               / \\||| : |||// \
 *             / _||||| -:- |||||- \
 *               | | \\\ - /// | |
 *             | \_| ''\---/'' | |
 *              \ .-\__ `-` ___/-. /
 *           ___`. .' /--.--\ `. . __
 *        ."" '< `.___\_<|>_/___.' >'"".
 *       | | : `- \`.;`\ _ /`;.`/ - ` : | |
 *         \ \ `-. \_ __\ /__ _/ .-` / /
 * ======`-.____`-.___\_____/___.-`____.-'======
 *                    `=---='
 *
 * .............................................
 *          佛祖保佑             永无BUG
 */



Measured memory_bytes: 384
N, K, Q = map(int, input().split())
A = []
point_list = [0] * N
for i in range(Q):
    a = int(input())
    A.append(input)
    point_list[a - 1] += 1

if K > Q:
    for i in range(N):
        print('Yes')
    exit()

for p in point_list:
    if p > Q - K:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 5376
#include<map>
#include<cstdio>
#include<iostream>
#define ooo(msg, ...) printf("(%s #%d) " msg, __FUNCTION__, __LINE__, __VA_ARGS__);
using namespace std;
typedef long long ll;
const int mo = 1e9+7;
ll n;
map < ll , ll > dp;
ll f(ll n) {
	return dp.count(n) ? dp[n] : dp[n] = (f(n / 2) % mo + f((n - 1) / 2) % mo + f((n - 2) / 2)% mo) % mo;
}
int main() {
	scanf("%lld", &n);
	dp[0] = 1; dp[1] = 2;
	printf("%lld\n", f(n));
	return 0;	
}


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

using db = double;
using ll = long long;
using vi = vector <int>;
#define op operator
#define pb push_back

const int N = 11;
char c[N][N];

int main() {
	ios :: sync_with_stdio(0);

	while(cin >> c[1][1]) {
		for(int i = 1; i <= 8; i ++)
			for(int j = 1; j <= 8; j ++)
				if(i > 1 || j > 1) cin >> c[i][j];
		int xi = 9, yi = 9, xa = 0, ya = 0;
		for(int i = 1; i <= 8; i ++)
			for(int j = 1; j <= 8; j ++) if(c[i][j] == '1') {
				xi = min(xi, i);
				yi = min(yi, j);
				xa = max(xa, i);
				ya = max(ya, j);
			}
		int dx = xa - xi + 1, dy = ya - yi + 1;
		if(dx == 2 && dy == 2) cout << "A\n";
		if(dx == 4 && dy == 1) cout << "B\n";
		if(dx == 1 && dy == 4) cout << "C\n";
		if(dx == 3 && dy == 2) {
			if(c[xi][yi] == '0') cout << "D\n";
			else cout << "F\n";
		}
		if(dx == 2 && dy == 3) {
			if(c[xi][yi] == '1') cout << "E\n";
			else cout << "G\n";
		}
	}

	return 0;
}

Measured memory_bytes: 3140
#include<stdio.h>
#define M 10000
#define NIL (-1)

typedef struct{
  int parent,left,right;
}node;

node t[M];


void preparse(int);
void inparse(int);
void postparse(int);

int main(){
  int n,i,v,left,right,root;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    t[i].parent = NIL;
  }
  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&left,&right);
    t[v].left = left;
    t[v].right = right;
    if(left != NIL) t[left].parent = v;
    if(right != NIL) t[right].parent = v;
  }

  for(i=0;i<n;i++) if(t[i].parent == NIL) root = i;

  printf("Preorder\n");
  preparse(root);
  printf("\n");
  printf("Inorder\n");
  inparse(root);
  printf("\n");
  printf("Postorder\n");
  postparse(root);
  printf("\n");
  
  return 0;
}

void preparse(int n){
  if(n == NIL) return;
  printf(" %d",n);
  preparse(t[n].left);
  preparse(t[n].right);

}

void inparse(int n){
  if(n==NIL) return;

  inparse(t[n].left);
  printf(" %d",n);
  inparse(t[n].right);

}

void postparse(int n){
  if(n==NIL) return;

  postparse(t[n].left);
  postparse(t[n].right);
  printf(" %d",n);

}



Measured memory_bytes: 2104
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<bool> d(1000005);
  vector<bool> visited(1000005);
  rep(i, n){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  rep(i, n){
    int x=a[i];
    if(visited[x])continue;
    visited[x]=true;
    while(x+a[i]<=1000000){
      x+=a[i];
      d[x]=true;
    }
  }
  int ans=0;
  rep(i, n){
    if(!d[a[i]]){
      if(i!=0 && a[i]==a[i-1])continue;
      if(i!=n-1 && a[i+1]==a[i])continue;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4292
import java.util.*;

//update 2020/1/1 23:01

public class Main{

  static Scanner sc = new Scanner(System.in);
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {

    int k = nextInt();
    int a = nextInt();
    int b = nextInt();

    boolean ok = false;

    for(int i=a;i<=b;i++){
      if(i%k==0){
        ok = true;
      }
    }

    if(ok){
      System.out.println("OK");
    }
    else{
      System.out.println("NG");
    }

  }

  static int lcm(int a,int b){
    return a*b*gcd(a,b);
  }

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

  /*
    static String toSmall(String s){
      char c = s.charAt(0);
      //if(Character.isUpperCase(c)){
      if(c<=90){
        c += 32;
      }
      return String.valueOf(c);
    }
    static String toBig(String s){
      char c = s.charAt(0);
      //if(Character.isLowerCase(c)){
      if(c>=97){
        c -= 32;
      }
      return String.valueOf(c);
    }
  */

  static String toSmall(String s){
    return s.toLowerCase();
  }

  static String toBig(String s){
    return s.toUpperCase();
  }

  static String next(){
    return sc.next();
  }

  static int nextInt(){
    return Integer.parseInt(sc.next());
  }

  static long nextLong(){
    return Long.parseLong(sc.next());
  }

  static double nextDouble(){
    return Double.parseDouble(sc.next());
  }

  static String[] splitString(String s){
    return s.split("");
  }

  static char[] splitChar(String s){
    return s.toCharArray();
  }

  static int charToInt(char a){
    return a - 48;
  }

////////////////////////////////////////////
  public static int max(int[] a){
    int lng = a.length;
    int max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
  public static long max(long[] a){
    int lng = a.length;
    long max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
////////////////////////////////////////////

////////////////////////////////////////////
  public static int min(int[] a){
    int lng = a.length;
    int min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
  public static long min(long[] a){
    int lng = a.length;
    long min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
////////////////////////////////////////////

}


Measured memory_bytes: 35740
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

const int V = 2500;
const int E = 5000;
int n, m, p, a[E], b[E], c[E], d[2][V], INF = -1e9;
bool loop[2][V];

int main() {
	cin >> n >> m >> p;
	inc(i, m) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
		c[i] -= p;
	}
	
	inc(k, 2) {
	inc(i, n) {
		d[k][i] = INF;
	}
	}
	d[0][0] = 0;
	d[1][n - 1] = 0;
	inc(k, 2) {
		inc(q, 2 * n) {
			inc(i, m) {
				if(d[k][a[i]] == INF) { continue; }
				loop[k][b[i]] |= setmax(d[k][b[i]], d[k][a[i]] + c[i]) && (q >= n);
			}
		}
		inc(i, m) { swap(a[i], b[i]); }
	}
	setmax(d[0][n - 1], 0);
	
	bool inf = false;
	inc(i, n) { inf |= (loop[0][i] && loop[1][i]); }
	
	cout << (inf ? -1 : d[0][n - 1]) << endl;
	
	return 0;
}


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

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...)
#endif

namespace solver{
  void solve(){
    int H, W, M; std::cin >> H >> W >> M;

    std::vector<int> h(M), w(M);
    for(int i = 0; i < M; ++i){
      std::cin >> h[i] >> w[i];
      h[i] -= 1;
      w[i] -= 1;
    }

    std::set<std::pair<int, int>> set;
    for(int i = 0; i < M; ++i) set.insert(std::make_pair(h[i], w[i]));

    std::vector<int> count_row(H), count_col(W);
    for(int i = 0; i < M; ++i){
      count_row[h[i]] += 1;
      count_col[w[i]] += 1;
    }

    int MAX = 0;
    MAX += *max_element(count_row.begin(), count_row.end());
    MAX += *max_element(count_col.begin(), count_col.end());

    dump(MAX);
    

    std::map<int, std::vector<int>> mh, mw;
    for(int i = 0; i < H; ++i) mh[count_row[i]].push_back(i);
    for(int i = 0; i < W; ++i) mw[count_col[i]].push_back(i);

    int64_t c = 0;
    for(int i = 0; i <= MAX; ++i){
      c += (int64_t)mh[i].size() * (int64_t)mw[MAX - i].size();
    }

    int ans;
    
    if(c > M){
      ans = MAX;
    }else{
      bool check = false;
      [&](){
        for(int i = 0; i <= MAX; ++i){
          for(auto x : mh[i]){
            for(auto y : mw[MAX - i]){
              //dump(std::make_pair(x, y));
              if(set.find(std::make_pair(x, y)) == set.end()){
                check = true;
                return;
              }
            }
          }
        }
      }();

      if(check) ans = MAX;
      else ans = MAX - 1;
    }
    
    std::cout << ans << "\n";
  }
}

int main(){
  solver::solve();
  return 0;
}


Measured memory_bytes: 71080
#include<iostream>
#include <cstddef>
#include<set>
#include<stack>
#include <deque>
#include<queue>
#include<utility>
#include<vector>
#include<map>
#include<cmath>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#define  ll  long long
#define ull unsigned long long
#define  sl(a)  scanf("%lld",&a)
#define  si(a)  scanf("%d",&a)
#define mem(n,m) memset(n,m,sizeof(n))
#define PI acos(-1)
#define pb    push_back
#define pf    push_front
#define vll   vector<ll>
#define pll   pair<ll,ll>
#define mp  make_pair
#define vpll vector< pair <ll,ll> >
#define vplpll vector<pair<ll,pair<ll,ll> > >
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S(X) ( (X) * (X) )
#define forab(i, a, b) for(i = a; i <= b; i++)
#define forn(i, n) for(i = 0; i < n; i++)
#define print(a,b) printf("Case %lld: %lld\n",a,b)
using namespace std;
ll powd(ll a,ll b){if(b==1){return a;}if(b%2==1){return powd(a,b-1)*a;}else{ll x=powd(a,b/2); return x*x;}}
ll powm(ll a,ll b,ll m){if(b==0){return 1;}if(b==1){return a%m;}if(b%2==1){return ((powm(a,b-1,m)%m)*(a%m))%m;}else{ll x=powm(a,b/2,m); return ((x%m)*(x%m))%m;}}
ll gcd(ll a,ll b){if(a==0){return b;}return gcd(b,a%b);}
int main()
{
    string s;
    cin>>s;
    ll l=s.length();
    ll sum=0;
    for(ll i=0;i<l;i++)
    {
        sum+=(s[i]-'0');
    }
    if(sum%9==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

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

using namespace std;

struct SegmentTree
{
  vector< int > seg;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, 0);
  }

  void set(int k, int x)
  {
    seg[k + sz - 1] = x;
  }

  void build()
  {
    for(int k = sz - 2; k >= 0; k--) {
      seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }

  int rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (0);
    if(a <= l && r <= b) return (seg[k]);
    return (max(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
                rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }

  int rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }
};

struct edge
{
  int to, cost;
};

int N;
vector< edge > g[100000];

int start[100000], stop[100000], ptr, depth[100000];

void dfs(int idx, int par)
{
  start[idx] = ptr++;
  for(edge& e : g[idx]) {
    if(e.to == par) continue;
    depth[e.to] = depth[idx] + e.cost;
    dfs(e.to, idx);
  }
  stop[idx] = ptr;
}

pair< int, int > dia(int idx, int par)
{
  pair< int, int > ret(0, idx);
  for(edge& e : g[idx]) {
    if(e.to == par) continue;
    auto child = dia(e.to, idx);
    ret = max(ret, {child.first + e.cost, child.second});
  }
  return (ret);
}

int calc(int idx)
{
  ptr = 0;
  depth[idx] = 0;
  dfs(idx, -1);
  SegmentTree tree(2 * N);
  for(int i = 0; i < N; i++) tree.set(start[i], depth[i]);
  tree.build();

  int ret = 0;
  for(int i = 0; i < N; i++) {
    for(edge e : g[i]) {
      if(depth[e.to] < depth[i]) e.to = i;
      ret = max(ret, max(tree.rmq(0, start[e.to]), tree.rmq(stop[e.to], 2 * N)) + e.cost);
    }
  }
  return (ret);
}

int main()
{
  scanf("%d", &N);
  for(int i = 1; i < N; i++) {
    int P, W;
    scanf("%d %d", &P, &W);
    g[P].push_back((edge) {i, W});
    g[i].push_back((edge) {P, W});
  }
  auto p = dia(0, -1);
  auto q = dia(p.second, -1);
  cout << max(calc(p.second), calc(q.second)) << endl;
}

Measured memory_bytes: 18164