akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int maxm(int a, int b, int c)
{
	return max(a,max(b,c));
}
int main()
{
	int n;
	cin>>n;
    int a[n],b[n],c[n];
    for(int i=0;i<n;i++)
    {
    cin>>a[i]>>b[i]>>c[i];	
    }
    int dp[3][n+1];
    memset(dp,0,sizeof dp);
    for(int j=1;j<=n;j++)
    {
    dp[0][j]=max(b[j-1]+dp[1][j-1],c[j-1]+dp[2][j-1]);
    dp[1][j]=max(a[j-1]+dp[0][j-1],c[j-1]+dp[2][j-1]);
    dp[2][j]=max(a[j-1]+dp[0][j-1],b[j-1]+dp[1][j-1]);
    }
    int ans=maxm(dp[0][n],dp[1][n],dp[2][n]);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 5912
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
using ll = long long;

using namespace std;


int u_find(int x, vector<int> &par) {
    if(par[x] == x) return x;
    else return u_find(par[x],par);
}

void unite(int x, int y, vector<int> &par, vector<int> &rank) {
    x = u_find(x,par);
    y = u_find(y,par);
    if(x == y) return;
    if(rank[x] < rank[y]) {
        par[x] = y;
        rank[y] += rank[x];
    }
    else {
        par[y] = x;
        rank[x] += rank[y];
    }
}

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> p(n+1);
    vector<int> r(n+1,1);
    rrep(i,n) {
        p[i] = i;
    }
    int ans = 0;
    rep(i,m) {
        int a,b;
        cin >> a >> b;
        unite(a,b,p,r);
    }
    rep(i,n) {
        ans = max(ans, r[u_find(i,p)]);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4748
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;

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

    int taro = 0, hanako = 0;

    for (size_t i = 0; i < n; i++) {
        string t, h;
        cin >> t >> h;

        if (t == h) {
            taro++;
            hanako++;
        } else if (t > h) {
            taro += 3;
        } else {
            hanako += 3;
        }
    }

    printf("%d %d\n", taro, hanako);
}



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

#define rep(i, n) for (int i = 0; i < (int)(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;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
    ll n;
    cin >> n;
    cout << (ll)pow(n, 3) << endl;
}


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

int main(void){
  string s, left;
  int pos, tmp, cnt, i;
  left = "qwertasdfgzxcvb";
  while(1){
    cin >> s;
    if(s == "#"){
      break;
    }
    if(left.find(s[0]) != std::string::npos){
      pos = 0;
    }else{
      pos = 1;
    }
    cnt = 0;
    for(i=1;i<s.length();i++){
      if(left.find(s[i]) != std::string::npos){
        tmp = 0;
      }else{
        tmp = 1;
      }
      if(pos != tmp){
        cnt++;
        pos = tmp;
      }
    }
    cout << cnt << endl;
  }
  return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    int N;
    cin >> N;
    vector<double> v(N);
    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }
    sort(ALL(v));
    double ans = (v[0] + v[1]) / 2.0;
    for (int i = 2; i < N; i++) {
        ans = (ans + v[i]) / 2.0;
    }

    printf("%32.18f\n", ans);

}

Measured memory_bytes: 3744
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
  int n,cnt[3]={};
  long a;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%ld",&a);
    if(a%4==0)
      cnt[0]++;
    else if(a%4==2)
      cnt[2]++;
    else
      cnt[1]++;
  }
  if(cnt[0]>=cnt[1]||(cnt[2]==0&&cnt[0]+1>=cnt[1]))
    printf("Yes\n");
  else
    printf("No\n");
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-
from sys import stdin

while True:
  s = stdin.readline().rstrip()
  if s == 'END OF INPUT':
    break
  ans = ''
  cnt = 0
  for i in s:
    if i == ' ':
      ans += str(cnt)
      cnt = 0
    else:
      cnt += 1
  ans += str(cnt)
  print(ans)


Measured memory_bytes: 5556
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long double p = 3.14159265359;
    long long  n,m;
    cin>>n;
    long long a[n];
    map<long long,long long > sum ;
    for(int i=0;i<n-1;i++){
        cin>>a[i];
        sum[a[i]]++;
    }
    for(int i=1;i<=n;i++){

       cout<<sum[i]<<"\n";
    }
    }



Measured memory_bytes: 17660
#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 rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int N;
    cin >> N;
    int ans = inf;
    rep2(i, 0, N){
        int x = i, y = N-i, sum = 0;
        while(x > 0){
            sum += x%6;
            x /= 6;
        }
        while(y > 0){
            sum += y%9;
            y /= 9;
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <cmath>
#include <cassert>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>

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

using namespace std;

typedef long long int64;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int64 X = 2184057LL;

int main() {
  int n;
  string s;
  cin >> n >> s;
  unordered_map<int64, int> left;
  vector<int64> p(2 * n + 2);
  p[0] = 1;
  for (int i = 1; i < sz(p); ++i)
    p[i] = p[i - 1] * X;
  for (int mask = 0; mask < (1 << n); ++mask) {
    int64 h1 = 0, h2 = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if ((mask >> i) % 2)
        h1 = h1 * X + s[i];
      else
        h2 += p[cnt++] * s[i];
    }
    int64 h = h1 * 98729321 + h2;
    left[h]++;
  }

  int64 res = 0;
  for (int mask = 0; mask < (1 << n); ++mask) {
    int64 h1 = 0, h2 = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if ((mask >> i) % 2)
        h2 = h2 * X + s[n + i];
      else
        h1 += p[cnt++] * s[n + i];
    }
    int64 h = h1 * 98729321 + h2;
    if (left.count(h))
      res += left[h];
  }
  cout << res << "\n";
  return 0;
}

