akhauriyash/Code-Regression huggingface dataset:
def getval():
    n,w = map(int,input().split())
    p = [list(map(int,input().split())) for i in range(n)]
    return n,w,p 

def main(n,w,p):
    #DP[n][w] 
    dp = [[0 for i in range(w+1)]]
    for i in range(n):
        item = p[i]
        temp = []
        for j in range(w+1):
            cur = dp[i][j]
            if j>=item[0]:
                cur = max(cur,dp[i][j-item[0]]+item[1])
            temp.append(cur)
        dp.append(temp)
    print(dp[n][w])
                
if __name__=="__main__":
    n,w,p = getval()
    main(n,w,p)

Measured memory_bytes: 220068
N, K = map(int, input().split())
As = list(map(int, input().split()))

maxDgt = 40

fss = [[0]*(2) for _ in range(maxDgt)]
for A in As:
    for i in range(maxDgt):
        fss[maxDgt-1-i][A&(1<<i) == 0] += 1<<i

K += 1

dp = [[-float('inf')]*(2) for _ in range(maxDgt+1)]
dp[0][0] = 0
for dgt, Kd in enumerate(map(int, bin(K)[2:].zfill(maxDgt))):
    for isLeK in range(2):
        xLim = 1 if isLeK else Kd
        for xd in range(xLim+1):
            isLeK2 = isLeK or xd < xLim
            dp[dgt+1][isLeK2] = max(dp[dgt+1][isLeK2], dp[dgt][isLeK] + fss[dgt][xd])

print(dp[-1][1])


Measured memory_bytes: 14620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    ll a, b, k;
    cin >> a >> b >> k;
    ll remain = 0;
    if (a < k) remain = k - a;
    cout << max(a - k, 0LL) << " " << max(b - remain, 0LL) << endl;
    return 0;
}


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

typedef long long int llint;

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

  int a[100001];
  map<int, int> m;
  
  for(int i = 0; i < n; i++) {
    cin>> a[i];
    if(!m[a[i]]) m[a[i]] = 0;
    m[a[i]]++;
  }

  int cnt = 0;
  
  for(int i = 0; i < n; i++) {
    if(m[a[i]] == -1) continue;

    if(m[a[i]] < a[i]) cnt += m[a[i]];
    else cnt += m[a[i]] - a[i];
    m[a[i]] = -1;
  }

  cout<< cnt <<endl;
  
  return 0;
}


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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    vector<ll> l(n);
    REP(i, n)
    cin >> l[i];
    SORT(l);
    ll sum = 0;
    REP(i, n - 1)
    {
        sum += l[i];
    }
    if (l[n - 1] < sum)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 200000;
int N;
int parent[MAX_N];
int vrank[MAX_N];


void init_union_find()
{
     for (int i = 0; i < N; ++i) {
          parent[i] = i;
          vrank[i] = 0;
     }
}


int find(int x)
{
     if (parent[x] == x) {
          return x;
     } else {
          return parent[x] = find(parent[x]);
     }
}


void unite(int x, int y)
{
     x = find(x);
     y = find(y);
     if (x == y) return;
    
     if (vrank[x] < vrank[y]) {
          parent[x] = y;
     } else {
          parent[y] = x;
          if (vrank[x] == vrank[y]) vrank[x]++;
     }
}


bool same(int x, int y)
{
     return find(x) == find(y);
}

int main() {
    int M;
    cin >> N >> M;
    init_union_find();
    for (int i = 0; i < M; i++) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        unite(X-1, Y-1);
    }
    unordered_set<int> s;
    for (int i = 0; i < N; i++) {
        s.insert(find(i));
    }
    cout << s.size() << endl;
    return 0;
}


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

int main(void) {
    int n;
    bool flag = false;
    cin >> n;

    for (int i = 1; i < 10; i++) {
        int a = n % i;
        if (a == 0 && (n / i) < 10) {
            cout << "Yes" << endl;
            flag = true;
            break;
        }
    }

    if (flag == false) {
        cout << "No" << endl;
    }

    return 0;
}

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

using namespace std;
using P = pair<int, int>;

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

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

signed main(){
    int N; cin >> N;
    vector<int> a( N );
    
    double ans = 0;
    REP( i, N ){
        cin >> a[i];
        ans += 1 / (double)a[i];
    }

    printf( "%.5f\n", 1 / ans );

}

Measured memory_bytes: 256
from datetime import date
while 1:
    m, d = map(int, raw_input().split())
    if m == d == 0: break
    ans = date(2004,m,d).weekday()
    ansday = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
    for i in range(7):
        if ans == i: print ansday[i]

Measured memory_bytes: 6504
#include <stdio.h>
  
