akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;


int main(){
	int s;
	cin >> s;
	int a,b;
	a=s/100;
	b=s%100;

	if((a>12 || a==0) && (b>12 || b==0)){
		cout << "NA" <<endl;
	}else if(0<a && a<=12 && 0<b && b<=12){
		cout << "AMBIGUOUS" <<endl;
	}else if(0<b && b<=12){
		cout << "YYMM" <<endl;
	}else{
		cout << "MMYY" <<endl;
	}
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <string.h>
#include <utility>
#include <vector>
using namespace std;

#define dlog(str) cout << "====" << str << endl;
#define INF 999999999
#define MOD 1000000009
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define REPR(i, n) for(int i = n - 1; 0 <= i; i--)
#define FOR(i, s, e) for(int i = s; i <= e; i++)
#define FORR(i, s, e) for(int i = s; e <= i; i--)
#define LLI long long int
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

int main() {
    int N;
    cin >> N;
    vector<int> v(N);
    int sum = 0, sum2 = 0, mi = INF;
    REP(i, N) {
        cin >> v[i];
        sum += v[i];
    }
    REP(i, N) {
        sum2 += v[i];
        chmin(mi, abs(sum - sum2 * 2));
    }
    cout << mi;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000000007


int main() {

	ll n; cin>>n;
	vector<ll> A(n);

	for(ll i=0;i<n;i++)
		cin>>A[i];
	
	ll maxi = 0, curr=0;
	for(ll i=0;i<n-1;i++) {
		if(A[i+1]<=A[i]){
			curr++;
			maxi = max(maxi, curr);
		}
		else
			curr=0;
	}

	cout<<maxi<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#define MOD 1000000007LL

using namespace std;
typedef long long int ll;

ll gcd(ll a, ll b)
{
	ll a1, r;
	if(a<b){
		a1=b;
		b=a;
		a=a1;
	}
	if(b==0){
		return a;
	}else{
		r=a%b;
		return gcd(b, r);
	}
 
}

long long int powmod(long long int a, long long int k, long long int m){ //0<=a<=1e9, 0<k<=1e18, 0<m<=1e9
	if(a==0){
		return 0;
	}
	long long int apow[60], c[60];
	for(int i=0; i<60; i++){
		if(i==0){
			apow[i]=a;
			c[i]=1;
		}else{
			apow[i]=apow[i-1]*apow[i-1]%m;
			c[i]=c[i-1]*2;
		}
	}
	long long int ans=1;
	for(int i=59; i>=0; i--){
		if(k>=c[i]){
			ans=ans*apow[i]%m;
		}
		k=k%c[i];
	}
	return ans;
}

int main()
{
	ll s;
	scanf("%lld", &s);
	ll sum[10];
	ll p[10];
	p[0]=1;
	for(ll i=1; i<10; i++){
		p[i]=p[i-1]*10;
		sum[i]=i*9*p[i-1];
	}
	ll ans=0;
	for(ll i=1; i<10; i++){
		for(ll j=i; j<10; j++){
			if(j==i){
				if(s%i!=0 || s/i>9*p[i-1]){
					continue;
				}else{
					ans+=(9*p[i-1]-s/i+1);
					ans%=MOD;
				}
			}else{
				ll s1=s;
				for(ll k=i+1; k<j; k++){
					s1-=sum[k];
				}
				if(s1<=0) continue;
				ll d=gcd(i, j);
				if(s1%d!=0) continue;
				ll i1=i/d, j1=j/d;
				s1=s1/d;
				ll y1=1;
				for(; y1<=i1; y1++){
					if((s1-j1*y1)%i1==0) break;
				}
				ll x1=(s1-j1*y1)/i1;
                if(x1<=0) continue;
				ll m1;
				if((x1-9*p[i-1]+j1-1)/j1<0){
					m1=0;
				}else{
					m1=(x1-9*p[i-1]+j1-1)/j1;
				}
				ll m2=(x1-1)/j1;
				if((9*p[j-1]-y1)/i1<m2) m2=(9*p[j-1]-y1)/i1;
				if(m1<=m2){
					ans+=(m2-m1+1);
					ans%=MOD;
				}
			}
		}
	}
	for(ll i=1; i*i<=s; i++){
		if(s%i==0){
			if(i>=10){
				ans=(ans+9*powmod(10, i-1, MOD)+1+MOD-s/i)%MOD;
			}
			if(i*i<s && s/i>=10){
				ans=(ans+9*powmod(10, s/i-1, MOD)+1+MOD-i)%MOD;
			}
		}
	}
	ans=(ans+s)%MOD;
	for(ll i=1; i*i<=s; i++){
		if(s%i==0){
			ans=(ans+MOD-1)%MOD;
			if(i*i<s){
				ans=(ans+MOD-1)%MOD;
			}
		}
	}
	for(ll i=1; i<9; i++){
		ll y1=s%i;
		if(y1==0) y1+=i;
		ll x1=(s-(i+1)*y1)/i;
		if(x1<=0) continue;
		ans=(ans-((x1-1)/(i+1)+1)%MOD+MOD)%MOD;
	}
	printf("%lld\n", ans);		
	return 0;
}

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

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

constexpr auto inf = 1e9;

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; }

using ll = long long;

int main()
{
	ll x, y;
	cin >> x >> y;

	ll ans = 0;
	ll a = x;
	while (a <= y)
	{
		a *= 2;
		ans++;
	}

	cout << ans << endl;

	return 0;
}

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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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


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

int main() {
    int n;
    std::string s;
    std::cin >> n >> s;

    for(int i = 0; i < s.length(); i++) {
        s[i] = s[i] + n;
        if(s[i] > 90) {
            s[i] = s[i] - 26;
        }
    }

    std::cout << s << std::endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
  int i, j, k;

  int n1 = mid - left;
  int n2 = right - mid;
  for ( i = 0; i < n1; i++ ) L[i] = A[left + i];
  for ( i = 0; i < n2; i++ ) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  i = j = 0;
  for ( k = left; k < right; k++ ){
    cnt++;
    if ( L[i] <= R[j] ){
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right ){
  int mid;
  if ( left+1 < right ){
    mid = (left + right)/2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

main(){
  int A[MAX], n, i;
  scanf("%d", &n);
  cnt = 0;
  for ( i = 0; i < n; i++ ) {
    scanf("%d", &A[i]);
    if (A[i] >= SENTINEL ){
      return 1;
    }
  }
  mergeSort(A, n, 0, n);

  for ( i = 0; i < n; i++ ) {
    if ( i ) printf(" ");
    printf("%d", A[i]);
    }
  printf("\n");

  printf("%d\n", cnt);

  return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int INF = 1000000000;

typedef vector< vector<int> > graph;

graph g;
vector<int> match;
vector<bool> visit;

bool search(int u){
	if(u<0) return true;
	for(int i=0;i<g[u].size();i++){
		int next = g[u][i];
		if(visit[next]) continue;
		visit[next] = true;
		if(search(match[next])){
			match[u] = next, match[next] = u;
			return true;
		}
	}
	return false;
}

int maximumMatch(int L, int R){
	int res = 0;
	match.assign(L+R, -1);
	for(int i=0;i<L;i++){
		visit.assign(L+R, false);
		res += search(i);
	}
	return res;
}

int main(){
	int N, M, L;
	static int dist[100][100];
	while(cin >> N >> M >> L, N){
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				dist[i][j] = (i==j ? 0 : INF);
		for(int i=0;i<M;i++){
			int a, b, c; cin >> a >> b >> c;
			dist[a][b] = dist[b][a] = min(dist[a][b], c);
		}
		for(int k=0;k<N;k++)
			for(int i=0;i<N;i++)
				for(int j=0;j<N;j++)
					dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
		g.assign(2*L, vector<int>());
		vector< pair<int, int> > vp(L);
		for(int i=0;i<L;i++)
			cin >> vp[i].second >> vp[i].first;
		sort(vp.begin(), vp.end());
		for(int i=0;i<L;i++){
			for(int j=i+1;j<L;j++){
				if(vp[i].first + dist[vp[i].second][vp[j].second] <= vp[j].first){
					g[i].push_back(L+j);
					g[L+j].push_back(i);
				}
			}
		}
		cout << L - maximumMatch(L, L) << endl;
	}
}

Measured memory_bytes: 6284
import sys

def solve(n):
    l = [2,1]
    for i in range(n):
        l.append(l[i]+l[i+1])
    print(l[n])


def readQuestion():
    ws = sys.stdin.readline().strip().split()
    n = int(ws[0])
    return (n,)

def main():
    solve(*readQuestion())

# Uncomment before submission
main()

Measured memory_bytes: 2940
let last_i = ref 0

let parent i = int_of_float (floor (float_of_int i) /. 2.)

let left i = 2*i

let right i = 2*i + 1

let swap i j t = let tmp = t.(i) in t.(i) <- t.(j); t.(j) <- tmp

let extract (t : int array) =
  let ret = t.(1) in
  t.(1) <- t.(!last_i);
  decr last_i;
  let rec max_heapify i =
    let l = left i in
    let r = right i in
    let m = if l <= !last_i && t.(l) > t.(i) then l else i in
    let m = if r <= !last_i && t.(r) > t.(m) then r else m in
    if i = m then ()
    else begin
      let tmp = t.(i) in t.(i) <- t.(m); t.(m) <- tmp;
      max_heapify m
    end in
  max_heapify 1;
  ret

let insert x (t : int array) =
  incr last_i;
  t.(!last_i) <- x;
  let rec doit i =
    if i <= 1 || t.(parent i) >= t.(i) then ()
    else begin
      let pi = parent i in
      let tmp = t.(i) in t.(i) <- t.(pi); t.(pi) <- tmp;
      doit pi
    end in
  doit !last_i

let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let t = Array.make 2000001 0 in
  while true do
    match read_line () |> split_on_char ' ' with
    | ["extract"] -> extract t |> Printf.printf "%d\n"
    | ["insert"; n] -> insert (int_of_string n) t
    | _ -> exit 0
  done

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

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    int ans = 0;
    if (a > b) swap(a, b);
    if (a+w >= b) ans = 0;
    else ans = b - a - w;
    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define FAST  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int 
#define ar array
#define pb push_back
#define fi(a,b) for(ll i=a;i<(b);i++)
#define fj(a,b) for(ll j=a;j<(b);j++)
#define fk(a,b) for(ll k=a;k<(b);k++)


int main()
{
	FAST;
	//#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	//#endif
	//int tt;
	//cin>>tt;
	//while(tt--)
	{
		ll n;
		cin>>n;
		ll ans=0;
		fi(1,n)
		{
			ans+=n/i;
			if(n%i==0) ans--;
		}
		cout<<ans;
		
		
		
	}		
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

    int ans = 0;
    bool ok = true;
    rep(i, 3)
    {
        if (s[i] == 'R')
        {
            if (ok)
            {
                ans++;
            }
            ok = true;
        }
        else
        {
            if (ans > 0)
            {
                ok = false;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long int
#define pr pair<ll, ll>
#define tp tuple<ll, ll, ll>
using namespace std;
long long int mod = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, k;
    cin >> n >> k;
    ll ans = n % k;
    ans = min(ans, k - n % k);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
function bomb(t,k){
   var dy=[-1,0,0,1];
   var dx=[0,-1,1,0];
   var ary=[[t,k,0]];
   var good=false;
   var obj={};
   while(true){
      if(ary.length==0)break;
      var v=ary.shift();
      var t=v[0];
      var k=v[1];
      if(obj.hasOwnProperty(t.join(",")+"&"+k.join(",")))continue;
      else obj[t.join(",")+"&"+k.join(",")]=true;
      var cnt=v[2];
      if(cnt==100)break;
      if(t[0]==k[0] && t[1]==k[1]){good=true;break;}
      for(var i=0;i<4;i++){
         var tx=t[0]+dx[i];
         var ty=t[1]+dy[i];
         var kx=k[0]+(-1*dx[i]);
         var ky=k[1]+(-1*dy[i]);
         if(tx<0 || ty<0 || tx>=x || ty>=y || yx[ty][tx]==1){
            tx=t[0];
            ty=t[1];
         }
         if(kx<0 || ky<0 || kx>=x || ky>=y || yx[ky][kx]==1){
            kx=k[0];
            ky=k[1];
         }
         ary.push([[tx,ty],[kx,ky],cnt+1]);
      }
   }
   return (good)?cnt:"NA";
}
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
while(true){
   var xy=arr.shift().split(" ").map(Number);
   var x=xy[0];
   var y=xy[1];
   if(xy.join(" ")=="0 0")break;
   var t=arr.shift().split(" ").map(Number);
   t=[t[0]-1,t[1]-1];
   var k=arr.shift().split(" ").map(Number);
   k=[k[0]-1,k[1]-1];
   var yx=[];
   for(var i=0;i<y;i++)yx.push(arr.shift().split(" ").map(Number));
   console.log(bomb(t,k));
}

Measured memory_bytes: 101488
n, x = map(int, input().split())
h=[1]*(n+1)
p=[1]*(n+1)
for i in range(1, n+1):
    h[i]=3+h[i-1]*2
for i in range(1, n+1):
    p[i]=p[i-1]*2+1
def f(m, y):
    if m==0:
        return 1
    if y==1:
        return 0
    if y<=h[m-1]+1:
        return f(m-1, y-1)
    if y==h[m-1]+2:
        return p[m-1]+1
    if y<=h[m-1]*2+2:
        return f(m-1, y-h[m-1]-2)+p[m-1]+1
    if y==h[m-1]*2+3:
        return p[m-1]*2+1
print(f(n,x))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
 template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
int main(){
  int n,ans=0,x=0;
  cin>>n;
  for(int i=1;i<=n;i++){
    ans+=i;
    x++;
    if(ans>=n)
      break;
  }
  for(int i=1;i<=x;i++){
    if(ans-n==i)
      continue;
    else
      cout<<i<<endl;
  }
}


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

int main() {
    int n;
    cin >> n;
    vector<int> A(n), B(n), C(n - 1);
    for (int i = 0; i < n; i++) {
        cin >> A.at(i);
    }
    for (int i = 0; i < n; i++) {
        cin >> B.at(i);
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> C.at(i);
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        res += B.at(A.at(i) - 1);
        if (i > 0) {
            if (A.at(i) - 1 == A.at(i - 1)) {
                res += C.at(A.at(i - 1) - 1);
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 3010;
const double eps = 1e-9;
double p[N], dp[N][N];
int n;

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.precision(10);
   cout << fixed;
   
   cin >> n;
   dp[0][0] = 1;
   for (int i = 0; i < n; ++i){
      double p;
      cin >> p;
      for (int j = 0; j < n; ++j){
         dp[i + 1][j + 1] += dp[i][j] * p;
         dp[i + 1][j] += dp[i][j] * (1 - p);
      }
   }
   
   double ans = 0;
   for (int i = n / 2; i < n; ++i)
      ans += dp[n][i + 1];
   
   cout << ans << '\n';

   return 0;
}

Measured memory_bytes: 70784
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <stack>
#include <string.h>
#include <unordered_map>
using namespace std;

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define left  (2*idx)+1
#define right (2*idx)+2
#define pb push_back
#define ll long long
#define all(x) x.begin(),x.end()

const ll N = 100007;
int a[N];

int main()
{
	FIO;

	

	int n, k, q, m;
	cin >> n >> k >> q;
	m = q;
	while(q--)
	{
		int x;
		cin >> x;
		a[x]+=1;
	}

	for(int i=1; i<=n; i++)
	{
		if(m-a[i] >= k)
		{
			cout << "No\n";
		}
		else
		{
			cout << "Yes\n";
		}
	}
	return 0;
	
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec.at(i);
    }

    int val = 1;
    int break_count = 0;
    for (int i = 0; i < N; i++) {
        if (vec[i] == val) {
            val += 1;
            continue;
        } else {
            break_count += 1;
        }
    }

    if (val == 1) {
        cout << "-1" << endl;
    } else {
        cout << break_count << endl;
    }

    return 0;
}

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

int n,sz[1000000],par[1000000];
long long d[1000000],chdst[1000000];
pair<long long,int>id[1000000];

bool solve()
{
	for(int i=0;i<n;i++)
		id[i]=make_pair(d[i],i);
	sort(id,id+n);
	for(int i=0;i<n;i++)
	{
		sz[i]=1,par[i]=-2;
		chdst[i]=0;
	}
	for(int i=n-1;i >= 1;--i)
	{
		int at=id[i].second;
		long long want=d[at]-n+2 * sz[at];
		int idx=lower_bound(id,id+n,make_pair(want,-1))-id;
		if(idx >= i || id[idx].first!=want)
			return false;
		par[at]=id[idx].second;
		sz[par[at]] += sz[at];
		chdst[par[at]] += chdst[at]+sz[at];
	}
	int root=id[0].second;
	par[root]=-1;
	return chdst[root]==d[root];
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%lld",&d[i]);
	if(!solve())
	{
		printf("-1");
		return 0;
	}
	for(int i=0;i<n;i++)
		if(par[i]!=-1)
			printf("%d %d\n",i+1,par[i]+1);
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> h(N);
  for (int i=0 ; i<N ; i++)
    cin >> h.at(i);
  vector<int> mini(N);
  mini.at(0) = 0;
  mini.at(1) = abs(h.at(1)-h.at(0));
  for (int i=2 ; i<N ; i++){
    int way1 = mini.at(i-1)+abs(h.at(i)-h.at(i-1));
    int way2 = mini.at(i-2)+abs(h.at(i)-h.at(i-2));
    mini.at(i) = min(way1, way2);
  }
  cout << mini.at(N-1) << endl;
}

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

int main(){
	int a,b;
	cin >> a;
	string n;
	cin >> n;
	cin >> b;
	for(int i = 0;i<a;i++){
		if(n[i] == n[b-1]){
			cout << n[i];
		}
		else{
			cout << "*";
		}
	}
	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 P = pair<int, int>;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll first_plus = 0;
  ll first_minus = 0;
  ll sum1 = 0;
  ll sum2 = 0;
  for (int i = 0; i < n; i++){
    if(i % 2 == 0){
      sum1 += a[i];
      if(sum1 <= 0){
        first_plus += abs(sum1 - 1);
        sum1 = 1;
      }
      sum2 += a[i];
      if(sum2 >= 0){
        first_minus += abs(sum2 + 1);
        sum2 = -1;
      }
    }else{
      sum1 += a[i];
      if(sum1 >= 0){
        first_plus += abs(sum1 + 1);
        sum1 = -1;
      }
      sum2 += a[i];
      if(sum2 <= 0){
        first_minus += abs(sum2 - 1);
        sum2 = 1;
      }
    }
  }
  cout << min(first_plus, first_minus) << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n,m,c,ans,dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
bool check(int x,int y) {
  return x>=0 && x<n && y>=0 && y<m;
}

void solve(vector<int> a[], int t) {
  int e=a[0][0];
  for(int k=1; k<=6; k++) {
    if(t<5 && k==e) continue;
    if(t==5 && k!=e) continue;
    vector<int> b[n];
    for(int i=0; i<n; i++) b[i]=a[i];
    bool u[n][m];
    memset(u,0,sizeof(u));
    queue<P> que;
    que.push(P(0,0));
    b[0][0]=k;
    u[0][0]=1;
    int cnt=1;
    while(!que.empty()) {
      P p=que.front();que.pop();
      int nx=p.first,ny=p.second;
      for(int i=0; i<4; i++) {
        int x=nx+dx[i],y=ny+dy[i];
        if(check(x,y) && b[x][y]==e && !u[x][y]) {
          b[x][y]=k;
          u[x][y]=1;
          cnt++;
          que.push(P(x,y));
        }
      }
    }
    if(t==5 && e==c) ans=max(ans,cnt);
    if(t<5) solve(b,t+1);
  }
}

int main() {
  while(cin >> n >> m >> c && n) {
    vector<int> a[n];
    for(int i=0; i<n; i++) {
      for(int j=0,x; j<m; j++) {
        cin >> x;
        a[i].push_back(x);
      }
    }
    ans=0;
    solve(a,0);
    cout << ans << endl;
  }
  return 0;
}


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

cnt = 0
res = 0 #余力
for i in range(n):

    ch = min(a[i],res)
    cnt += ch
    a[i] -= ch
    if b[i] > a[i]:
        cnt += a[i]
        res = b[i] - a[i]
    else:
        cnt += b[i]
        res = 0

cnt += min(a[n],res)

print(cnt)

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

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; }

using ll=long long;
const int Nmax=110;
const int Wmax=100010;
int N,W; 
ll dp[Nmax][Wmax];
ll v[Nmax];
ll w[Nmax];
const ll INF=1LL<<60;


int main(){
  cin >> N >> W;
  for (int i=1;i<=N;i++)
      cin >> w[i] >> v[i];
  
  for (int j=0;j<=W;j++){
    for (int i=0;i<N;i++){
      chmax(dp[i+1][j],dp[i][j]);
      if (j+w[i+1]<=W) chmax(dp[i+1][j+w[i+1]],dp[i][j]+v[i+1]);
    }
  }
  
  cout << dp[N][W] << endl;
  
}


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

int N,ans;
string A,B,C;

int getSame(int i){
        if(A[i] == B[i] && A[i] == C[i]) return 3;
        else if(A[i] == B[i] || A[i] == C[i] || B[i] == C[i]) return 2;
        else return 1;
}

int main(){
        ans = 0;
     cin >> N >> A >> B >> C;
     for (int i=0; i<N; ++i){
             //cout << getSame(i) << endl;
             ans += 3-getSame(i);
     }

     cout << ans << endl;

     return 0;
}


Measured memory_bytes: 256
x = input()
m = len(x)
x = int(x)

p = m//2
q = m%2

if q==1:
  if p==0:
    print(x)
    exit()
  else:
    a = 90
    while(p>0):
      x -= a
      a *= 100
      p -= 1
    print(x)
    exit()
else:
  if p==0:
    print(0)
    exit()
  else:
    x = 0
    a = 9
    while(p>0):
      x += a
      a *= 100
      p -= 1
    print(x)
    exit()  
    


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

int main() {
  int N, K, ResultMin;
  cin >> N >> K;//N回　Kを足す

  //init
  ResultMin = 1;
  //考えられる最小値を求める
  for (int i = 0; i < N; i++) {
    int nibai, tasu;
    nibai = 0;
    tasu = 0;
    
    nibai = ResultMin * 2;
    tasu = ResultMin + K;
    if (nibai < tasu) {
      ResultMin = nibai;
    } else {
      ResultMin = tasu;
    }
  }
  cout << ResultMin << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define SORT(x) sort(ALL(x))
typedef long long ll;
typedef long double ld;
int main(){
    ll n;
    cin>>n;
    vector<ll> v(n);
    REP(i,n){
        cin>>v[i];
    }
    ll m;
    REP(i,1000){
        sort(ALL(v));
        m=v[0];
        if(m==1){
            cout<<1;
            return 0;
        }else{
            FOR(j,1,n){
                ll r=v[j]%m;
                if(r!=0){
                    v[j]=r;
                }
            }
        }
        if(m==MIN(v)){
            cout<<m;
            return 0;
        }
    }
}


Measured memory_bytes: 4044
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++) 
#define rrep(i,n) for(int i = 1; i <= (int)(n); i++) 
#define pb push_back
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

//const ll mod = 1000000007;
//const ll INF = mod * mod;
const double pi = 3.14159265358979;

double degree(double x) {
    return atan(x) / pi * 180;
}

int main() {
    double a,b,x;
    cin >> a >> b >> x;
    double s = x / a;
    if(s <= a*b/2) {
        double h = s * 2 / b;
        double c = b / h;
        cout << fixed << setprecision(10) << degree(c) << endl;
    }
    else {
        double h = (a * b - s) * 2 / a;
        double c = h / a;
        cout << fixed << setprecision(10) << degree(c) << endl;
    }
}

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

int main() {
	long int n;
	cin >> n;
	vector<long long int> a(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	long long int d = a[n / 2 - 1];
	long long int e = a[n / 2];
	cout << e - d << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <utility>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main(void)
{
	int N;
	vector<pair<int, int>> list;

	cin >> N;
	list.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int x, y;
		cin >> x >> y;
		if (x < y)
		{
			list.emplace_back(x, y);
		}
		else
		{
			list.emplace_back(y, x);
		}
	}

	// case R_max = max, B_min = min:
	//      R <- bigger, B <- smaller
	int R_max = INT_MIN;
	int R_min = INT_MAX;
	int B_max = INT_MIN;
	int B_min = INT_MAX;
	for (int i = 0; i < N; ++i)
	{
		int bigger = list[i].second;
		int smaller = list[i].first;
		R_max = max(R_max, bigger);
		R_min = min(R_min, bigger);
		B_max = max(B_max, smaller);
		B_min = min(B_min, smaller);
	}

	long long result = (long long)(R_max - R_min) * (long long)(B_max - B_min);

	int max_of_all = R_max;
	int min_of_all = B_min;
	int second_min = R_min;

	// case B_max = max, B_min = min:
	//      minimize R_max - R_min
	sort(begin(list), end(list));
	R_max = list[list.size() - 1].first;
	R_min = INT_MAX;
	int R_range = R_max - list[0].first;
	for (int i = 0; i < N - 1; ++i)
	{
		R_max = max(R_max, list[i].second);
		if (R_min <= list[i].first)
		{
			break;
		}
		R_min = min(R_min, list[i].second);
		int R_min_ = min(R_min, list[i + 1].first);
		R_range = min(R_range, R_max - R_min_);
	}

	result = min(result, (long long)(R_range) * (long long)(max_of_all - min_of_all));

	cout << result << endl;
}

Measured memory_bytes: 1792
import sys
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

M = int(input())
dcs = map(int, read().split())

digit_sum = 0
digit_count = 0

for d, c in zip(dcs, dcs):
    digit_sum += d * c
    digit_count += c

print((digit_sum - 1) // 9 + digit_count - 1)

Measured memory_bytes: 108592
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[][] field = new char[8][8];
		for (int i = 0; i < 8; i++) {
			String str = sc.next();
			char[] c = str.toCharArray();
			for (int j = 0; j < str.length(); j++) {
				field[i][j] = c[j];
			}
		}
		char turn = 'o';
		int[] result = { 0, 0, 0 };
		boolean opassed = false;
		boolean xpassed = false;
		do {
			Arrays.fill(result, 0);
			char[][] tfield = new char[8][8];
			for (int i = 0; i < 8; i++)
				for (int j = 0; j < 8; j++)
					tfield[i][j] = field[i][j];
			int a = count(field, turn);
			for (int i = 0; i < 8; i++)
				for (int j = 0; j < 8; j++) {
					if (tfield[i][j] == '.')
						move(tfield, turn, i, j);
					int b = count(tfield, turn);
					if (b - a > Math.max(result[0], 1)) {
						result[0] = b - a;
						result[1] = j;
						result[2] = i;
					} else if (result[0] > 1 && b - a == result[0]) {
						if (turn == 'o') {
							if (i < result[2]
									|| (i == result[2] && j < result[1])) {
								result[1] = j;
								result[2] = i;
							}
						}
						if (turn == 'x') {
							if (i > result[2]
									|| (i == result[2] && j > result[1])) {
								result[1] = j;
								result[2] = i;
							}
						}
					}
					for (int k = 0; k < 8; k++)
						for (int l = 0; l < 8; l++)
							tfield[k][l] = field[k][l];
				}
			if (result[0] > 1) {
				move(field, turn, result[2], result[1]);
				if (turn == 'o')
					opassed = false;
				if (turn == 'x')
					xpassed = false;
			} else {
				if (turn == 'o')
					opassed = true;
				if (turn == 'x')
					xpassed = true;
			}
			if (turn == 'o')
				turn = 'x';
			else
				turn = 'o';
		} while (!(opassed && xpassed));
		printfield(field);
		sc.close();
	}

	static void printfield(char[][] field) {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++)
				System.out.print(field[i][j]);
			System.out.println();
		}
	}

	static int count(char[][] field, char turn) {
		int result = 0;
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				if (field[i][j] == turn)
					result++;
		return result;
	}

	static void move(char[][] field, char turn, int x, int y) {
		int[] dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
		int[] dy = { 1, 1, 0, -1, -1, -1, 0, 1 };
		field[x][y] = turn;
		for (int i = 0; i < dx.length; i++) {
			if (x + dx[i] >= 0 && x + dx[i] < 8 && y + dy[i] >= 0
					&& y + dy[i] < 8) {
				if ((turn == 'o' && field[x + dx[i]][y + dy[i]] == 'x')
						|| (turn == 'x' && field[x + dx[i]][y + dy[i]] == 'o')) {
					for (int j = 2; j < 8; j++) {
						if (x + j * dx[i] >= 0 && x + j * dx[i] < 8
								&& y + j * dy[i] >= 0 && y + j * dy[i] < 8) {
							if (field[x + j * dx[i]][y + j * dy[i]] == '.')
								break;
							if (field[x][y] == field[x + j * dx[i]][y + j
									* dy[i]]) {
								for (int k = 1; k < j; k++)
									field[x + k * dx[i]][y + k * dy[i]] = field[x][y];
								break;
							}
						}
					}
				}
			}
		}
	}
}

Measured memory_bytes: 24456
#include <stdio.h>

int main(int argc, char *argv[])
{
	int a,b,c;
	scanf("%d %d %d", &a, &b, &c);

	if (a <= b && b <= c) {
		printf("%d %d %d\n", a, b, c);
	} else if (a <= c && c <= b) {
		printf("%d %d %d\n", a, c, b);
	} else if (b <= c && c <= a) {
		printf("%d %d %d\n", b, c, a);
	} else if (b <= a && a <= c) {
		printf("%d %d %d\n", b, a, c);
	} else if (c <= a && a <= b) {
		printf("%d %d %d\n", c, a, b);
	} else if (c <= b && b <= a) {
		printf("%d %d %d\n", c, b, a);
	}

	return 0;
}

Measured memory_bytes: 596
#include <stdio.h>

int N;
int C[501];
int S[501];
int F[501];

int nextTrain(int c, int s, int f, int t){
        int n = 0;
        while(s + n * f < t){ n++; }
        return s + n * f;
}
int main(){
        scanf("%d",&N);

        int t = 0;
        for(int i = 1; i <= N - 1; i++){
                scanf("%d %d %d",C+i,S+i,F+i);
        }

        for(int start_pos = 1; start_pos <= N ; start_pos++){
                int pos = start_pos;
                int t = 0;
                while(pos < N){
                        t = nextTrain(C[pos],S[pos],F[pos],t);
                        //printf("pos = %d wait until t=%d\n",pos,t);
                        //printf("pos = %d departure reached to the next t=%d\n",pos,t);
                        t += C[pos];
                        pos++;
                }
                printf("%d\n",t);
        }
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a[100000]={0};
    for(int i(0);i<n;i++){
        cin>>a[i];
    }
    int two(0);
    int four(0);
    for(int i(0);i<n;i++){
        if(a[i]%4==0)four++;
        else if(a[i]%2==0)two++;
    }
    if(two>=2){
        int left = n-two;
        int div = left / 2;
        int mod = left % 2;
        if(mod>0)div++;
        if(four>=div)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    else{
        int div = n / 2;
        if(four>=div)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 640
N, K = map(int, input().split())
p = list(map(int, input().split()))

p.insert(0, 0)
for i in range(1, N+1):
    p[i] = (p[i] + 1) / 2 + p[i-1]

s = [0] * (N+1)
for i in range(N-K+1):
    s[i] = p[i+K] - p[i]

print(max(s))

Measured memory_bytes: 72116
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<iso646.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>

#define FOR(counter,initial_value,condition) for(int counter = initial_value; counter < condition;counter++)

void insertionSort(int A[], int N) {
	FOR(i, 1, N) {
		int v = A[i];
		int j = i - 1;
		while (j >= 0 and A[j] > v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j+1] = v;
	}
}

int
main()
{	
	int n;
	long long d[100] = {};
	d[0] = 2;
	d[1] = 1;
	int i = 2;
	for (std::cin >> n; i <= n; ++i) {
		d[i] = d[i - 1] + d[i - 2];
	}
	std::cout << d[n] << std::endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if(a < b){
            if(a > c){
                System.out.println(c+" "+a+" "+b);
            }else if(b < c){
                System.out.println(a+" "+b+" "+c);
            }else{
                System.out.println(a+" "+c+" "+b);
            }
        }else{
            if(a < c){
                System.out.println(b+" "+a+" "+c);
            }else if(b > c){
                System.out.println(c+" "+b+" "+a);
            }else{
                System.out.println(b+" "+c+" "+a);
            }
        }

        sc.close();
    }
}


Measured memory_bytes: 26172
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);++i)
#define alrep(i,j,n) for(int i=0;i<(n);++i)for(int j=i+1;j<(n);++j)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int MOD=1e9+7;
const long long INF = 1LL << 60;
int gcd(int a,int b) { return b ? gcd(b,a%b) : a;}
int lcm(int a,int b) { return a/gcd(a,b)*b;}
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
void printb(unsigned int v) {
  unsigned int mask = (int)1 << (sizeof(v) * CHAR_BIT - 1);
  do putchar(mask & v ? '1' : '0');
  while (mask >>= 1);
}
void putb(unsigned int v) {putchar('0'), putchar('b'), printb(v), putchar('\n');}
#define ALL(W) (W).begin(),(W).end()



signed main(){
  int N;
  cin >> N;
  for(int i=1;i<10;i++)for(int j=1;j<10;j++){
    if(N==i*j){
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b,sum,sum2=0,temp=0,var,i;
    cin>>n>>a>>b;
    for(i=1; i<=n; i++)
    {

        sum=0,temp=i;
        while(temp!=0)
        {
            var=temp%10;
            sum=sum+var;
            temp=temp/10;
        }

        if(a<=sum&& sum<=b)
        {

            sum2=sum2+i;
        }
    }
    cout<<sum2<<endl;
    return 0;
}


Measured memory_bytes: 384
// 7/1 解き直し → 6/30
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;
const int INF = 1000000007;

// 中点それ自体である時はできない。

int main() {
    double W, H, x, y;
    cin >> W >> H >> x >> y;

    double ans = W * H / 2.0;
    cout << fixed << setprecision(15);
    cout << ans << endl;

    if (2 * x == W && 2 * y == H) cout << 1 << endl;
    else cout << 0 << endl;

    return 0;
}

Measured memory_bytes: 3768
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
using ll =  long long;
int main()
{

   ll  n , k;
   cin>>n>>k;
   ll answer = 0;

   for(ll  i =k;i<=n+1;i++){
    ll mini= (i*(i-1))/2;
    ll maxi = i*n-mini;

    answer += (maxi-mini+1)%1000000007;



   }
   cout<<answer%1000000007;
    return 0;
}


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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) {
        ll d = euclid(b, a % b, y, x);
        return y -= a / b * x, d;
    }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1)
            ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1);
        return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e)
            return Mod(1);
        Mod r = *this ^ (e / 2);
        r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);

    cin >> skipws;
    for (;;) {
        int n, m; cin >> n >> m;
        swap(n, m);

        if (!n) break;

        int p0, q0;

        vector<vector<char>> mp(n, vector<char>(m, ' '));
        vector<vi> vis(n, vi(m, 0));
        
        rep(i, 0, n) rep(j, 0, m) {
            cin >> mp[i][j];
            if (mp[i][j] == '@') p0 = i, q0 = j;
        }        

        queue<pii> q;
        q.push({p0, q0});
        vis[p0][q0] = true;
        int ans = 1;

        const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!q.empty()) {
            int x, y;
            tie(x, y) = q.front(); q.pop();
            // cout << x << "  " << y << endl;
            rep(i, 0, 4) {
                int xx = x + dir[i][0], yy = y + dir[i][1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && mp[xx][yy] == '.' && !vis[xx][yy]) {
                    vis[xx][yy] = true;
                    q.push({xx, yy});
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3168
#include <algorithm>
#include <climits>
#include <vector>
#include <iostream>

using namespace std;

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

    vector<vector<long long>> A(N, vector<long long>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    long long sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            long long orig = A[i][j];
            long long via_shortest = LLONG_MAX;
            for (int k = 0; k < N; k++) {
                long long via = A[i][k] + A[k][j];
                if (via < orig) {
                    cout << -1 << endl;
                    return 0;
                } else if (k != i && k != j) {
                    via_shortest = min(via, via_shortest);
                }
            }
            if (via_shortest > orig) {
                sum += orig;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	long long n,q;
	cin >> n>>q;
	vector<vector<long long> >res(n);
	while (q--)
	{
		int op;
		cin >> op;
		if (op == 0)
		{
			long long t, q;
			cin >> t >> q;
			res[t].push_back(q);
		}
		else if (op == 1)
		{
			int t;
			cin >> t;
			for (vector<long long>::iterator it = res[t].begin(); it != res[t].end(); it++)
				if (it == res[t].begin())cout << *it;
				else cout << " " << *it;
			cout << endl;
		}
		else if (op == 2)
		{
			int t;
			cin >> t;
			res[t].clear();
		}
	}
	return 0;
}


Measured memory_bytes: 8808
#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        long ans=0;
        //printf("%d\n",n);
        for(int i=0;i<600;i+=n){
            ans+=i*i*n;
        }

        printf("%ld\n",ans);
    }
    return 0;
}

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

int main() {
    int N, A, B, C, D;
    char S[200005];

    cin >> N >> A >> B >> C >> D;
    cin >> S;

    if (B < C) {
        // A < B < C < D の配置 (Bは Aの移動の邪魔にならない)
        if (C < D) {
            int frag_ad = 1;
            for (int i = A - 1; i < D - 2; i++) {
                if (S[i] == '#' && S[i+1] == '#') {
                    frag_ad = 0;
                    break;
                }
            }
            if (frag_ad == 1) {
                cout << "Yes" << endl;
            }
            else {
                cout << "No" << endl;
            }
        }

        // A < B < D < C (Bが Aの移動の邪魔になる)
        else {
            int frag_ac = 1;
            int frag_bd = 0;
            for (int i = A - 1; i < C - 2; i++) {
                if (S[i] == '#' && S[i+1] == '#') {
                    frag_ac = 0;
                    break;
                }
            }
            for (int i = B - 2; i < D - 1; i++) {
                if (S[i] == '.' && S[i+1] == '.' && S[i+2] == '.') {
                    frag_bd = 1;
                }
            }

            if (frag_ac == 1 && frag_bd == 1) {
                cout << "Yes" << endl;
            }
            else {
                cout << "No" << endl;
            }
        }

    }

    // A < C < B < D の配置(A, Bの追い越し考慮不要)
    else {
        int frag_ac = 1;
        int frag_bd = 1;
        for (int i = A - 1; i < C - 2; i++) {
            if (S[i] == '#' && S[i+1] == '#') {
                frag_ac = 0;
                break;
            }
        }
        for (int i = B - 1; i < D - 2; i++) {
            if (S[i] == '#' && S[i+1] == '#') {
                frag_bd = 0;
                break;
            }
        }
        if (frag_ac == 1 && frag_bd == 1) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
}


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

using namespace std;

using ll = long long;
using ull = unsigned long long;

std::vector<int> PN;

void SieveOfEra(){
	int endN = 55555;
	std::vector<int> pre,next;
	for (int i = 2; i <= endN; i++) {
		pre.push_back(i);
	}
	while (pre[0] < sqrt(endN)) {
		PN.push_back(pre[0]);
		next.clear();
		for (size_t i = 0; i < pre.size(); i++) {
			if (pre[i] % pre[0] != 0) {
				next.push_back(pre[i]);
			}
		}
		pre = next;
	}
	for (size_t i = 0; i < pre.size(); i++) {
		PN.push_back(pre[i]);
	}
}



int main(int argc, char const *argv[]) {
	SieveOfEra();

	int n;
	std::cin >> n;
	int count = 0;

	for (size_t i = 0; i < PN.size(); i++) {
		if (count == n) {
			std::cout << '\n';
			return 0;
		}
		if (PN[i] % 5 == 1) {
			count++;
			std::cout << PN[i] << ' ';
		}
	}
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
typedef long long ll;

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

#include <climits>
#include <queue>
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

struct Edge{
  ll cap; // capacity
  int to;
  int rev; // reverse edge id

  Edge(){}
  Edge(ll c, int t, int r) :
    cap(c), to(t), rev(r){}
};

template<class E> // Edge type
class Graph{
public:
  typedef std::vector<std::vector<E> > G;

private:
  G g;

public:
  Graph(int n) : g(G(n)) {}

  void addEdge(int from, int to, ll cap){
    g[from].push_back(E(cap, to, g[to].size()));
    g[to].push_back(E(0, from, g[from].size() - 1));
  }

  G &getRowGraph(){
    return g;
  }
};

template<class E>
class Dinic{
  typedef typename Graph<E>::G G;
  G &g;
  std::size_t n; // size of graph

  std::vector<int> level;
  std::vector<int> iter;

  // other utilities

  // search length of shortest path from s
  void bfs(int s){
    std::queue<int> que;
    level = std::vector<int>(n, -1);

    level[s] = 0;
    que.push(s);

    while(!que.empty()){
      int v = que.front(); que.pop();
      for(int i = 0; i < (int)g[v].size(); i++){
	E &e = g[v][i];
	if(e.cap > 0 && level[e.to] < 0){
	  level[e.to] = level[v] + 1;
	  que.push(e.to);
	}
      }
    }
  }

  // search path
  ll dfs(int v, int t, ll f){
    if(v == t) return f;
    for(int &i = iter[v]; i < (int)g[v].size(); i++){
      E &e = g[v][i];
      if(e.cap > 0 && level[v] < level[e.to]){
	ll d = dfs(e.to, t, min<ll>(f, e.cap));
	if(d > 0){
	  e.cap -= d;
	  g[e.to][e.rev].cap += d;
	  return d;
	}
      }
    }
    return 0;
  }

public:
  Dinic(Graph<E> &graph) : g(graph.getRowGraph()){
    n = g.size();
  }

  // Max flow of the flow from s to t.
  ll solve(int s, int t){
    ll flow = 0;
    while(true){
      ll f;
      bfs(s);
      if(level[t] < 0) return flow;
      iter  = std::vector<int>(n, 0);
      while((f = dfs(s, t, numeric_limits<ll>::max())) > 0){
	flow += f;
      }
    }
  }
};

template<class E>
ll dinic(Graph<E> &g, int s, int d){
  return Dinic<E>(g).solve(s, d);
}



int main(){
  const int n = getInt();

  const int s = n;
  const int t = n + 1;

  Graph<Edge> g(n + 2);
  ll sum = 0;
  ll inf = 1ll << 60;

  REP(i,n) {
    const int a = getInt();

    if(a > 0) {
      g.addEdge(s, i, a);
      g.addEdge(i, t, 0);
      sum += a;
    } else {
      g.addEdge(s, i, 0);
      g.addEdge(i, t, -a);
    }

    REP(j,i) if((i + 1) % (j + 1) == 0) {
      g.addEdge(i, j, inf);
    }
  }

  printf("%lld\n", sum - dinic(g, s, t));

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String w = sc.next().toUpperCase();
		sc.close();
		int[] alp = new int[26];
		for(int i = 0;i < w.length();i++) {
			char c = w.charAt(i);
			alp[c - 65]++;
		}
		String ans = "Yes";
		for(int i = 0;i < alp.length;i++) {
			if(alp[i]%2 != 0) {
				ans = "No";
				break;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 21716
// finish date: 2019/2/22

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    int N, W;
    cin >> N >> W;
    vi w(N), v(N);
    rep(i, N) cin >> w[i] >> v[i];

    vvl dp(N, vl(1000 * N + 1, INFll));
    dp[0][v[0]] = w[0];
    ll ma = 0;
    FOR(i, 1, N) {
        dp[i][v[i]] = w[i];
        rep(j, 1000 * N + 1) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            if (j + v[i] <= 1000 * N && dp[i - 1][j] != 0) dp[i][j + v[i]] = min(dp[i][j + v[i]], w[i] + dp[i - 1][j]);
        }
    }
    rep(i, N) rep(j, 1000*N + 1) if (dp[i][j] <= W) ma = max(ma, (ll) j);
    cout << ma << endl;

    return 0;
}

Measured memory_bytes: 79488
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s=="RRR"){
        cout << 3 << endl;
    }else if(s=="RRS"||s=="SRR")
    {
        cout << 2 << endl;
    }
    else if(s=="SSS")
    {
        cout << 0 << endl;
    }
    else
    {
        cout << 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3624