Measured memory_bytes: 14280
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

typedef pair<int, int> P;

int main() {
  int n; cin >> n;
  vector<int> A(n), B;
  loop(i,0,n) cin >> A[i];
  int sum = 0;
  loop(i,0,n) {
    sum += A[i];
    if (A[i]%10 != 0) B.push_back(A[i]);
  }
  
  if (sum % 10 != 0) {
    cout << sum << endl;
    return 0;
  }
  
  if (B.size() == 0) {
    cout << 0 << endl;
    return 0;
  }
  
  sort(B.begin(), B.end());
  cout << sum - B[0] << endl;
  return 0;
}


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

using namespace std;

struct data {
  data *prev,*next;
  int key;
};

data *root;

void init() {
  root=(data*)malloc(sizeof(data));
  root->next=root;
  root->prev=root;
}
void insert(int k) {
  data *tmp=(data*)malloc(sizeof(data));
  tmp->prev=root; tmp->next=root->next; tmp->key=k;
  root->next->prev=tmp;
  root->next=tmp;
}
void Delete(int k) {
  for(data *p=root->next;p!=root;p=p->next) {
    if(p->key==k) {
      p->prev->next=p->next;
      p->next->prev=p->prev;
      break;
    }
  }
}
void deleteFirst() {
  root->next=root->next->next;
  root->next->prev=root;
}
void deleteLast() {
  root->prev=root->prev->prev;
  root->prev->next=root;
}