int main(void){
	int h,w,i,j;
	while(1){
		scanf("%d %d", &h, &w);
		if(h == 0 && w == 0)	break;
		for(i = 0; i < h; i++){
			for(j = 0; j < w; j++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
return 0;
}

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

using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    int l=a[a.size()-1]; //left
    int r=l;             // right
    int i=0,j=a.size()-2;
    long long int sum=0;
    while(i<j){
        int li=abs(l-a[i]),ri=abs(r-a[i]);
        int lj=abs(l-a[j]),rj=abs(r-a[j]);
        if(li>ri||lj>rj){ //left side
            if(li>lj){
                sum+=li;
                l=a[i++];
            }else{
                sum+=lj;
                l=a[j--];
            }
        }else{
            if(ri>rj){
                sum+=ri;
                r=a[i++];
            }else{
                sum+=rj;
                r=a[j--];
            }
        }
        //cout<<l<<"---"<<r<<"------"<<i<<"---"<<j<<"----------"<<sum<<endl;
    }
    sum+=max(abs(l-a[i]),abs(r-a[i]));
    cout<<sum<<endl;
}

Measured memory_bytes: 768
/* @ by batr (T) 
   Codeforces Round #597 (Div. 2)
   01.11.19
   
*/
#include <bits/stdc++.h>
 
#define ll long long
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
 
#define cmp_all(X) (X).begin(), (X).end(), cmp
 
#define rB rbegin()
#define B begin()
#define E end()
#define sz size()
#define skip continue
 
#define ppi pair<pair<int, int>, int>
#define pii pair<int, int> 
#define pli pair<ll, int>
#define pcc pair<char, char>
 
#define F first
#define S second

using namespace std;
 
const int maxn = 1e5 + 17;
const int MAXN = maxn * 4;
const int darr = 1e3 + 17;
const ll INF = 1e17 + 5;
const int mod = 1e9 + 7;
 
void Need_For_Speed () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int a, b;

int main () {
	Need_For_Speed();
	cin >> a >> b;
	int add = 0;
	if (b > 0) {
		add++;
	}
	if (a >= 0 && b >= 0) {
		if (a <= b) {
			cout << b - a;
		}	
		else {
			cout << a - b + 1 + add;		
		}
		return 0;
	}
    if (a >= 0 && b < 0) {
    	cout << abs(a + b) + 1;
		return 0;
    }
    if (a < 0 && b >= 0) {
    	cout << abs(a + b) + add;    	
    	return 0;
    }
    if (a < 0 && b < 0) {
    	if (a <= b) {
    		cout << b - a;
    	}	
    	else {
			cout << a - b + 2;    		
    	}
    }
	return 0;
}

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

//---main---------------------------------------------
int main(){
    //main
    int X;
    cin >> X;

    if(400<=X && X<600){
        cout << 8 << endl;
    }else if(600<=X && X < 800){
        cout << 7 << endl;
    }else if(800<=X && X < 1000){
        cout << 6 << endl;
    }else if(1000<=X && X < 1200){
        cout << 5 << endl;
    }else if(1200<=X && X < 1400){
        cout << 4 << endl;
    }else if(1400<=X && X < 1600){
        cout << 3 << endl;
    }else if(1600<=X && X < 1800){
        cout << 2 << endl;
    }else if(1800<=X && X < 2000){
        cout << 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3628
import sys


def input():
    return sys.stdin.readline().strip()


N = int(input())
S = []
T = []
for i in range(N):
    s, t = input().split()
    S.append(s)
    T.append(int(t))
X = input()
A = S.index(X)
print(sum(T[A + 1 :]))


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

typedef vector< int >      vi;
typedef vector< vi >       vvi;
typedef pair<int, int>     pi;
typedef vector< pi >       vpi;

typedef long long          ll;
typedef vector<ll>         vl;
typedef vector< vl >      vvl;

const int LARGE_INT = 1000000007;
const ll LARGE_LONG = 1L << 62;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = (int)(a); i < (int)(b); i++)

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int  n, x, next=1, ans=0;
    cin >> n;
    
    REP(i, 0, n) {
        cin >> x;
        if (x == next)  next++;
        else            ans++;
    }
    if (ans == n)  cout << "-1\n";
    else           cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }

#define MAX_V 10

struct edge {
    int to;
    int cost;
};

int V = 10;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(pii(0, s));

    while (!que.empty()) {
        pii p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;

        for (int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(pii(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int h, w; cin >> h >> w;
    rep(i, 10){
        rep(j, 10){
            int cost; cin >> cost;
            if(i == j) continue;
            G[i].push_back(edge{j, cost});
        }
    }
    int to1_cost[10];
    rep(i, 10){
        if(i==1) to1_cost[i] = 0;
        else{
            dijkstra(i);
            to1_cost[i] = d[1];
        }
    }
    
    int sum = 0;
    rep(i, h){
        rep(j, w){
            int num; cin >> num;
            if(num == -1 || num == 1) continue;
            sum += to1_cost[num];
        }
    }
    cout << sum << ln;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,e,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>a>>b>>c>>d>>e>>k;
    if(e-a>k)Cout(":(");
    else Cout("Yay!");
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	var n, l int
	fmt.Scan(&n, &l)

	var arr = make([]string, n, n)

	for i := 0; i < n; i++ {
		arr[i] = nextLine()
	}

	sort.Strings(arr)
	fmt.Println(strings.Join(arr, ""))
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 640
import std.algorithm;
import std.range;
import std.stdio;
import std.math;
import std.array;
import std.string;
import std.conv;

/// 数列の読み込み
auto readNums(T = int)() {
	return readln().chomp.split.map!(to!T).array;
}

/// 数の読み込み
auto readNum(T = int)() {
	return readNums!T.front;
}

/// 指定行数読み込み
auto readRows(size_t rows) {
	return generate(() => readln().chomp).take(rows).array;
}

void main() {
    immutable n = readNum();
    const row1 = readNums();
    const row2 = readNums();
    int candies = 0;
    foreach(i; 0 .. n) {
        candies = max(candies, row1[0 .. i + 1].sum + row2[i .. $].sum);
    }
    writeln(candies);
}

Measured memory_bytes: 256
A = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
B = [int(input()) for _ in range(n)]
# X = list(map(int, input().split()))
# n, k = map(int, input().split())
# p = math.ceil(sum(X)/n)
for i in range(3):
    for j in range(3):
        for k in range(n):
            if A[i][j] == B[k]:
                A[i][j] = 0
judge = False
# 横軸を確認
for i in range(3):
    if A[i][1:] == A[i][:-1]:
        judge = True
# 縦軸を確認
for i in range(3):
    tmp = []
    for j in range(3):
        tmp.append(A[j][i])
    if tmp[1:] == tmp[:-1]:
        judge = True
# 斜めの確認
tmp_2 = []
for i in range(3):
    tmp_2.append(A[i][i])
if tmp_2[1:] == tmp_2[:-1]:
    judge = True
tmp_3 = []
for i in range(3):
    tmp_3.append(A[i][2-i])
if tmp_3[1:] == tmp_3[:-1]:
    judge = True
print("Yes") if judge else print("No")


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

int N,arr[100000];
int main(){
  cin >> N;
  for (int i=0; i<N; i++){
    cin >> arr[i];
  }
  int greatest=arr[0];
  for (int i=1; i<N; i++){
    if (arr[i] > greatest){
      greatest = arr[i];
    }
    else if (arr[i] < greatest-1){
      cout << "No";
      return 0; //terminate
    }
  }
  cout << "Yes";
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
#define ff first
#define ss second
#define MAX 333
#define endl '\n'
#define boost ios_base::sync_with_stdio(0);cin.tie(0)
const int inf=1e15;

int32_t main()
{
    boost;
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt","r",stdin);
    //     freopen("output.txt","w",stdout);
    // #endif // ONLINE_JUDGE

    int n;
    cin>>n;
    string s;
    cin>>s;
    char a[26];
    for(int i=0;i<26;i++)
        a[i]='A'+i;

    for(int i=0;i<s.size();i++)
        cout<<a[(s[i]-'A'+n)%26];
    cout<<endl;
}


Measured memory_bytes: 256
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


# Code

n = intput()

x = round(n / 1.08)


for t in range(x - 1000, x + 1000):
    if int(t * 1.08) == n and t > 0:
        print(t)
        break
else:
    print(":(")


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

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<

template<class T> bool ckmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool ckmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

int main() { FAST
    ll n, x, t;
    cin >> n >> x >> t;
    ll val = n/x;
    if(n%x != 0) val++;
    cout << val*t << "\n";
}



Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/







int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    if (N <= 999) cout << "ABC" << endl;
    else cout << "ABD" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include<algorithm> 
#include <iomanip>
#define PI 3.14159265359

using namespace std;

int main(){
double r;
cin>>r;
double men,syuu;
men=r*r*PI;
syuu=r*2*PI;
cout<<fixed<<setprecision(5)<<men<<" "<<syuu<<endl;

}


Measured memory_bytes: 3284
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
A = [input() for _ in range(H)]

count = [[0]*W for _ in range(H)]
q = deque([])

for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			q.append((i, j))
# print(q)

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while len(q) >= 1:
	i, j = q.popleft()
	# print(i, j)
	for x, y in zip(dx, dy):
		ny = i + y
		nx = j + x
		if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "#":
			count[ny][nx] = count[i][j] + 1
			q.append((ny, nx))

ans = 0
for i in range(H):
	ans = max(ans, max(count[i]))
# print(count)
print(ans)


Measured memory_bytes: 107736
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    int n,t;
    cin >> n >> t;
    ll time = 0;
    ll sum = 0;
    rep(i,n){
        int a;
        cin >> a;
        if(time + t <= a){
            sum += t;//前のやつについて
            time = a;
        }else{
            sum += a - time;
            time = a;
        }
    }
    sum += t;
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;
typedef long long  ll;

int main() {
	ll N;
	cin >> N;
	vector<pair<ll, ll>> task(N);
	for (ll i = 0; i < N; i++)
	{
		cin >> task[i].second >> task[i].first;
	}
	sort(task.begin(), task.end());
	ll accum = 0, ntime = 0;
	for (ll i = 0; i < N; i++)
	{
		if (task[i].first != ntime) {
			if (accum > ntime) {
				cout << "No" << endl;
				return 0;
			}
			ntime = task[i].first;
			accum += task[i].second;
		}
		else {
			accum += task[i].second;
		}
	}
	if (accum > ntime) {
		cout << "No" << endl;
		return 0;
	}

	cout << "Yes" << endl;

	return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

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

vpll G[200100];
ll dist[200100];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m,s,t; cin>>n>>m>>s>>t;
  s--,t--;
  rep(i,m){
    ll u,v,a,b; cin>>u>>v>>a>>b; u--,v--;
    G[u].emplace_back(v,a);
    G[v].emplace_back(u,a);
    ll nu=n+u, nv=n+v;
    G[nu].emplace_back(nv,b);
    G[nv].emplace_back(nu,b);
  }
  
  priority_queue<pll, vector<pll>, greater<pll>> q;
  q.emplace(0,s);
  q.emplace(0,t+n);
  fill(dist,dist+2*n+1,LINF);
  dist[s]=dist[t+n]=0;
  
  while(!q.empty()){
    auto p=q.top(); q.pop();
    ll v=p.second, c=p.first;
    if(dist[v]<c) continue;
    for(auto np: G[v]){
      ll nv=np.first, nc=np.second;
      if(chmin(dist[nv],dist[v]+nc)){
        q.emplace(dist[nv],nv);
      }
    }
  }
  
  ll base=1e15;
  ll prev=0;
  vll ans(n);
  rrep(i,n){
    chmax(prev,base-(dist[i]+dist[n+i]));
    ans[i]=prev;
  }
  rep(i,n){
    cout<<ans[i]<<endl;
  }
  
}


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

int dp1[502][2][10][500][3], dp2[502][2][10][500][3], m, len[2];
char S[2][550];

void solve(int dp[][2][10][500][3], int o) {
	dp[0][0][0][0][0] = 1;
	rep(i, len[o])rep(j, 2)rep(k, 10)rep(l, m)rep(d, 3) {
		int s, g, p = S[o][i] - '0';
		if (d == 1) { s = k + 1; g = (j ? 9 : p); }
		else if (d == 2) { s = 0; g = (j ? k - 1 : min(k - 1, p)); }
		else { s = 0; g = (j ? 9 : p); }
		for (int x = s; x <= g; x++) {
			if (x&&k == x)continue;
			int y;
			if (d == 1)y = 2;
			else if (d == 2)y = 1;
			else {
				if (k == 0)y = 0;
				else if (x < k)y = 1;
				else y = 2;
			}
			(dp[i + 1][j || x < p][x][(l * 10 + x) % m][y] += dp[i][j][k][l][d]) %= MOD;
		}
	}
}
int main() {
	scanf("%s%s%d", S[0], S[1], &m);
	rep(i, 2)len[i] = strlen(S[i]);
	int d = len[0] - 1;
	while (S[0][d] == '0') {
		S[0][d] = '9'; d--;
	}
	S[0][d]--;
	solve(dp1, 0); solve(dp2, 1);
	int sum1 = 0, sum2 = 0;
	rep(i, 2)rep(j, 10)rep(t, 3) {
		(sum1 += dp1[len[0]][i][j][0][t]) %= MOD;
		(sum2 += dp2[len[1]][i][j][0][t]) %= MOD;
	}
	printf("%d\n", (sum2 + MOD - sum1) % MOD);
}

Measured memory_bytes: 73960
#abc085_C - Otoshidama
N, Y = list(map(int,input().split()))
ans = []
count = 0
if 1000*N <= Y <= 10000*N:
    for x in range(N+1):
        if count == 1:
            break
        for y in range(N+1-x):
            if 10000*x + 5000*y + 1000*(N-x-y) == Y:
                print(x,y,N-x-y)
                count = 1
                break
if count == 0:
    print(-1,-1, -1)

Measured memory_bytes: 3064
a = int(input())
l = [a,a]
n = 1
end = 0
tmp = 0
while end == 0:
    if l[n] % 2 == 0:
        tmp = int(l[n]/2)
    else:
        tmp = int(l[n]*3 + 1)
    n = n + 1
    if tmp in (l):
        end = 1
    l.append(tmp)

print(n)


Measured memory_bytes: 3060
N = int(input())
a = list(map(int, input().split()))
for i in range(N):
	a.append(a[i] - 1)
	a.append(a[i] + 1)

import collections
a_c=collections.Counter(a)


s_val, s_count=zip(*a_c.most_common())

print(max(s_count))

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

int main(){
   int n,k;
   cin >> n >> k;   
   vector<long long> h(1000000);
    long long sum = 0;
    for (int i = 0;i < n;i++){
        cin >> h.at(i);
        sum += h.at(i);
    }

   sort(h.begin(),h.end(),greater<long long>());

    for (int i = 0;i < k;i++){
        sum -= h.at(i);
    }
    cout << sum << endl;
}

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

c0=0
c1=0
c2=0
c3=0

for i in range(n):
    s=input()
    if s=='AC':
        c0+=1
    elif s == 'WA':
        c1+=1
    elif s== 'TLE':
        c2+=1
    else:
        c3+=1

print('AC x '+str(c0))
print('WA x '+str(c1))
print('TLE x '+str(c2))
print('RE x '+str(c3))

Measured memory_bytes: 9092
N,M,Q = map(int,input().split())
lis = []
i = 0
ai,bi,dist,poin = [],[],[],[]
while True:
    try:
        lis.append(list(map(int,input().split())))
        ai.append(lis[i][0])
        bi.append(lis[i][1])
        dist.append(lis[i][2])
        poin.append(lis[i][3])
        i+=1

    except:
        break;
        #または、quit(),os.exit()をして止める。
#print(bi)
        
def point(num):
  tok = 0
  for i in range(Q):
    #print('A(='+str(num[ai[i]-1])+') - B(='+str(num[bi[i]-1])+') = dist(='+str(dist[i]))
    if(num[bi[i]-1] - num[ai[i]-1] == dist[i]):
      tok += poin[i]
  return tok

#per = [M**i for i in range(1,N+1)].sort()

def UpdateA(num):
  NewA = num
  flag = 0
  i = N-1
  while(flag == 0 and i >= 0):
    NewA[i] += 1
    if(NewA[i] > M):
      i -= 1
      continue
    else:
      j=i+1
      while(j<N):
        NewA[j] = NewA[j-1]
        j+=1
      flag = 1
  #print('NewA - '+str(NewA))
  return NewA
  
maxi = 0
A = [1 for i in range(N)]
while(1):
  thisp = point(A)
  #print('this p = '+str(thisp))
  if(thisp > maxi):
    maxi = thisp
    #print('maxi - '+str(maxi))
    if(maxi == sum(poin)):
      break
  A = UpdateA(A)
  if(sum(A) > N*M):
    break

print(maxi)
  

Measured memory_bytes: 69072
#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>
using namespace std;

#define LL long long int
#define uLL unsigned long long int

#define S(a) scanf("%d",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define S3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define SLL(a) scanf("%lld",&a)
#define SLL2(a,b) scanf("%lld%lld",&a,&b)
#define SLL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define SC(a) scanf("%c",&a)
#define P(a) printf("%d",a)
#define PS(a) printf("%s",a)
#define PLL(a) printf("%lld",a)
#define PCASE(kk) printf("Case %d: ",kk++)
#define PCASENL(kk) printf("Case %d:\n",kk++)
#define NL puts("")

#define pb push_back
#define mp(a,b) make_pair(a,b)
#define pi (2.0*acos(0.0))
#define pii pair<int,int>

template<typename T>inline T POW(T B,T P)
{
    if(P==0) return 1;
    if(P&1) return B*POW(B,P-1);
    else return SQR(POW(B,P/2));
}
template <typename T>inline T ModInv (T b,T m)
{
    return BigMod(b,m-2,m);
}
template<typename T>inline T ABS(T a)
{
    if(a<0)return -a;
    else return a;
}
template<typename T>inline T gcd(T a,T b)
{
    if(a<0)return gcd(-a,b);
    if(b<0)return gcd(a,-b);
    return (b==0)?a:gcd(b,a%b);
}
template<typename T>inline T lcm(T a,T b)
{
    if(a<0)return lcm(-a,b);
    if(b<0)return lcm(a,-b);
    return a*(b/gcd(a,b));
}
template <class T> inline T BMOD(T p,T e,T m)
{
    T ret=1;
    while(e)
    {
        if(e&1) ret=(ret*p)%m;
        p=(p*p)%m;
        e>>=1;
    }
    return (T)ret;
}

//for(__typeof(pp.begin()) i=pp.begin(); i!=pp.end(); i++ )

//knight and king move....



//int Dx[]={-2,-1,1,2,1,2,-2,-1};
//int Dy[]={-1,-2,2,1,-2,-1,1,2};
//int dx[]={-1,1,0,0};
//int dy[]={0,0,-1,1};
//int dx[]= {-1,-1,0,0,1,1};
//int dy[]= {-1,0,-1,1,0,1};
//////////////////////////////////////////////////

int main()
{
    LL n,x;
    SLL2(n,x);

    LL ds=(n-(2*x));

    if(ds==0)
    {
        PLL((x*3LL)),NL;
    }
    else if(ds>0)
    {
        LL ans;

        ans=3LL*x+(n-x);
        LL l=x,w=ds;
        if(l<w)swap(l,w);
        while(1)
        {
            if(l%w==0)
            {
                ans+=((2LL*(l/w))-1)*w;
                break;
            }
            ans+=(2LL*(l/w))*w;
//            l=l-((2LL*(l/w))*w);
            l%=w;
            if(l==0)break;
            if(l<w)swap(l,w);

        }
        PLL(ans),NL;
    }
    else
    {
        ds=n-x;
        LL ans=x+ds;
        LL l=x,w=ds;
        if(l<w)swap(l,w);
        while(1)
        {
            if(l%w==0)
            {
                ans+=((2LL*(l/w))-1)*w;
                break;
            }
            ans+=(2LL*(l/w))*w;
//            l=l-((2LL*(l/w))*w);
            l%=w;
            if(l==0)break;
            if(l<w)swap(l,w);

        }
        PLL(ans),NL;
    }



    return 0;
}


Measured memory_bytes: 384
n = int(input())
a = list(map(int, input().split()))

p = set()
q = 0
for i in range(n):
  if a[i] < 3200:
    p.add(a[i]//400)
  else:
    q += 1

p = len(p)
print(max(p, 1), p+q)

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

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a.at(i);
    }

    unordered_map<int, int> x;
    for (int i = 0; i < N; i++) {
        if (x.count(a.at(i))) {
            x.at(a.at(i))++;
        } else {
            x[a.at(i)] = 1;
        }
    }

    int good = 0;
    for (auto itr = x.begin(); itr != x.end(); itr++) {
        if ((*itr).first <= (*itr).second) {
            good += (*itr).second - (*itr).first;
        } else {
            good += (*itr).second;
        }
    }

    cout << good << endl;
}

Measured memory_bytes: 4644
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define nl '\n'
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define dcit cin.sync_with_stdio(0);cin.tie(0);
#define frp(x, y) freopen(x, "r", stdin);freopen(y, "w", stdout);
typedef pair<int, int> pii;
typedef long long ll;

#ifdef LOCAL_PROJECT

#define gc getchar()
#define pc(x) putchar(x)

#endif
#ifndef LOCAL_PROJECT

#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)

#endif

template<typename T> void scani(T &x) {x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printi(T n) {register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);pc(10);}
string nextstring() { string r; register char c=gc;while(c==32||c==10) c = gc;while(!(c==32||c==10)) { r += c;c = gc; }return r; }
char nextgetchar(){ register char c = gc; while(c==32 || c==10) c = gc; return c;}

void prints(string k){ for (int i = 0; i < k.length(); i++)pc(k[i]); }
void scani() {}

template<typename First, typename ... Ints>
void scani(First &arg, Ints&... rest) { scani(arg);scani(rest...); }

int N, K, a[100002], dp[100002];
int fun(int idx){
    if(idx<=0) return 9999999999;
    if(dp[idx]!=-1) return dp[idx];
    int ans = 9999999999;
    for (int i = 1; i <= K; i++) {
        if((idx-i)>=1)ans = min(ans, fun(idx-i)+abs(a[idx]-a[idx-i]));
        else break;
    }
    return dp[idx]=ans;
}

int main(){
    memset(dp, -1, sizeof dp); dp[1] = 0;
    scani(N, K);
    for (int i = 1; i <= N; i++)scani(a[i]);
    printi(fun(N));
    return 0;
}


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

//素因数分解 {素数、何乗}の配列、1のときは要素なしの配列
vector<pair<int,int>> primefact(ll N){
    vector<pair<int,int>> ans(0);
    ll a=2;
    while(N>=a*a){
        if(N%a==0){
            ans.push_back({a,0});
            ll A=ans.size()-1;
            while(N%a==0){
                ans.at(A).second++;
                N/=a;
            }
        }
        a++;
    }
    if(N>1)ans.push_back({N,1});
    return ans;
}

int main() {
    ll A,B;
    cin>>A>>B;
    vector<P> AP=primefact(A),BP=primefact(B);
    ll a=0,b=0;
    ll ans=1;
    while(a<sz(AP) && b<sz(BP)){
        if(AP.at(a).first==BP.at(b).first){
            ans++;a++;b++;
        }
        else if(AP.at(a).first>BP.at(b).first){b++;}
        else{a++;}
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <vector>

constexpr int prime[] = {2,  3,  5,  7,  11, 13,  17,  19, 23, 29,
                         31, 37, 41, 43, 47, 53,  59,  61, 67, 71,
                         73, 79, 83, 89, 97, 101, 103, 107};

constexpr size_t alphabet = 26;
constexpr size_t str_len = 10;

inline int64_t hash(std::string &str) {
  int64_t result = 1;

  for (size_t i = 0; i < str_len; ++i) {
    result *= prime[str[i] - 'a'];
  }

  return result;
}

inline int64_t hash(char *str, int start, int end) {
  int64_t result = 1;

  for (size_t i = start; i < end; ++i) {
    result *= prime[str[i] - 'a'];
  }

  return result;
}

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

  char input[100000 * 11 + 5];

  fread(input, sizeof(char), sizeof(char) * 11 * n, stdin);

  std::vector<int64_t> sn(n);

  for (int i = 0; i < n; ++i) {
    sn[i] = hash(input, i * 11 + 1, i * 11 + 10 + 1);
  }

  std::sort(sn.begin(), sn.end());

  int64_t count = 0;
  int64_t local_count = 0;
  for (int i = 1; i < n; ++i) {
    if (sn[i - 1] == sn[i]) {
      count += (++local_count);
    } else {
      local_count = 0;
    }
  }

  printf("%ld\n", count);

  return 0;
}

Measured memory_bytes: 2048
#include <stdio.h>

#define INF 1000000

int w,h;
char map[20][24];
int rinsetu[400][400];

int yogore_num;
int yogore[11][2];
int sx,sy;

int getid(int y,int x) {
	return y*w+x;
}

/* [rest_yogore][now_pos] */
int memo[1024][11];

int tansaku(int rest_yogore,int now_pos) {
	int result=INF;
	int i;
	if(rest_yogore==0)return 0;
	if(memo[rest_yogore][now_pos]>0)return memo[rest_yogore][now_pos]-1;
	for(i=0;i<yogore_num;i++) {
		if(rest_yogore & (1<<i)) {
			int nowresult;
			nowresult=tansaku(rest_yogore & ~(1<<i),i);
			nowresult+=rinsetu[getid(yogore[now_pos][1],yogore[now_pos][0])]
				[getid(yogore[i][1],yogore[i][0])];
			if(nowresult<result)result=nowresult;
		}
	}
	memo[rest_yogore][now_pos]=result+1;
	return result;
}

int main(void) {
	while(scanf("%d%d",&w,&h)==2 && (w|h)!=0) {
		int i,j,k;
		int result;
		for(i=0;i<h;i++)scanf("%s",map[i]);
		for(i=0;i<getid(h,0);i++) {
			for(j=0;j<getid(h,0);j++) {
				rinsetu[i][j]=(i==j?0:INF);
			}
		}
		for(i=0;i<1024;i++) {
			for(j=0;j<11;j++)memo[i][j]=0;
		}
		yogore_num=0;
		for(i=0;i<h;i++) {
			for(j=0;j<w;j++) {
				if(map[i][j]!='x') {
					if(i+1<h && map[i+1][j]!='x') {
						rinsetu[getid(i,j)][getid(i+1,j)]=1;
						rinsetu[getid(i+1,j)][getid(i,j)]=1;
					}
					if(j+1<w && map[i][j+1]!='x') {
						rinsetu[getid(i,j)][getid(i,j+1)]=1;
						rinsetu[getid(i,j+1)][getid(i,j)]=1;
					}
					if(map[i][j]=='o') {
						sx=j;sy=i;
					} else if(map[i][j]=='*') {
						yogore[yogore_num][0]=j;
						yogore[yogore_num][1]=i;
						yogore_num++;
					}
				}
			}
		}
		for(k=0;k<getid(h,0);k++) {
			for(i=0;i<getid(h,0);i++) {
				for(j=0;j<getid(h,0);j++) {
					if(rinsetu[i][j]>rinsetu[i][k]+rinsetu[k][j]) {
						rinsetu[i][j]=rinsetu[i][k]+rinsetu[k][j];
					}
				}
			}
		}
		yogore[yogore_num][0]=sx;
		yogore[yogore_num][1]=sy;
		result=tansaku((1<<yogore_num)-1,yogore_num);
		printf("%d\n",result<INF?result:-1);
	}
	return 0;
}

Measured memory_bytes: 1244
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  int n;
  cin>>n;
  vl a(n);
  rep(i,n)cin>>a[i];

  ll x = a[0];
  ll ans = 0,res;
  if(x<0){
    ans+=abs(x)+1;
    x=1;
  }
  if(x==0){
    ans++;
    x++;
  }
  srep(i,1,n){
    // show(a[i]);
    // show(x);
    if(x>0 && x+a[i]>0){
      ans+=x+a[i]+1;
      x=-1;
    }
    else if(x<0&&x+a[i]<0){
      ans+=abs(x+a[i])+1;
      x=1;
    }
    else{
      if(x>0){
        x=x+a[i];
        ans+=(x==0);
        x-=(x==0);
      }else{
        x=x+a[i];
        ans+=(x==0);
        x+=(x==0);
      }
      
    }
  }
  res = ans;

  x = a[0];
  ans = 0;
  if(x>0){
    ans+=x+1;
    x=-1;
  }
  if(x==0){
    ans++;
    x--;
  }
  srep(i,1,n){
    // show(a[i]);
    // show(x);
    if(x>0 && x+a[i]>0){
      ans+=x+a[i]+1;
      x=-1;
    }
    else if(x<0&&x+a[i]<0){
      ans+=abs(x+a[i])+1;
      x=1;
    }
    else{
      if(x>0){
        x=x+a[i];
        ans+=(x==0);
        x-=(x==0);
      }else{
        x=x+a[i];
        ans+=(x==0);
        x+=(x==0);
      }
      
    }
  }
  mins(res,ans);
  print(res);
  return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"

typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))
#define min3(x, y, z) min(x, min(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif

using namespace std;
int main() {
  int N;
  cin >> N;
  string tmp;
  map<string,int> list;
  int pm = 0;
  rep(i, N) {
    cin >> tmp;
    list[tmp]++;
    pm = max(list[tmp],pm);
  }
  for (auto itr = list.begin(); itr != list.end(); itr++) {
    if (itr->second == pm) {
      cout << itr->first << endl;
    }          
  }
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
rep(i,N) {
  cin >> list[i];
}
//配列(スタックとしても使える)
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
//ソート クイックだからO(NlogN)
sort(all(list));
sort(all(list), greater<int>());

//配列の内容表示
dout << "====listの内容====\n";
for (int edp = 0; edp < N; edp++) dout << list[edp] << endl;
dout << "====ここまで====\n";


//配列の最小最大(Nは要素数)
*min_element(all(c))
*max_element(all(c))

//a[0]からa[N]を逆順にする(計算量はO(N))
reverse(all(a));
//listの末尾に要素を追加
list.push_back(10);
//listの末尾から要素を削除
list.pop_back();
//空ですか？
list.empty()



//キュー(待ち行列)
//定義
queue<int> a;
//追加
a.push(x);
//取る
a.pop();
//チェック
a.front()
//サイズ
a.size()
//空ですか
a.empty()



//優先度付きキュー※全部計算量がO(NlogN)あるので注意
// int 型の要素を持ち、最も小さい値を取り出す形の priority_queue を定義
priority_queue<int, vector<int>, greater<int>> Q1;
// double 型の要素を持ち、最も大きい値を取り出す形の priority_queueを定義
priority_queue<double, vector<double>, less<double>> Q2;
//追加
a.push(x);
//取る
a.pop();
//一番小さいの教えて下さい
a.top()
//サイズ
a.size()
//空ですか
a.empty()



//部分文字列
//添字3から5文字
s.substr(3,5)
//添字3から全部
s.substr(3)

//入れ替え
swap(a,b);



// int 型の番地に string 型の変数を記録する場合（2^31 要素の string型配列と同じような感じ）
map<int, string> hoge; for (auto itr =
list.begin(); itr != list.end(); itr++) {
    //順番にマップを眺める。itr->firstでキー、itr->secondがバリュー
}

//ソート済みのaの中で初めてx以上になるインデックスを返す
lower_bound(all(a), x) - a

*/


Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int N;
    cin >> N;
    vint b(N);
    for (int i = 0; i < N; i++)
    {
        cin >> b[i];
        b[i]--;
    }
    vint ans;
    while (ans.size() < N)
    {
        for (int i = b.size() - 1; i >= 0; i--)
        {
            if (b[i] == i)
            {
                b.erase(b.begin() + i);
                ans.push_back(i + 1);
                goto L;
            }
        }
        cout << -1 << endl;
        return 0;
    L:;
    }
    reverse(all(ans));
    for (auto &&i : ans)
    {
        cout << i << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
using namespace std;
typedef pair<int,int> P;//Pでpair<-,->を表す。
typedef long long LL; 



int main()
{ 
    int n;
    cin>>n;
    LL a[n];
    int ans=0;
    vector<LL> v;
    for(int i=0;i<n;i++){cin>>a[i];}
    for(int i=0;i<n;i++){
        if(v.empty()){ans++;v.push_back(a[i]);}
        else{
            LL x=v.back();
            if(x<a[i]){
                //二分探査
                int val_min=0;
                int val_max=v.size()-1;
                while(val_min!=val_max&&(val_min+1)!=val_max){
                    int val=(val_min+val_max)/2;
                    if(v[val]<a[i]){val_max=val;}
                    else{val_min=val;}
                }
                if(val_min==val_max){v[val_min]=a[i];}
                else{
                    if(v[val_min]<a[i]){v[val_min]=a[i];}
                    else{v[val_max]=a[i];}
                }
            }
            else{
                ans++;
                v.push_back(a[i]);
            }
        }
        /*cout<<i<<' ';
        for(int j=0;j<v.size();j++){
            cout<<v[j]<<' ';
        }
        cout<<endl;*/
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2168
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: usize = s.next().unwrap().parse().unwrap();
	let m: usize = s.next().unwrap().parse().unwrap();
	let info: Vec<_> = (0..m)
		.map(|_| {
			let a: usize = s.next().unwrap().parse().unwrap();
			let b: usize = s.next().unwrap().parse().unwrap();
			(a - 1, b - 1)
		})
		.collect();
	let mut uf = UnionFind::new(n);
	let n = n as i64;
	let mut ans = vec![n * (n - 1) / 2];
	for (a, b) in info.into_iter().rev().take(m - 1) {
		let s = uf.size(a) as i64;
		let t = uf.size(b) as i64;
		let x = if uf.find(a) != uf.find(b) {
			ans.last().unwrap() - s * t
		} else {
			ans.last().unwrap().clone()
		};
		uf.unite(a, b);
		ans.push(x);
	}
	use std::io::Write;
	let out = std::io::stdout();
	let mut out = out.lock();
	for ans in ans.into_iter().rev() {
		writeln!(out, "{}", ans).unwrap();
	}
}

pub struct UnionFind {
	data: Vec<i32>,
}

impl UnionFind {
	pub fn new(n: usize) -> UnionFind {
		UnionFind { data: vec![-1; n] }
	}

	pub fn unite(&mut self, x: usize, y: usize) -> bool {
		let x = self.find(x);
		let y = self.find(y);
		if x == y {
			false
		} else {
			let (x, y) = if self.data[x] > self.data[y] {
				(y, x)
			} else {
				(x, y)
			};
			self.data[x] += self.data[y];
			self.data[y] = x as i32;
			true
		}
	}

	pub fn find(&mut self, i: usize) -> usize {
		if self.data[i] < 0 {
			i
		} else {
			let p = self.data[i] as usize;
			self.data[i] = self.find(p) as i32;
			self.data[i] as usize
		}
	}

	pub fn size(&mut self, i: usize) -> usize {
		let i = self.find(i);
		(-self.data[i]) as usize
	}
}


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

int main() {
    int n; cin >> n;
    int r = n % 10;
    if (r == 3) {
        cout << "bon" << endl;
    } else if (r == 0 || r == 1 || r == 6 || r == 8) {
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3584