int main() {
  init();
  int n; cin >> n;
  int x;
  char s[15];
  while(n--) {
    cin >> s;
    if(s[0]=='i') cin >> x,insert(x);
    else if(s[6]=='\0') cin >> x,Delete(x);
    else if(s[6]=='F') deleteFirst();
    else deleteLast();
  }
  for(data *p=root;p->next!=root;p=p->next)
    cout << (p==root?"":" ") << p->next->key;
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 37472
#define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_a_genius = 0; ngtkana_is_a_genius < int(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (int i = int(begin); (i) < int(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  lint t; std::cin >> t;
  std::vector<lint> a(n); std::cin>>a;
  debug(a);
  std::adjacent_difference(all(a), a.begin());
  debug(a);
  lint ans = 0;
  for (lint x : a) {
    ans += std::min(t, x);
  }
  ans += t;
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 1792
import copy as cp

def make_divisors(n):
    divisors = [n]
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

N = int(input())
div1_l = make_divisors(N-1)
count = len(div1_l)

div_l = make_divisors(N)
for d in div_l:
    n = N
    while True:
        if n%d == 0:
            n = n//d
        else:
            if n%d == 1:
                count += 1
            break
if N == 2:
    count = 1

print(count)

Measured memory_bytes: 3864
#140 b
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
for i,x in enumerate(a):
    ans+=b[x-1]
    if i!=n-1 and x+1==a[i+1]:
           ans+=c[x-1]
print(ans)


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

using namespace std;

#define vll vector<long long>
#define ll long long
#define ld long double
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vld vector<long double>
#define vs vector<string>
#define MOD 1000000007
#define endl "\n"
#define vc vector<char>
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define RFOR(i,b,a) for (ll i = (b) - 1; i >= (a); i--)
#define ALL(a) a.begin(), a.end()
#define mp make_pair
#define SZ(a) int((a).size())
#define pi acos(-1.0)
#define F first
#define S second
#define RESET(a, b) memset(a, b, sizeof(a))
#define INF 1000000000000000000
#define PLL pair<long,long>
#define PI pair<int,int>
/*

,--.  ,--. ,--. ,--.                                            ,---.       ,--. ,--.
|  ,'.|  | `--' |  |,-.  ,--.,--.  ,---.  ,--. ,--.  ,--,--.   |  o ,-.     |  .'   /  ,--,--.  ,---.   ,---.   ,--,--.
|  |' '  | ,--. |     /  |  ||  | (  .-'   \  '  /  ' ,-.  |   .'     /_    |  .   '  ' ,-.  | | .-. | | .-. | ' ,-.  |
|  | `   | |  | |  \  \  '  ''  ' .-'  `)   \   '   \ '-'  |   |  o  .__)   |  |\   \ \ '-'  | | '-' ' | '-' ' \ '-'  |
`--'  `--' `--' `--'`--'  `----'  `----'  .-'  /     `--`--'    `---'       `--' '--'  `--`--' |  |-'  |  |-'   `--`--'
                                          `---'                                                `--'    `--'
*/





using namespace std;

int main() {
/*
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
*/
//    ifstream in("ladder.in");
//    cin.rdbuf(in.rdbuf());
//    ofstream out("ladder.out");
//    cout.rdbuf(out.rdbuf());

     ll five=0,seven=0;
     vll num(3);
     FOR(i,0,3) {
         cin >> num[i];
     }
     FOR(i,0,3){
         if(num[i]==5)five++;
         if(num[i]==7)seven++;
     }
     if(five==2 && seven==1)cout<<"YES"<<endl;
     else cout<<"NO"<<endl;




    return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
using graph = vector<vector<ll>>;


int main() {
	string s;
	ll k;
	cin >> k;
	cin >> s;
	if (s.size() <= k) {
		cout << s << endl;
	}
	else {
		for (int i = 0; i < k; i++) {
			cout << s[i] ;
		}
		cout << "..." << endl;
	}
	return 0;
}

Measured memory_bytes: 3628
import sys
input = sys.stdin.readline


def main():
    mod = 10**9 + 7
    n = int(input())
    all = pow(10, n, mod)
    non_0 = non_9 = pow(9, n, mod)
    non_0_and_9 = pow(8, n, mod)
    ans = all - non_0 - non_9 + non_0_and_9
    print(ans % mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9112
import java.util.*;
import java.io.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		int k=sc.nextInt();
		long[][] dp=new long[s.length()][k+1];
		int count=0;
		for(int i=0; i<s.length(); i++){
			if(s.charAt(i)!='0'){
				count++;
			}
			if(i==0){
				dp[0][1]=s.charAt(i)-'0';
			}else{
				dp[i][1]=dp[i-1][1]+9;
				for(int j=2; j<=k; j++){
					if(count==j && s.charAt(i)!='0'){
						dp[i][j]+=(dp[i-1][j-1]-1)*9+dp[i-1][j]+(s.charAt(i)-'0');
					}else if(count+1==j && s.charAt(i)=='0'){
						dp[i][j]+=(dp[i-1][j-1]-1)*9+dp[i-1][j];
					}else{
						dp[i][j]+=dp[i-1][j-1]*9+dp[i-1][j];
					}
				}
			}
		}
		
		System.out.println(dp[s.length()-1][k]);
	}
}


Measured memory_bytes: 21972
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

c=array(3)
3.times do|i|
    c[i]=get_nsp
end
puts c[0][0]+c[1][1]+c[2][2]

Measured memory_bytes: 1788
n=int(input())
s=list(input())
x=int(n/2)
b=[]
ans=[]
if n % 2 == 0: 
    for i in range(x):
       a=s.pop(0) 
       b.append(a)
else:
    ans="No"
if b == s:
    ans="Yes"
else:
    ans="No"
print(ans)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a == 1 ) {
		a = 14;
	}
	if (b == 1) {
		b = 14;
	}
	if (a > b) {
		cout << "Alice";
	}
	else if (b > a) {
		cout<< "Bob";
	}
	else {
		cout << "Draw";
	}
	return 0;
}

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

int dat[2005][2005];
int presum[2005][2005];
int conn[2005][2005];
int consum[2005][2005];

struct query
{
    int x1, y1, x2, y2;
};

query qry[200005];
int ans[200005];

int main()
{
    int n, m, q;
    scanf("%d%d%d",&n,&m,&q);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%1d", &dat[i][j]);

    for (int i = 0; i < q; i++) scanf("%d%d%d%d", &qry[i].x1, &qry[i].y1, &qry[i].x2, &qry[i].y2);

    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1] + dat[i][j];

    for (int i = 0; i < q; i++) ans[i] = presum[qry[i].x2][qry[i].y2] - presum[qry[i].x1-1][qry[i].y2] - presum[qry[i].x2][qry[i].y1-1] + presum[qry[i].x1-1][qry[i].y1-1];

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            conn[i][j] = dat[i][j] & dat[i][j + 1];
        }
    }

    for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++)
        consum[i][j] = consum[i-1][j] + consum[i][j-1] - consum[i-1][j-1] + conn[i][j];

    for (int i = 0; i < q; i++) ans[i] -= consum[qry[i].x2][qry[i].y2-1] - consum[qry[i].x1-1][qry[i].y2-1] - consum[qry[i].x2][qry[i].y1-1] + consum[qry[i].x1-1][qry[i].y1-1];

    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            conn[i][j] = dat[i][j] & dat[i + 1][j];
        }
    }

    for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++)
        consum[i][j] = consum[i-1][j] + consum[i][j-1] - consum[i-1][j-1] + conn[i][j];

    for (int i = 0; i < q; i++) ans[i] -= consum[qry[i].x2-1][qry[i].y2] - consum[qry[i].x1-1][qry[i].y2] - consum[qry[i].x2-1][qry[i].y1-1] + consum[qry[i].x1-1][qry[i].y1-1];

    for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}


Measured memory_bytes: 68480
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define lo long long
using namespace std;
int n,m,x,y,dp[li],mx,vis[li];
vector<int> v[li];
int dfs(int node){
	int cev=-inf;
	vis[node]=1;
	if((int)v[node].size()==0) return 0;
	if(~dp[node]) return dp[node];
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		cev=max(cev,dfs(go)+1);
	}
	return dp[node]=cev;
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		v[x].pb(y);
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0) mx=max(mx,dfs(i));
	}
	printf("%d\n",mx);
	return 0;
}




Measured memory_bytes: 9216
from collections import deque
import sys
import math
import io

    
H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
    grid += '#' + input() + '#'
grid += '#' * (W+2)
move = [1, -1, W+2, -W-2]
    
def bfs(start):
    lst = [10**9] *((H+2)*(W+2))
    lst[start] = 0
    q = deque([start])
    while q:
        x = q.popleft()
        dx = lst[x]
        for d in move:
            y = x + d
            if grid[y] == '#':
                continue
            dy = dx + 1
            if dy >= lst[y]:
                continue
            lst[y] = dy
            q.append(y)
    return max(x for x in lst if x < 10**9)
    
    
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '#'))

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n;
  cin>>n;
  if(n <= 999) cout << "ABC" << endl;
  else cout << "ABD" << endl;

  return 0;
}


Measured memory_bytes: 256
s = [int(i) for i in list(input())]
n = len(s)

a,b = [],[]

for i in range(n):
    if i%2 == 0:
        a.append(0)
        b.append(1)
    else:
        a.append(1)
        b.append(0)

A,B = 0,0

for j in range(n):
    if s[j] != a[j]:
        A += 1
    if s[j] != b[j]:
        B += 1

print(min(A,B))


Measured memory_bytes: 6556
import * as fs from 'fs';

const input = fs.readFileSync('/dev/stdin', 'utf8');
// const input = fs.readFileSync('./input.txt', 'utf8');

_c(input);

function _c(input: string) {
  const A = input
    .split('\n')[1]
    .split(' ')
    .map((s) => parseInt(s));
  let sum = 0n;
  let front = 0;
  for (const a of A) {
    if (front <= a) {
      front = a;
    } else {
      sum += BigInt(front - a);
    }
  }
  console.log(sum.toString());
}


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

using namespace std;

#define REP(i, x, y) for (int i = x; i < y; i++)

const int8_t  INFC = 0x3f;
const int16_t INFS = 0x3f3f;
const int32_t INF  = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;

int usedA[12345],usedB[12345];
vector<int> A,B,BtoA(12345);
string s[12345];

int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    int ans = 0;
    REP(k, 0, n)
    {
        //string s[k];
        cin >> s[k];
        for (int i = 0; i < s[k].size() - 1; i++)
        {
            if (s[k][i] == 'A' && s[k][i + 1] == 'B') ans++;
        }
        if (s[k].back()=='A') A.push_back(k);
        if (s[k].front()=='B') B.push_back(k);
        if (s[k].back()!='A'&&s[k].front()!='B') s[k]="ZZ";
        else s[k] = string()+(s[k].front()=='B'?'B':' ')+(s[k].back()=='A'?'A':'Z');
    }
    sort(s,s+n);
    REP(i,0,n)
    {
        //cout << s[i] << endl;
        REP(j,i+1,n)
        {
            if (usedB[j]==0&&s[i].back()=='A'&&s[j].front()=='B') {ans++,usedB[j]=1;break;}
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
from sys import setrecursionlimit
setrecursionlimit(1000000)
def calc_dist(b,h,dist,E,D,ne):
	D[dist] += 1
	for nxt in E[h]:
		if nxt == b or nxt == ne:
			continue
		calc_dist(h,nxt,dist+1,E,D,ne) 

def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for i in xrange(N):
			D = [0]*N
			calc_dist(-1,i,0,E,D,-1)
			for j in xrange(rad):
				D[rad-j-1] += D[rad-j]
			ans = min(N-D[0],ans)
	else:
		for a,b in pairs:
			D1 = [0]*N
			D2 = [0]*N
			calc_dist(-1,a,0,E,D1,b)
			calc_dist(-1,b,0,E,D2,a)
			for j in xrange(rad):
				D1[rad-j-1] += D1[rad-j]
				D2[rad-j-1] += D2[rad-j]
			ans = min(N-D1[0]-D2[0],ans)
	print ans

solve()

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

int main(){
  int n,a;
  set<int>s;
  cin>>n;
  for(int i=0;i<n;++i){
  	cin>>a;
  	s.insert(a);
  }
  cout << s.size() << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;

int main(){
	while(1){
		int n,k; cin >>n>>k;
		if(n==0&& k==0) break;
		vector<ll> a(n);
		cinf(n,a);
		vector<ll> s(n+1,0);
		for(int i=0;i<n;i++){
			s[i+1]=s[i]+a[i];
		}
		ll ans=-1e9;
		for(int i=0;i<=n-k;i++){
			ll sum=s[i+k]-s[i];
			ans=max(ans,sum);
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 4408
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define N 100005
int ok[405][405];
int vis[405];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ok[i][j]=1;
    pii p[100005];
    for(int i = 0;i<m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        p[i]=mp(x,y);
    }
    for(int i = 1;i<=n;i++){
        MEM(vis);
        vis[i]=1;
        int ook=1;
        vis[i]=1;
        for(int j=m-1;j>=0;j--){
            if(vis[p[j].x]||vis[p[j].y]){
                if(vis[p[j].x]&&vis[p[j].y]){
                    ook=0;
                    //if(p[j].x==i||p[j].y==i)ook=0;
                    //break;
                }
                if(vis[p[j].x])vis[p[j].y]=1;
                if(vis[p[j].y])vis[p[j].x]=1;
            }
        }
        for(int j=0;j<m;j++){
            if(vis[p[j].x]||vis[p[j].y]){
                if(vis[p[j].x]&&vis[p[j].y]){
              //      if(p[j].x==i||p[j].y==i)ook=0;
               //     break;
                }
                if(vis[p[j].x])vis[p[j].y]=1;
                if(vis[p[j].y])vis[p[j].x]=1;
            }
        }
        if(!ook){
            for(int j=1;j<=n;j++)ok[i][j]=ok[j][i]=0;
        }
        for(int j=1;j<=n;j++){
            if(vis[j])ok[i][j]=ok[j][i]=0;
        }
    }
    LL ans=0;
    for(int i = 1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ans+=ok[i][j];
            if(ok[i][j]){
              //  printf("%d %d\n",i,j);
            }
        }
    }
    printf("%lld\n",ans);
}
/*
3 10 17 25 34 44
6 24 47 78 118    168
 18  23  31  40 50

 45 100 186 312  488  725
   55 86 126   176  

     0   
     1   1
     2   3
     3 5  1 0 0
    4*/

Measured memory_bytes: 1664
#include <stdio.h>

int main(int argc, char *argv[])
{
    int x, y;

    for (;;) {
        scanf("%d%d", &x, &y);
        if ((x == 0) && (y == 0))
            break;
        if (x < y)
            printf("%d %d\n", x, y);
        else
            printf("%d %d\n", y, x);
    }
}


Measured memory_bytes: 2044
#include <stdio.h>

int main(){
  char line[100];
  int num;
  int i;
  int s[13], h[13], c[13], d[13];
  char card;
  int n;
  for(i=0; i<13; ++i){
	s[i]=0;
	h[i]=0;
	c[i]=0;
	d[i]=0;
  }
  fgets(line, sizeof(line), stdin);
  sscanf(line, "%d", &num);
  for(i=0; i<num; ++i){
	fgets(line, sizeof(line), stdin);
	sscanf(line, "%c %d", &card, &n);
	n=n-1;
	switch(card){
	case 'S':
	  s[n]=1;
	  break;
	case 'H':
	  h[n]=1;
	  break;
	case 'C':
	  c[n]=1;
	  break;
	case 'D':
	  d[n]=1;
	default:
	  break;
	}
  }
  for(i=0; i<13; ++i){
	if(s[i]==0)
	  printf("S %d\n",i+1);
}
  for(i=0; i<13; ++i){
	if(h[i]==0)
	  printf("H %d\n",i+1);
}
  for(i=0; i<13; ++i){
	if(c[i]==0)
	  printf("C %d\n",i+1);
}
  for(i=0; i<13; ++i){
	if(d[i]==0)
	  printf("D %d\n",i+1);
}

  return 0;
}



Measured memory_bytes: 2036
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
#define PI acos(-1.0)
#define eps 1e-9
#define ll long long
#define ull unsigned long long
#define nl printf("\n")
#define sf scanf
#define pf printf
#define INF (ll)1e15
#define mod 1000000007

///#define isValid(n,m,nx,ny)nx>=0&&nx<n&&ny>=0&&ny<m
///int kx[]={1, 1, -1, -1, 2, 2, -2, -2}; //knight moves
///int ky[]={2,-2,  2, -2, 1,-1,  1, -1}; //knight moves
///int dx[]={1,-1,0,0,1,-1,1,-1};//eight direction
///int dy[]={0,0,1,-1,1,-1,-1,1};//eight direction
 
///using namespace __gnu_pbds;
using namespace std;
 
///inline double toRad(double deg){return deg*PI/180;}
///inline double toDeg(double rad){return rad*180/PI;}
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;
 
const int S=123456;
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    #endif
    int n,m;
    while(sf("%d %d",&n,&m)==2)
    {
        string s[n+5];
        for(int i=0;i<n;i++)
        {
            cin>>s[i];
        }

        int x=0,y=0;
        for(int i=0;i<n+2;i++)
        {
            for(int j=0;j<m+2;j++)
            {
                if(i==0 || i==n+1)pf("#");
                else if(j==0 || j==m+1)pf("#");
                else
                {
                    pf("%c",s[x][y]);
                    y++;
                    if(y==m)x++,y=0;
                }
            }
            nl;
        }
    }
    return 0;
}
 









 




























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

int main()
{
    long w, h, x, y;
    cin >> w >> h >> x >> y;
    double ans = w * h / 2.0;
    int num = 0;
    if (x * 2 == w && y * 2 == h) {
        num = 1;
    }
    cout << ans << " " << num << endl;
    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main() {
  string s; cin>>s;
  cout<<((s[2]==s[3] && s[4]==s[5]) ? "Yes" : "No")<<endl;
}

Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
using namespace std;

#define LL long long int

int N,M;
int A[10];

string ans = "";

bool is_a_bigger(const string a,const string b){//aの方が大きいかどうかを返す
	if(a.length()!=b.length()) return a.length()>b.length();
	for(int i=0;i<a.length();i++){
		if(a[i]!=b[i]) return a[i]>b[i];
	}
	return false;
}

void solve(){
	int num2match[10];//iを作るのに必要なマッチの数をnum2match[i]とおく
	num2match[1] = 2;
	num2match[2] = 5;
	num2match[3] = 5;
	num2match[4] = 4;
	num2match[5] = 5;
	num2match[6] = 6;
	num2match[7] = 3;
	num2match[8] = 7;
	num2match[9] = 6;
	string dp[10001];//マッチ棒i本で作れる最大値をdp[i]とおく
	for(int i=1;i<=N;i++) dp[i] = "-";
	dp[0] = "";
	for(int i=1;i<=N;i++){
		for(int n=0;n<M;n++){
			if(i-num2match[A[n]]>=0){
				if(dp[i-num2match[A[n]]]!="-"){
					string new_dp = to_string(A[n])+dp[i-num2match[A[n]]];
					if(is_a_bigger(new_dp,dp[i])){
						dp[i] = new_dp;
					}
				}
			}
		}
	}
	ans = dp[N];
}
 
int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++)cin >> A[i];
 
	solve();

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


Measured memory_bytes: 32384
N, K = map(int, input().split())
tree = [int(input()) for n in range(N)]
diff = 10 ** 9
tree.sort()
for i in range(N - (K - 1)):
    if tree[i] == tree[i + 1] == tree[i + 2]:
        diff = 0
        break
    elif tree[i + K - 1] - tree[i] < diff:
        diff = tree[i + K - 1] - tree[i]
print(diff)


Measured memory_bytes: 7384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int x; cin >> x;
    cout << (x==3 || x==5 || x==7 ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
S = str(input())



rightanswer =[]
for i in range(len(S)):
    if i%2==0:
        rightanswer.append(0)
    else:
        rightanswer.append(1)

difference=0
for i in range(len(S)):
    if S[i] != str(rightanswer[i]):
               difference+=1

print(min(difference,len(S)-difference))

Measured memory_bytes: 4084
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        List<String> list = new ArrayList<>(Arrays.asList(new String[] { "3", "5", "7" }));
        for (int i = 0; i < 26484; i++) {
            String base = list.get(i);
            list.add(base + 3);
            list.add(base + 5);
            list.add(base + 7);
        }

        List<Long> longList = list.stream().filter(i -> i.contains("3") && i.contains("5") && i.contains("7"))
                .map(i -> Long.parseLong(i)).collect(Collectors.toList());

        int result = 0;
        for (int i = 0; i < longList.size(); i++) {
            if (longList.get(i) <= (long) n) {
                result++;
            }
        }

        // 出力
        System.out.println(result);
    }
}


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

int main(){
  string s;
  cin >> s;
  sort(s.begin(),s.end());
  char a=s[0];
  map<char,bool> check;
  
  for(char c:s){
    if(check.count(c)) continue;
    else{
      int t= count(s.begin(),s.end(),c);
      check[c]=1;
      if(t%2!=0){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  if(A%2 != 0 && B%2 != 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


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

int main(){
  int A,B,K;
  cin>>A>>B>>K;
  int sum=0;
  for(int i=100;i>0;i--){
    if(A%i==0&&B%i==0){
      sum++;
      if(sum==K){
        cout<<i<<endl;
        return 0;
      }
    }
  }
    
  
  
  
}

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

int main(void) {
  int A, B, ans;
  cin >> A >> B;

  ans = (B-1) / (A-1);
  if((B-1)%(A-1)!=0) ans+=1;
  
  cout << ans << endl; 

  return (0);
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      int A_1 = sc.nextInt();
      int A_2 = sc.nextInt();
      int A_3 = sc.nextInt();
      int[] S = new int[]{A_1,A_2,A_3};
      Arrays.sort(S);
      
      System.out.println((S[2]-S[1])+(S[1]-S[0]));
    }
}

Measured memory_bytes: 35788
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);       
		int n = sc.nextInt();
        int judge = 0;
        if(n%100>0 && n%100<=12){judge++;}
        if(n/100>0 && n/100<=12){judge+=2;}
		if(judge==0){System.out.println("NA");}
        if(judge==1){System.out.println("YYMM");}
        if(judge==2){System.out.println("MMYY");}
        if(judge==3){System.out.println("AMBIGUOUS");}
  }
}


Measured memory_bytes: 21844
A, B, C, X, Y = map(int, input().split())
 
p1 = 2 * C * min(X, Y) + A * (X - min(X, Y)) + B * (Y - min(X, Y))
p2 = 2 * C * max(X, Y)
p3 = A * X + B * Y
print(min(p1, p2, p3))

Measured memory_bytes: 9128
S=input()
if S =="SUN":
    print(7)
if S =="MON":
    print(6)
if S =="TUE":
    print(5)
if S =="WED":
    print(4)
if S =="THU":
    print(3)
if S =="FRI":
    print(2)
if S =="SAT":
    print(1)

Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7

H, W, K = inpl()
cost = [[0]*(W) for _ in range(W)]

# 棒を移動するときの倍率
for i in range(W):
    for j in range(-1, 2):
        k = i + j
        if k < 0 or k >= W:
            continue
        q = [0] * (W-1) # "."*(W-1)
        if j == -1:
            if i > 0:
                q[i-1] = 1
            if i > 1:
                q[i-2] = 2
            if i < W - 1:
                q[i] = 2
        elif j == 0:
            if i > 0:
                q[i-1] = 2
            if i < W - 1:
                q[i] = 2
        else:
            if i < W - 1:
                q[i] = 1
            if i < W - 2:
                q[i+1] = 2
            if i > 0:
                q[i-1] = 2
        pattern = 0
        Q = [q*1]
        #print(i, k, j,  q)
        while Q:
            p = Q.pop()
            if not 0 in p:
                pattern += 1
                continue
            s = p.index(0)
            q = p*1
            q[s] = 2
            Q.append(q)
            p[s] = 1
            if s < W - 2:
                p[s+1] = 2
            Q.append(p)
        cost[i][k] = pattern

DP = [1] + [0]*(W-1)
for _ in range(H):
    DP2 = [0]*(W)
    for i in range(W):
        for j in range(max(0, i-1), min(W, i+2)):
            DP2[j] = (DP2[j] + (DP[i] * cost[i][j])%MOD)%MOD
    DP = DP2

print(DP2[K-1])

Measured memory_bytes: 40432
D,G = map(int,input().split())
p = [0]*D
c = [0]*D
ans = 10 ** 9
for i in range(D):
    p[i],c[i] = map(int,input().split())
for i in range(2 ** D):
    point = 0
    count = 0
    for j in range(D):
        if (i>>j)&1 == 1:
            point += 100*(j+1)*p[j]+c[j]
            count += p[j]
    if point < G:
        for j in range(D)[::-1]:
            if ((i>>j)&1) == 0:
                for k in range(p[j]):
                    point += (j+1)*100
                    count += 1
                    if point >= G:
                        break
                break
    if point >= G:
        ans = min(ans,count)
print(ans)

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef unordered_set<int> si;
typedef pair<int, int> pp;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define all(e) (e).begin(), (e).end()


template <typename T>
void printV(vector<T> A) {
    if (A.empty()) cerr << "EMTPY\n";
    else { 
        cerr << "[";
        for (int i = 0; i < A.size() -1 ; ++i) {
            cerr << A[i] << ", ";
        }
        if (A.size()) cerr << A.back() << "]\n";
    }
}


template <typename T>
void printVV(vector<vector<T>> A) {
    cerr << "[";
    for (auto v : A) {
        printV<T>(v);
    }
    cerr << "]";
}

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&& ...args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " |";
    __f(comma + 1, args...);
}

int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s; cin >> s;
    int n; cin >> n;
    bool rev = false;
    
    string pre,suf;
    for (int i = 0; i < n; ++i) {
        int t; cin >> t;
        if (t == 2) {
            int f; char c; cin >> f >> c;
            if ((f == 2 && rev) || (f == 1 && !rev)) pre = c + pre;
            else suf = suf + c;
        }
        else {
            rev = !rev;
        }
    }

    s = pre + s + suf;
    if (rev) reverse(all(s));
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 1320
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)n;i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<ll,ll> mll;
typedef vector<ll> vll;
ll inf=1e18;
 
 
ll N;
ll A[200003];
 
int main(){
    cin>>N;
    Rep(i,N) cin>>A[i];
    A[N]=0;
    bool f=true;
    ll cnt=0;
    Rep(i,N){
        if((A[i]>i)||(i>=1&&(A[i]>(A[i-1]+1)))){
            f=false;
            break;
        }
    }
    if(f){
        rep(i,N-1){
            if(A[i-1]+1==A[i]) cnt++;
            else cnt+=A[i];
        }
        cout<<cnt<<endl;
    }
    else cout<<-1<<endl;

    
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){if((ll)(a)==inf)cout<<"inf"<<'\n';else if((ll)(a)==-inf)cout<<"-inf"<<'\n';else cout<<a<<'\n';}
template<class T,class U> void outs(T a,U b){if((ll)(a)>=inf-100||(ll)(a)<=-inf+100)out(b);else out(a);}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';if((ll)(v[i])==inf)cout<<"inf";else if((ll)(v[i])==-inf)cout<<"-inf";else cout<<(ll)(v[i]);}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
int main(){
    ll n;cin>>n;
    rep(tt,n){
        ll a,b,c,d;cin>>a>>b>>c>>d;
        if(b>d||a<b){
            out("No");
            continue;
        }
        if(c>=b-1){
            out("Yes");
            continue;
        }
        ll g=gcd(b,d);
        a%=g;
        ll res=g*((c+1)/g+1)+a;
        while(res-g>=c+1)res-=g;
        //out(res);
        if(res>=b){
            out("Yes");
            continue;
        }
        out("No");
    }
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

struct Vec{
	int ind;
	int val;
};

bool valDesc( const Vec& left, const Vec& right ) {
    return left.val == right.val  ? left.val> right.val: left.val > right.val;
}

bool valAsc( const Vec& left, const Vec& right ) {
    return left.val == right.val  ? left.val <  right.val: left.val < right.val;
}
int main(void){
	int ans,N,K,a[100000];
	string s;
	vector<int> stable;
	
	scanf("%d%d",&N,&K);
	for(int i=0;i<N;i++){
		scanf("%d", &a[i]);
	}

	ans = 1 + ceil(float(N-K)/float(K-1)) ;
	printf("%d\n",ans);
	fflush(stdout);

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,t=0;
	cin>>n;
	if(n>=0&&n<10)
		t+=n;
	if(n>=10&&n<100)
		t+=9;
	if(n>=100&&n<1000)
		t+=n-99+9;
	if(n>=1000&&n<10000)
		t+=909;
	if(n>=10000&&n<100000)
		t+=n-9999+909;
	if(n>=100000&&n<1000000)
		t+=90909;
	if(n>=1000000&&n<10000000)
		t=n-999999+90909;
	if(n>=10000000&&n<100000000)
		t=9090909;
	if(n>=100000000&&n<1000000000)
		t=n-99999999+9090909;
	cout<<t;
} 


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int number = int.Parse(Console.ReadLine());
            int[] inputPs = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

            long answer = 0;

            List<int> greaterValues = new List<int>{ 0, 0, number + 1, number + 1 };

            // 各値がどの index に存在するかの配列。
            int[] indices = new int[number];
            for(int i = 0; i < number; i++)
            {
                // inputPs 上の位置を 1 ～ n の値で表現
                indices[inputPs[i] - 1] = i + 1;
            }

            // 大きい数字から処理していく
            for(int i = number; i > 0; i--)
            {
                int myPoint = indices[i - 1];
                int point0 = InsertValuesInOrder(myPoint, ref greaterValues);
                long representTime = GetRepresentTime(point0, greaterValues);
                answer += representTime * i;
            }
            Console.WriteLine(answer.ToString());

            return;
        }

        static int InsertValuesInOrder(int value, ref List<int> targetSeq)
        {
            int inf = 0;
            int sup = targetSeq.Count() - 1;
            while (sup - inf > 1)
            {
                int pivot = (sup + inf) / 2;
                if (targetSeq[pivot] < value)
                {
                    inf = pivot;
                }
                else
                {
                    sup = pivot;
                }
            }
            targetSeq.Insert(sup, value);

            return sup;
        }

        static long GetRepresentTime(int myIndex, List<int> largerValuePoints)
        {
            int point0 = largerValuePoints[myIndex];
            int leftPoint2 = largerValuePoints[myIndex - 2];
            int leftPoint1 = largerValuePoints[myIndex - 1];
            int rightPoint1 = largerValuePoints[myIndex + 1];
            int rightPoint2 = largerValuePoints[myIndex + 2];
            int leftFirstValueRange = point0 - leftPoint1;
            int leftSecondValueRange = leftPoint1 - leftPoint2;
            int rightFirstValueRange = rightPoint1 - point0;
            int rightSecondValueRange = rightPoint2 - rightPoint1;
            return leftFirstValueRange * rightSecondValueRange + leftSecondValueRange * rightFirstValueRange;
        }
    }
}


Measured memory_bytes: 20948
# A - Sharing Cookies
# https://atcoder.jp/contests/abc067/tasks/abc067_a

A, B = map(int, input().split())

result = 'Impossible'

if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
    result = 'Possible'

print(result)


Measured memory_bytes: 9148
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

int main()
{
  std::string S, T;
  std::cin >> S >> T;
  std::vector<std::set<int>> alphaS(26);

  for(int i=0; i<S.size(); i++)
  {
    alphaS[S[i]-'a'].insert(i);
  }

  int loop = 0;
  int pos = -1;
  for(int i=0; i<T.size(); i++)
  {
    const auto& alphaset = alphaS[T[i]-'a'];
    if(alphaset.empty()) { std::cout << -1; return 0;}
    auto it = alphaset.upper_bound(pos);
    if( it == alphaset.end() )
    {
      pos = -1; loop += 1; i-=1;
    }
    else
    {
      pos = *it;
    }
  }

  std::cout << loop*S.length() + pos + 1;
}


Measured memory_bytes: 5120