akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long

template <class T>
struct BIT{
  int n;
  vector<T> bit; //[1,N]

  BIT(int _n){
    n = _n;
    bit.resize(n,0);
  }

  T sum(int i){
    T sum = 0;
    while(i > 0){
      sum += bit[i];
      i -= i & -i;
    }
    return sum;
  }

  void add(int i,T x){
    while(i < n){
      bit[i] += x;
      i += i & -i;
    }
  }
};

signed main(){

  int n,q; cin >> n >> q;
  BIT<int> bit(n+1);
  for(int i = 0; i < q; i++){
    int com,x,y; cin >> com >> x >> y;
    if(com == 0){
      bit.add(x,y);
    }
    else {
      cout << bit.sum(y) - bit.sum(x-1) << endl;
    }
  }


  return 0;
}



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

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define pb push_back
#define mp make_pair
#define SZ(a) ((int)(a.size()))
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> PI;

const int MAX_N=123456*3;
bool npr[123456*4];
int sum[123456*4];
int main(int argc, char *argv[])
{
	int dx[] = {-1, 0, 1, 0};
	int dy[] = {0, 1, 0, -1};
	int x[500], y[500];
	for(;;){
		int n;
		cin >> n;
		if(n==0){
			break;
		}
		int maxX=0, minX=0, maxY=0, minY=0;
		x[0] = y[0] = 0;
		for(int i=1;i<n;i++){
			int a, d;
			cin >> a >> d;
			x[i] = x[a] + dx[d];
			y[i] = y[a] + dy[d];
			maxX = max(maxX, x[i]);
			minX = min(minX, x[i]);
			maxY = max(maxY, y[i]);
			minY = min(minY, y[i]);
		}
		cout << (maxX - minX + 1) << " " << (maxY - minY + 1) << endl;
	}

  return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main() {
 
    ll N, min = 1000000000001;
 
    cin >> N;
 
    for(ll i = 1; i < 1000001; i++){
        if(N % i == 0){
            if(min > i + (ll)(N / i) - 2){
                min = i + (ll)(N / i) - 2;
            }
        }
    }
 
    cout << min << endl;
 
    return 0;
}

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

using namespace std;

int main()
{
	string a, b, c;
	int turn = 0;
	
	cin >> a >> b >> c;
	
	while (turn != 4) {
		if (turn == 0) {
			if (a.empty() == 1) {
				cout << "A" << endl;
				turn = 4;
			}
			else {
				turn = a[0] - 'a';
				a.erase(0, 1);
			}
		}
		if (turn == 1) {
			if (b.empty() == 1) {
				cout << "B" << endl;
				turn = 4;
			}
			else {
				turn = b[0] - 'a';
				b.erase(0, 1);
			}
		}
		if (turn == 2) {
			if (c.empty() == 1) {
				cout << "C" << endl;
				turn = 4;
			}
			else {
				turn = c[0] - 'a';
				c.erase(0, 1);
			}
		}
	}
	
	return (0);
}

Measured memory_bytes: 256
d,g = map(int,input().split())
P,C = [0]*d,[0]*d
for i in range(d): P[i],C[i] = map(int,input().split())
ans = 10**9
for bin in range(0, 1<<d):
    cnt = tot = 0
    rest_max_bit = -1
    for i in range(d):
        if bin & 1<<i:
            t = (i+1)*100
            tot += P[i]*t + C[i]
            cnt += P[i]
        else: rest_max_bit = i
    if tot >= g:
        ans = min(ans, cnt)
        continue
    if rest_max_bit < 0: continue
    t = (rest_max_bit+1)*100
    rest_g = g - tot
    p = min(P[rest_max_bit]-1, (rest_g+t-1)//t) # [0,pi-1]
    if p*t >= rest_g: ans = min(ans, cnt + p)
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <numeric>
#include <queue>
using namespace std;

int64_t min(int64_t a,int64_t b) {
    if (a > b)
    {
        return b ;
    }else
    {
        return a ;
    }
}

int main(){
    int x,y ;
    cin >> x >> y ;
    if (y % 2 == 1)
    {
        cout << "No" << endl ;
    }else {
    if (2*x <= y && y <= 4*x)
    {
        cout << "Yes" << endl ;
    }else
    {
        cout << "No" << endl ;
    }
    
    }
    
    
}


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  int cnt[100100] = {};
  for (int i = 0; i < n; i++) {
    int A;
    cin >> A;
    cnt[A]++;
  }

  int num = 0;
  if(n%2==0) {
    for (int i = 1; i < n; i += 2) {
      if (cnt[i] != 2) {
        cout << 0 << endl;
        return 0;
      }
      num++;
    }
  } else {
    for (int i = 0; i < n; i += 2) {
      if (i == 0) {
        if (cnt[i] != 1) {
          cout << 0 << endl;
          return 0;
        }
      } else {
        if (cnt[i] != 2) {
          cout << 0 << endl;
          return 0;
        }
      }
      num++;
    }
    num--;
  }

  long long ans = 1;
  for (int i = 0; i < num; i++) {
    ans *= 2;
    ans %= 1000000007;
  }

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


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

using namespace std;

#ifdef LOCAL_DEFINE
  #include "../../library/DEBUG.hpp"
#else
  #define debug(...) 0
#endif

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  long long k;
  cin >> n >> m >> k;
  vector<long long> a(n);
  vector<long long> b(m);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  vector<long long> pre1(n);
  vector<long long> pre2(m);
  int ans = 0;
  pre1[0] = a[0];
  if (pre1[0] <= k) ans = 1;
  for (int i = 1; i < n; i++) {
    pre1[i] = a[i] + pre1[i - 1];
    if (pre1[i] <= k) ans = i + 1;
  }
  pre2[0] = b[0];
  if (pre2[0] <= k) ans = max(ans, 1);
  for (int i = 1; i < m; i++) {
    pre2[i] = b[i] + pre2[i - 1];
    if (pre2[i] <= k) ans = max(ans, i + 1);
  }
  for (int i = 0; i < n; i++) {
    if (k - pre1[i] <= 0) break;
    int pos = lower_bound(pre2.begin(), pre2.end(), k - pre1[i]) - pre2.begin();
    if (pos == m || pre2[pos] > k - pre1[i]) --pos;
    ans = max(ans, i + 1 + pos + 1);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 9516
# coding: utf-8
n,a_,b_=map(int,input().split())
l=[min(a_,n-a_),min(b_,n-b_)]
a,b=min(l),max(l)
mod=10**9+7
def pow_k(x,n):
    k=1
    #kは漏れたやつ
    while n>1:
        if n%2==1:
            k*=x
            n-=1
            k=k%mod
        x**=2
        x=x%mod
        n//=2
    
    return (k * x) % mod
    
#ans=pow_k(2,1000000000)
def modcomb(n,r,mod):
    X, Y =  1, 1
    r = min(r, n-r)
    for i in range(1,r+1):
        X = X * (n-i+1) % mod
        Y = Y * i % mod
    
    return (X * pow_k(Y, mod-2) % mod) % mod
ans=pow_k(2,n)-1-modcomb(n,a,mod)-modcomb(n,b,mod)
print(ans%mod)

Measured memory_bytes: 38512
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
const int mod=1e9+7;
using LL=long long;
using std::cout;using std::endl;using std::cin;
using std::vector;using std::string;using std::set;using std::multiset;
using std::pair;using std::map;
using std::min;using std::max;

namespace ndifix{
}

int main(){
  int n,m;cin>>n>>m;
  vector<int> K(m);
  vector<vector<int>> s(m);
  for(int i=0;i<m;i++){
    cin>>K[i];
    s[i].resize(K[i]);
    for(int j=0;j<K[i];j++)cin>>s[i][j];
    std::sort(s[i].begin(),s[i].end());
  }
  vector<int> p(m);for(int i=0;i<m;i++)cin>>p[i];
  
  int ans=0;
  vector<int> buf(m);
  for(int i=0;i<(1<<n);i++){
    buf.clear();buf.resize(m);
    bool flag=1;
    for(int j=0;j<m;j++){//light
      for(int k=0;k<n;k++){//switch k
        if(i & (1<<k)){
          for(int l=0;l<K[j];l++){if(s[j][l]==k+1)buf[j]++;}
        }
      }
      if(buf[j]%2 != p[j]){flag=0;break;}
    }
    if(flag){
      ans++;
      //cout<<std::bitset<10>(i).to_string()<<endl;
    }
  }

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


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

using namespace std;
//131073
const int maxn = 223456;
typedef pair<int, int> pii;
typedef long long ll;
multiset<int>s;
multiset<int>::iterator it;

int c[12345];
int main(){
    ios_base::sync_with_stdio(0);
//    freopen("input.txt", "r", stdin);
    int x;
    int n;
    int res = 0, even = 0;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        if(x % 2 == 0)even++;
        res = 0;
        if(x % 2 == 0)
            while (x % 2 == 0){
                x /= 2;
                res ++;
            }
        sum += res;
    }
    if(!even)cout << 0 <<endl;
//    if(even >= 2)cout << sum+1 << endl;
    else cout << sum << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int n,x;
	scanf("%d",&n);
	if(n<=599&&n>=400)
	x=8;
		if(n<=799&&n>=600)
	x=7;
		if(n<=999&&n>=800)
	x=6;
		if(n<=1199&&n>=1000)
	x=5;
		if(n<=1399&&n>=1200)
	x=4;
		if(n<=1599&&n>=1400)
	x=3;
		if(n<=1799&&n>=1600)
	x=2;
			if(n<=1999&&n>=1800)
	x=1;
	printf("%d",x);
} 

Measured memory_bytes: 3136
while True:
    try:
        a = map(int, raw_input().split())
        b = map(int, raw_input().split())
        hit,blow = 0,0
        for i in range(4):
            if a[i] == b[i]:
                hit += 1
            else:
                for j in range(4):
                    if a[i] == b[j]:
                        blow += 1
        print hit, blow
    except EOFError:
        break

Measured memory_bytes: 4228
#include<iostream>
using namespace std;
int main(){
    int n,a,b;
    cin>>n;
    a=n%10,n/=10,b=n%10,n/=10;
    if(a==7||b==7||n==7)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3100
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
using namespace std;

int main(){
  int n,d; cin>>n>>d;
  if(n%(d*2+1)==0) cout<<n/(d*2+1)<<endl;
  else cout<<n/(d*2+1)+1<<endl;
  return 0;
}

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

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string str = Console.ReadLine();
                if (string.IsNullOrEmpty(str))
                {
                    return;
                }
                int n = int.Parse(str);
                int count = 0;
                for (int a = 0; a <= 9; a++)
                {
                    for (int b = 0; b <= 9; b++)
                    {
                        for (int c = 0; c <= 9; c++)
                        {
                            for (int d = 0; d <= 9; d++)
                            {
                                if (a + b + c + d == n)
                                {
                                    count++;
                                }
                            }
                        }
                    }
                }
                Console.WriteLine(count);
            }
        }
    }
}

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

using namespace std;

#define FOR(i,s, t) for(int i = s; i < t; i++)
#define ALL(a)  a.begin(), a.end()
#define SZ(x) (int)x.size()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define SORT(a) sort(ALL(a))
using VI = vector<int>;
using LL = long long;
using VVL = vector<vector<LL>>;
using VL = vector<LL>;

const LL LINF = 1e18;

int editDistance(string& s, string& t) {
	VVL dp(1010, VL(1010, 0));

	FOR(i, 0, 1010) {
		dp[i][0] = i;
		dp[0][i] = i;
	}
	FOR(i, 0, SZ(s)) {
		FOR(j, 0, SZ(t)) {
			int cost = (s[i] == t[j]) ? 0 : 1;
			dp[i + 1][j + 1] = min(dp[i][j] + cost, min(dp[i + 1][j] + 1, dp[i][j + 1] + 1));
		}
	}
	return dp[s.size()][t.size()];
}

signed main() {
	string s, t;
	cin >> s >> t;
	cout << editDistance(s, t) << endl;
}





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

// Common file
#include <ext/pb_ds/assoc_container.hpp>
// Including tree_order_statistics_node_update
#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 pb push_back
#define F first
#define S second
#define rep(i,n) for(int i = 0; i < (n); i++)

using ll = long long;
using ld = long double;
using ul = unsigned long long;
using ii = pair<int, int>;
#define Mosta     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ReadFile            freopen("input.in","r",stdin)
#define WriteFile           freopen("output.txt","w",stdout)
const ll mod7 = 1000000007,mod = 1000000000,OO = 0x3f3f3f3f;
const ld EPS = 1e-7;
double Pi=acos(-1);
const ld rad=Pi/180.0;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
            y = y>>1;
            x = (x*x) % p;
    }
    return res;
}
ll nCr (ll n,ll m)
{
    return(m == 0)?1:n*nCr(n-1,m-1)/m;
}

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

const int N = 1005;
int a[N] , n , k , ans = 0;

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

    for(int i = 0; i < n; ++i)
        cin >> a[i];

    sort(a , a + n);

    for(int i = 0; i < k; ++i)
        ans += a[i];

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define endl "\n";
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define double long double
#define M_PI 3.14159265358979323846 
const int mod = 1e9 + 7;

int32_t main()
{
    fastio;

    int n, m; cin >> n >> m;
    vector<int> edge[n+1];
    for(int i=0; i<m; i++){
    	int u, v; cin >> u >> v;
    	edge[u].push_back(v);
    	edge[v].push_back(u);
    }

    queue<int> q;
    q.push(1);
    vector<bool> visited(n+1,false);
    vector<int> ans(n+1, 0);
    visited[1] = true;
    while(!q.empty()){
    	int curr = q.front(); q.pop();
    	//cout << curr << endl;
    	for(auto v: edge[curr]){
    		if(!visited[v]){
    			visited[v] = true;
    			ans[v] = curr;
    			q.push(v);
    		}
    	}
    }

	bool flag = true;
	for(int i=1; i<n+1; i++){
		if(!visited[i]){
			flag = false;
			break;
		}
	}

	if(flag){
		cout << "Yes" << endl;
		for(int i=2; i<=n; i++) cout << ans[i] << endl;
	}else{
		cout << "No" << endl;
	}
    return 0;
}

/*
3 1 2 4
1 2 3
*/

Measured memory_bytes: 12940
n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0] * n
for i in range(n):
    for j in range(i + 1, n):
        d = min(j - i, abs(y - j) + abs(x - i) + 1)
        ans[d] += 1
for i in ans[1:]:
    print(i)



Measured memory_bytes: 74448
X,N=map(int,input().split())
A=list(map(int,input().split()))

S=[i for i in range(-1,102)]

for j in range(N):
    S.remove(A[j])
    
n=1000  
x=0
for k in S:
    if abs(k - X) < n:
        n=abs(k - X)
        x=k
    elif n == abs(k - X):
        x=min(x,k)
print(x)

Measured memory_bytes: 9128
#include<bits/stdc++.h>
using namespace std;
const int M=15;

int n,m,A[M][M];
bool ck(int x){
	int sq=sqrt(x+0.5);
	return sq*sq==x;
}

void Solve(){
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++){
			int s=0;
			for(int q=1;q<=m;q++)s+=(A[i][q]-A[j][q])*(A[i][q]-A[j][q]);
			ans+=ck(s);
		}
	printf("%d\n",ans);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&A[i][j]);
	Solve();
	return 0;
}

Measured memory_bytes: 256
// AOJ 2664: Shopping
// 2017.12.3 bal4u@uu

#include <stdio.h>
#include <string.h>

#define HASHSIZ 15013
typedef struct { char *s; int id, w; } HASH;
HASH hash[HASHSIZ+2], *hashend = hash + HASHSIZ;			// Hash table

void insert(char *s, int w, int id)
{
	HASH *tp = hash + (101 * *s + 103 * *(s+w-1) + 107 * w) % HASHSIZ;
	while (tp->s != NULL) {
		if (tp->w == w && memcmp(tp->s, s, w) == 0) return;
		if (++tp == hashend) tp = hash;
	}
	tp->s = s, tp->id = id, tp->w = w;
}

int lookup(char *s, int w)
{
	HASH *tp = hash + (101 * *s + 103 * *(s+w-1) + 107 * w) % HASHSIZ;
	while (tp->s != NULL) {
		if (tp->w == w && memcmp(tp->s, s, w) == 0) break;
		if (++tp == hashend) tp = hash;
	}
	return tp->id;
}

#define MAX 5002
/* UNION-FIND library */
int p[MAX], rank[MAX];

void make_set(int x) { p[x] = x, rank[x] = 0; }
void link(int x, int y) {
	if (rank[x] > rank[y]) p[y] = x;
	else { p[x] = y; if (rank[x] == rank[y]) rank[y] = rank[y] + 1;	}
}
int find_set(int x) { if (x != p[x]) p[x] = find_set(p[x]);	return p[x]; }
void union_set(int x, int y) { link(find_set(x), find_set(y)); }

int x[MAX];
char s[MAX][20];

char buf[30], *bp;
int getint()
{
	int n = 0;
	while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);
	return n;
}

int main()
{
	int n, m, i, j, ans;
	char *q;

	fgets(bp=buf, 10, stdin), n = getint();
	for (i = 0; i < n; i++) p[i] = i;

	for (i = 0; i < n; i++) {
		fgets(bp=s[i], 20, stdin);
		q = bp; while (*bp >= 'a') bp++;
		insert(q, bp-q, i);
		bp++, x[i] = getint();
	}

	fgets(bp=buf, 10, stdin), m = getint();
	while (m--) {
		fgets(bp=buf, 30, stdin);
		q = bp; while (*bp >= 'a') bp++;
		i = lookup(q, bp-q);

		q = ++bp; while (*bp >= 'a') bp++;
		j = lookup(q, bp-q);
		union_set(i, j);
	}

	for (i = 0; i < n; i++) {
		j = find_set(i);
		if (x[i] < x[j]) x[j] = x[i];
	}
	for (ans = 0, i = 0; i < n; i++) ans += x[p[i]];
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2020
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
long long int lcm(long long int a,long long int b){
  long long int n;
  n=a*b/__gcd(a,b);
  return n;
}
using ll =long long int;
#define ci(a) cin>>a
#define co(a) cout<<a<<endl
#define gcd(a,b) __gcd(a,b)
#define vec vector<ll>
#define For(i,a,b) for(ll i=a;i<b;i++)
#define rFor(i,a,b) for(ll i=a;i>b;i--)
#define wFor(i,a,b) for(ll i=a;i<b;i+=2)
#define wrFor(i,a,b) for(ll i=a;i>b;i-=2)
#define sort(a,b) sort(a.begin(),b.end())
#define reverse(a,b) reverse(a.begin(),b.end())
//gcd 最大公約数
//lcm 最小公倍数
//double 少数（変数）
//string 文字列（変数）
//sqrt 平方根
//ceil 天井関数
//floor 床関数
//abs 絶対値
//pow 累乗
//cbrt  立方根
//hypot 平方和の平方根
//(string-'0') 文字列を数字に変換
//(char-'0') 数字に変換
//vector<vector<int>> data(a,vector<int>(b)) a×b行列
//for(int i=0;i<a;i++)
//for(int j=0;j<b;j++)
//cin>>data.at(i).at(j)  a×b行列の入力
//floor(log10(a)+1) aの10進法での桁数
//ceil(log10(a)) aの10進法での桁数

int main() {
  int a,b;
  ci(a>>b);
  co(max(a-b,0));
}


Measured memory_bytes: 256
def pad(b,N):
    b = "0"*(N-len(b)) + b
    return b

def cal(A):
    N = len(A)
    for i in range(2**(N-1)):
        b = list(pad(bin(i)[2:],N-1))
        for j in range(N-1):
            if b[j] == "1":
                b[j] = "+"
            else:
                b[j] = "-"
        s = A[0]
        for j in range(N-1):
            if b[j] == "+":
                s += A[j+1]
            else:
                s -= A[j+1]
        if s == 7:
            output = str(A[0])
            for j in range(N-1):
                output += b[j]
                output += str(A[j+1])
            output += "=7"
            return output

def main():
    A = list(map(int,input()))
    print(cal(A))

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>

using namespace std;


int main() {
	int i, j, k;
	string str;

	cin >> str;

	if (str[0] == str[2]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}






	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
from collections import deque

icase=0
if icase==0:
    r,c=map(int,input().split())
#    xy=[[[0] for i in range(c+2)] for i in range(r+2)]
#    xy=[[-1] *(c+2) for i in range(r+2)]
#    for i in range(1,r+1):
#        xy[i]=[-1]+list(map(int,input().split()))+[-1]
    xy=[["#"] *(c+2) for i in range(r+2)]
    for i in range(1,r+1):
        xy[i]=["#"]+list(input())+["#"]
elif icase==1:
    c,r=3,3       
    xy=[["#","#","#","#","#"],
        ["#",".",".","#","#"],
        ["#","#",".",".","#"],
        ["#",".",".",".","#"],
        ["#","#","#","#","#"]]

sc=[0,1,-1,0]
sr=[1,0,0,-1]
        
g=[[[] for j in range(c+2)] for i in range(r+2)]

for ri in range(1,r+1):
    for ci in range(1,c+1):
        if xy[ri][ci]==".":
            for i in range(4):
                if xy[ri+sr[i]][ci+sc[i]]==".":
                    g[ri][ci].append((ri+sr[i],ci+sc[i]))

#-----------------------------------------
sy,sx=1,1
gy,gx=r,c
#xy[sy][sx]=-1
q=deque()
q.append((sy,sx))

parent=[[-1]*(c+2) for i in range(r+2)]
parent[sy][sx]=0
dist=[[-1]*(c+2) for i in range(r+2)]
dist[sy][sx]=1
yn=""
while q:
    sty,stx = q.popleft()
    for vy,vx in g[sty][stx]:
        xy[vy][vx]=-1
        if vy==gy and vx==gx:
            parent[vy][vx]=(sty,stx)
            dist[vy][vx]=dist[sty][stx]+1
            yn="yes"
            break
        elif parent[vy][vx] !=-1:
            continue
        else:
            parent[vy][vx]=(sty,stx)
            dist[vy][vx]=dist[sty][stx]+1
            q.append((vy,vx))
#            print(q0)
    if yn=="yes":
        break

if yn!="yes":
    print(-1)
else:
    icnt=0
    for ri in range(1,r+1):
        for ci in range(1,c+1):
            if xy[ri][ci]=="." or xy[ri][ci]==-1:
                icnt+=1
    print(icnt-dist[gy][gx])    
#-----------------------------------------


Measured memory_bytes: 4468
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
ll INF = 1001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N),B(N+1);
    rep(i,N){
        cin >> A[i];
        B[i+1] = B[i] + A[i];
    }
    ll ans = 0;
    map<ll,ll> mp;
    rep(i,N+1){
        ans += mp[B[i]];
        mp[B[i]]++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 15872
n = input()
N = int(n)

digit = int(len(n))

odd_number = 0

# 1-9(10-99)100-999(1000-9999)10000-99999(100000-999999)1000000
# １桁（２桁）３桁（４桁）５桁（６桁）７桁

for i in range(1 , digit+1):
    if i % 2 == 1 and i != digit:
        odd_number += 10**i - 10**(i-1)
    if i % 2 == 1 and i == digit:
        odd_number += N - 10**(i-1) + 1

print(odd_number)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int N,A[2000];
long ans,K,mod=1e9+7;
main()
{
	cin>>N>>K;
	for(int i=0;i<N;i++)cin>>A[i];
	for(int i=0;i<N;i++)
	{
		long cnt=0,t=0;
		for(int j=0;j<N;j++)if(A[j]>A[i])cnt++,t+=j<i;
		ans+=K*(K-1)/2%mod*cnt%mod+t*K%mod;
		ans%=mod;
	}
	cout<<ans<<endl;
}

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

int main() {
	int a[100];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int cnt = 1;
	int now = a[0];
	for (int i = 0; i < n; i++) {
		if (a[i] != now) {
			cnt++;
		}
		now = a[i];
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
class Cell:
    def __init__(self, x):
        self.x = x
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.start = Cell(None)
        self.start.next = None
        self.start.prev = None

    def InsCell(self, x):
        new = Cell(x)
        if self.start.next != None:
            new.next = self.start.next
            self.start.next.prev = new
        else:
            self.start.prev = new
            new.next = self.start
        self.start.next = new
        new.prev = self.start

    def DelCell(self, x):
        tmp = self.start
        while tmp.x != x:
            if tmp.next == self.start:
                return
            tmp = tmp.next
        tmp.prev.next = tmp.next
        tmp.next.prev = tmp.prev
        tmp = None

    def DelFisrtCell(self):
        tmp = self.start.next
        if tmp.next == self.start:
            self.start.next = None
            self.start.prev = None
        else:
            self.start.next = tmp.next
            tmp.next.prev = self.start
        tmp = None

    def DelLastCell(self):
        tmp = self.start.prev
        if tmp.prev == self.start:
            self.start.next = None
            self.start.prev = None
        else:
            self.start.prev = tmp.prev
            tmp.prev.next = self.start
        tmp = None

    def PrintCell(self):
        ans = []
        tmp = self.start.next
        if tmp == None:
            print("")
        else:
            while tmp != self.start:
                ans.append(tmp.x)
                tmp = tmp.next
            print(" ".join(ans))

import sys
input = sys.stdin.readline

n = int(input())
l = DoublyLinkedList()

for _ in range(n):
    c = input().split()
    if c[0] == "insert":
        l.InsCell(c[1])
    elif c[0] == "delete":
        l.DelCell(c[1])
    elif c[0] == "deleteFirst":
        l.DelFisrtCell()
    elif c[0] == "deleteLast":
        l.DelLastCell()

l.PrintCell()



Measured memory_bytes: 227596
import sys

def warn(*m):
    print(m, file=sys.stderr)

D,*CS = map(int, open(0).read().split())
C = CS[:26]
S = [CS[26*i:26*(i+1)] for i in range(1, D+1)]

def imax(xs):
    m = -1
    i = 0
    for j, x in enumerate(xs):
        if x > m:
            i = j
            m = x
    return i

def ratio(xs):
    s = sum(xs)
    return [x / s for x in xs]

ds = [0] * 26

def pick(d, w):
    ss = ratio(S[d])
    cc = ratio([(1 + d - ds[i]) * x for i, x in enumerate(C)])
    return imax([(s * w) * c for s, c in zip(ss, cc)])

w = 0.5
for d in range(D):
    i = pick(d, w)
    w += (1 / 365)
    ds[i] = d + 1
    print(i + 1)

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

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;

int main() {
  
  int a,b,c,d,x;
  long long la,lb;
  double da,db;
  string s,ss,sss;
  
  int ans = 0;
  string anss = "";
  
  cin >> a;
  
  int ab [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
  int result3 = std::max({a, b, c});
//--------------------------------------------------------------------------------

  //if(a > 9 || b > 9) ans = -1;
  //else ans = a*b;

  cout << a*a << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll x,y,z;
    ll a;
   
    vector<set<int> > v(3);
    cin>>x;
    for(int i=0;i<x;i++){
        cin>>a;
        v[0].insert(a);
    }
    cin>>y;
    for(int i=0;i<y;i++){
        cin>>a;
        v[1].insert(a);
    }
    cin>>z;
    for(int i=0;i<z;i++){
        cin>>a;
        v[2].insert(a);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(((v[0].count(i)==0)&&(v[2].count(i)))||((v[1].count(i))&&(v[2].count(i)))){
            ans++;
        }
    }
    cout << ans<<endl;
    


    return 0;
}




Measured memory_bytes: 3212
from itertools import product

N,M,X = map(int,input().split())

books = tuple(tuple(map(int,input().split())) for _ in range(N))

def it():
    for choice in product(range(2),repeat=N):
        cost = 0
        skills = [0]*M
        for flag,book in zip(choice,books):
            if flag:
                C, A = book[0], book[1:]
                cost += C
                for i,a in enumerate(A):
                    skills[i] += a

        if all(v >= X for v in skills):
            yield cost

best = min(it(), default=None)
print(-1 if best is None else best)

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

int main(){
    string s;
    cin>>s;
    if(s[s.size()-1]=='0'||s[s.size()-1]=='1'||s[s.size()-1]=='6'||s[s.size()-1]=='8'){
        cout<<"pon"<<endl;
    }
    else if(s[s.size()-1]=='3'){
        cout<<"bon"<<endl;
    }
    else cout<<"hon"<<endl;
    return 0;
}

Measured memory_bytes: 3628
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();
        String s = "";
        int l = 0;
        int x = 0;
        int ans = 0;

        for(int i=A; i<=B; i++){
            s = String.valueOf(i);
            l = s.length();
            if(l%2==0){
                for(int j=0; j<l/2; j++){
                    if(s.charAt(j)==s.charAt(l-1-j)){
                        x += 1;
                    }
                    else{
                        break;
                    }
                    if(x==l/2){
                        ans += 1;
                    }
                }
                x = 0;
            }
            else{
                for(int j=0; j<l/2; j++){
                    if(s.charAt(j)==s.charAt(l-1-j)){
                        x += 1;
                    }
                    else{
                        break;
                    }
                    if(x==(int)l/2){
                        ans += 1;
                    }
                }
                x = 0;
            }
        }
        System.out.println(ans);
    } 
}

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

int main() {
    int t ;
    int c=0,c1=0,c2=0,c3=0;
    cin>>t;
    while(t--)
    {
        
        string str;
        cin>>str;
        if(str.length()==2){
            if(str[0]=='A')
            c++;
            else if(str[0]=='R')
            c1++;
            else if(str[0]=='W')
            c2++;
            else
            break;
        }
        else
        c3++;
    }
        cout<<"AC x "<<c;
        cout<<"\nWA x "<<c2;
        cout<<"\nTLE x "<<c3;
        cout<<"\nRE x "<<c1;
    
        
    
	return 0;
}


Measured memory_bytes: 3620
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()

d=defaultdict(list)
n=int(input())

for s in range(n-1):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])
#defaultdict(<class 'list'>, {1: [[2, 1], [3, 1]], 2: [[1, 1], [3, 3]], 3: [[1, 1], [2, 3]]})

def DIJKSTRA(point,d):
    cost      = {node:float("inf") for node in d.keys()}
    Q         = []  #頂点のリスト
    cost[point]=0  #開始地点のコストをゼロとする（当たり前
    heappush(Q,(point,cost[point]))
    while Q:
        prefnd,tmpC=heappop(Q)
        if cost[prefnd]<tmpC:
            continue
        for node,c in d[prefnd]:
            altC=c+tmpC
            if cost[node]>altC:
                cost[node]=altC
                heappush(Q,(node,altC))
    return cost

q,k=map(int,input().split())
y=DIJKSTRA(k,d)

for i in range(q):
    a,b=map(int,input().split())
    print(y[a]+y[b])

Measured memory_bytes: 110300
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
#define Mod 1e9+7
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
LL n,k;
int a[41],ma;
LL data[Max];
void fun(LL x)
{
	int i=0;
	while(x)
	{
		a[i]+=x%2;
		x/=2;
		i++;
	}
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&data[i]);
		fun(data[i]);
	}
	int mi=Max;
	LL f=k;
	while(f)
	{
		ma++;
		f/=2;
	}
	LL ans=0,t=0;
	for(int i=40;i>=0;i--)
	{
		t=i==0?1:pow(2,i);
		if(a[i]>=(n-a[i]))
		{
			ans+=a[i]*t;
		}
		else
		{
			if(k>=t)
				ans+=(n-a[i])*t,k-=t;
			else
				ans+=a[i]*t;
		}
	}
	printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 1024
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    x,y = map(int, readline().split())

    ans = 0

    d = {}
    d[1] = 300000
    d[2] = 200000
    d[3] = 100000

    if x in d:
        ans += d[x]
    
    if y in d:
        ans += d[y]

    if x == 1 and y == 1:
        ans += 400000
    
    print(ans)
    

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <stdio.h>

int main() {
    int c[3][3], b[2][3];
    int i, j, flag=1;
    for(i=0; i<3; i++) {
        for(j=0; j<3; j++) {
            scanf("%d", &c[i][j]);
            if(i>0) {
                b[i-1][j] = c[i][j] - c[i-1][j];
                if(j>0) {
                    if(b[i-1][0]!=b[i-1][j]) {
                        flag = 0;
                    }
                }
            }
        }
    }

    if(flag) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
    
}

Measured memory_bytes: 128
def countingSort(A,n,k):
    B = [0]*(n)
    C = [0]*(k+1)

    for i in A:
        C[i] += 1
    
    for i in range(1, k):
        C[i] += C[i-1]
    
    for a in reversed(A):
        B[C[a]-1] = a
        C[a] -= 1

    return B

def main():
    n = int(input())
    A = list(map(int, input().split()))

    B = countingSort(A,n,10000)

    print(*B)
             
if __name__ == "__main__":
    main()


Measured memory_bytes: 224504
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, a; cin >> n >> a;
  cout << n * n - a << '\n';
}

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

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef vector<pii> vpii;
typedef vector<pil> vpil;
typedef vector<pli> vpli;
typedef set<int> si;
typedef set<ll> sll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;

const double pi = acos(-1.0);
const long long INF = 2e18;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz size()
#define in insert
#define endl "\n"

#define sqr(a) ((a) * (a))
#define jor(a) !(a&1)// jor means EVEN number
#define bjor(a) (a&1)// bjor means ODD number

#define all(a)  a.begin(), a.end()
#define mem(arr, b) memset(arr, b, sizeof(arr)) //memset only for -1 and 0
//fill(a, a+n, 5) //fill for any value

#define for0(i,b) for(int i=0;i<(b);i++)
#define for1(i,b) for(int i=1;i<=(b);i++)
#define forab(i,a,b) for(int i=(a);i<=(b);i++)
#define forba(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))

#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fileRead freopen("input.txt", "r", stdin);
#define fileWrite freopen("output.txt", "w", stdout);

void print(int a[], int n){ // for testing or debugging
    for(int i=0;i<n;i++)cout<<a[i]<<" "; cout<<endl;
}

#define watch(x) cout << (#x) << " is " << (x) << endl

//-------------------------------------------------------------------
#define mx 100000+1

vi v[mx];
bool vis[mx];

void dfs(int s)
{
    if(vis[s]) return;
    else{
        vis[s] = 1;
        for(auto t: v[s]) if(vis[t]==0) dfs(t);
    }
}

int main()
{
    int tc=1;
    //cin>>tc;
    while(tc--){
        int n; cin>>n;
        int e; cin>>e;
        
        for0(i,e){
            int x; cin>>x; int y; cin>>y;
            v[x].pb(y); v[y].pb(x);
        }

        int ans=0;
        for1(i,n){
            if(vis[i]==0) ans++,dfs(i);
        }

        cout<<ans-1;
    }
}

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

int n, m;
string str;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	str = string(n + 1, 'x');
	for(int i = 0; i < m; i++){
		int s, c;
		cin >> s >> c;
		if(str[s] == 'x') str[s] = '0' + c;
		else if(str[s] != '0' + c){
			cout << "-1\n";
			return 0;
		}
	}
	if(str == "xx" || str == "x0"){
		cout << "0\n";
		return 0;
	}
	int pos = false;
	for(int i = 1; i <= n; i++)
		if(!pos && str[i] == '0'){
			cout << "-1\n";
			return 0;
		}else if(str[i] != 'x' && str[i] != '0') pos = true;
		else if(pos && str[i] == 'x') str[i] = '0';
		else if(!pos && str[i] == 'x') str[i] = '1', pos = true;
	if(!pos) cout << "-1\n";
	else cout << str.substr(1) << "\n";
	return 0;
}

Measured memory_bytes: 256
N = int(input())
cards = list(map(int, input().split()))

cards.sort(reverse = True)
sum_A = 0
sum_B = 0


for i in range(N):
    if i % 2 == 0:
        sum_A += cards[i]
    else:
        sum_B += cards[i]

print(sum_A - sum_B)

Measured memory_bytes: 3060
X = int(input())

q, r = divmod(X, 500)

v = 0

if q == 0:
    q, r = divmod(X, 5)
    v += 5 * q
else:
    v += 1000 * q
    q, r = divmod(r, 5)

    v += 5 * q

print(v)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int main() {
  int W, H;
  int flg,flg2;
//　配列サイズの読み込み
  cin >> H >> W;
   vector<vector<char>> A(H,vector<char>(W));
//  配列データの読み込み
  for (int i = 0; i < H; i++) {
	for (int j = 0; j < W; j++) {
	  cin >> A.at(i).at(j);
    }
  }
//  配列要素を表示すべきか、横と縦に#があるかをチェック
  for (int i = 0; i < H; i++) {
	flg2 = 0;
    for (int j = 0; j < W; j++) {
    	flg = 0;
      	for (int k = 0; k < H; k++) {
        	if (A.at(k).at(j) == '#') {
          		flg++;
		     	break;
        	}
		}
      	for (int k = 0; k < W; k++) {
        	if (A.at(i).at(k) == '#') {
          		flg++;
		        break;
        	}
	    }
      	if (flg == 2) {
        	cout << A.at(i).at(j);
	        flg2 = 1;
    	}
    }
    if (flg2 == 1) {
		cout << endl;
    }
  }
}

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

using namespace std;

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

    vector <int> data(N);
    for(int i=0; i<N; i++){
        cin >> data[i];
    }
    
    float sum = 0;
    for(int i=0; i<N; i++){
        sum += 1.0/data[i];
    }
    cout << 1.0/sum << endl;
}

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

typedef pair<int, int> P;
const int N = (int)1e5 + 50, INF = (int)1e9;

int n, m;
map<int, vector<int> > G[N];
set<int> rem[N];
int dis[N];

deque<P> que;

void dfs(int v, int color, int d) {
//    printf("in %d , color: %d\n", v, color);
    rem[v].erase(color);
    if(d < dis[v]) {
        dis[v] = d;
        que.push_back({v, color});
    }
    for(int nxt : G[v][color]) {
        if(rem[nxt].find(color) != rem[nxt].end()) {
//            printf("from %d to %d\n", v, nxt);
            dfs(nxt, color, d);
        }
    }
}

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

    cin >> n >> m;
    fill(dis, dis + n, INF);
    for(int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c; a--, b--, c--;
        G[a][c].push_back(b);
        G[b][c].push_back(a);
        rem[a].insert(c);
        rem[b].insert(c);
    }
    while(!rem[0].empty()) dfs(0, *rem[0].begin(), 1);
//    for(int i = 0; i < n; i++) {
//        printf("dis %d: %d\n", i + 1, dis[i]);
//    }
    while(!que.empty()) {
        P p = que.front();
        int v = p.first, c = p.second;
        que.pop_front();
        while(!rem[v].empty()) {
            dfs(v, *rem[v].begin(), dis[v] + 1);
        }
    }
    if(dis[n-1] == INF) dis[n-1] = -1;
    cout << dis[n - 1] << endl;
}

Measured memory_bytes: 72832
#include <bits/stdc++.h>
    using namespace std;
    int main(){
    char a[20]="CODEFESTIVAL2016";
    char s[20];
    int b=0;
    cin>>s;
    for(int i=0;i<16;i++)
    if(a[i]!=s[i])
    b++;
    cout<<b<<endl;
    return(0);
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVVld = vector<VVld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}


int main() {
  int N; cin >> N;
  Vll a(N);
  rep(i, N) cin >> a[i];
  Vll cum(N+1);
  rep(i, N) cum[i+1] = cum[i] + a[i];

  VVll dp(N+1, Vll(N+1));

  rep2(d, 1, N) rep(i, N) {
    int j = i+d+1;
    if (j > N) continue;

    ll sub = INFll;
    rep2(k, i+1, j) chmin(sub, dp[i][k] + dp[k][j]);
    dp[i][j] = sub + cum[j] - cum[i];
  }

  ll ans = dp[0][N];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1536
from collections import deque
import numpy as np
def main():
    H,W = map(int,input().split())
    maze = [input() for _ in range(H)]

    ans = 0
    for x in range(H):
        for y in range(W):
            #壁からはスタートできない
            if maze[x][y] == "#":
                continue

            #初期化
            distance = [[0]*W for _ in range(H)]
            #start位置
            stack = deque([[x,y]])

            while stack:
                h,w = stack.popleft()
                for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    new_h, new_w = h+i, w+j
                    if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                        continue
                    elif maze[new_h][new_w] != '#' and distance[new_h][new_w] == 0:
                        distance[new_h][new_w] = distance[h][w] + 1
                        stack.append([new_h, new_w])

            distance[x][y] = 0
            ans = max(ans, np.max(distance))

    print(ans)

main()

Measured memory_bytes: 27280
// AOJ 0254: Scone
// 2017.9.12 bal4u@uu
// 2017.11.12

#include <stdio.h>
#include <string.h>

int s[30003], f[100002];
char buf[330010], *p;

int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int n, m, i, a, ans, max;
	long long sum;

	while (fgets(p=buf, 20, stdin) && *p != '0') {
		n = getint(), p++, m = getint();
		memset(f, -1, sizeof(int)*m);
		fgets(p=buf, sizeof(buf), stdin);
		for (sum = 0, max = ans = s[0] = 0, i = 1; i <= n; i++) {
			a = getint(), p++;
			sum += a; a %= m; if (a > max) max = a;
			if (a == m-1) ans = a;
			if ((s[i] = s[i-1] + a) >= m) s[i] -= m; f[s[i]] = i;
		}
		if (ans > 0) goto Done;
		if (max == 0) { ans = 0; goto Done; }
		if (sum < m) { ans = (int)sum; goto Done; }
		for (ans = m-1; ans > max; ans--) {
			for (i = 0; i <= n; i++) {
				if ((a = s[i] + ans) >= m) a -= m;
				if (f[a] >= i) goto Done;
			}
		}
Done:	printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;

const int inf = 1 << 30;

int main()
{
	int N;
	cin >> N;
	vector<int> h(N);

	for (auto &x : h) {
		cin >> x;
	}

	vector<int> dp(N, inf);

	dp[0] = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N && j <= i + 2; ++j) {
			dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
		}
	}

	cout << dp[N - 1] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using namespace std;
 
#define PB(x)	push_back(x)
#define ALL(x)	(x).begin(), (x).end()
#define ALLR(x) (x).rbegin(), (x).rend()
#define MP(x)	make_pair(x);
    
#define debug(x) 		cerr << #x << '=' << x << endl;
#define debug2(x, y)	cerr << #x << '=' << x << ' ' << #y << '=' << y << endl;
#define debugn(a)		cerr << #a << ": "; for (auto x: a) cerr << x << ' '; cerr << endl;
#define debugm(a) 		cerr << #a << ":\n"; \
						for (auto v: a) { for(auto x: v) cout << x << ' '; cerr << "\n"; }
 
#define int long long
 
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<string> vs;
typedef unsigned long long ull;
 
const int INF  = LONG_LONG_MAX;
const int NINF = LONG_LONG_MIN;
const int mmod = 1000000007;

int32_t main()
{
	string s;
	cin >> s;
	
	int cnt = 0;
	for (int i = 0; i < (int)s.size()/2; i++) {
		if (s[i] != s[(int)s.size()-i-1])
			cnt++;
	}
	cout << cnt << endl;
}
// g++ -Wall -Wextra -Wshadow -fsanitize=undefined 


Measured memory_bytes: 256
#include <stdio.h>

int parts[605], t[1005][4];

int main(void)
{
	int n, i, j;
	int a, b, c, sum;
	
	while (1){
		
		scanf("%d %d %d", &a, &b, &c);
		
		sum = a + b + c;
		
		if (sum == 0) break;
		
		for (i = 0; i < sum; i++) parts[i] = 2;
		
		scanf("%d", &n);
		
		for (i = 0; i < n; i++){
			scanf("%d %d %d %d", &t[i][0], &t[i][1], &t[i][2], &t[i][3]);
			
			t[i][0]--; t[i][1]--; t[i][2]--;
			
			if (t[i][3] == 1){
				parts[t[i][0]] = 1;
				parts[t[i][1]] = 1;
				parts[t[i][2]] = 1;
			}
		}
		for (i = 0; i < n; i++){
			
			if (t[i][3] == 0 && parts[t[i][0]] == 1 && parts[t[i][1]] == 1) parts[t[i][2]] = 0;
			if (t[i][3] == 0 && parts[t[i][2]] == 1 && parts[t[i][0]] == 1) parts[t[i][1]] = 0;
			if (t[i][3] == 0 && parts[t[i][1]] == 1 && parts[t[i][2]] == 1) parts[t[i][0]] = 0;
		}
		for (i = 0; i < sum; i++) printf("%d\n", parts[i]);
	}
	
	return (0);
}
		
		

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

using namespace std;

#define ll long long
#define pii pair<int,int>
#define MAX 1000000000

vector<pii> dir{{-1,0},{1,0},{0,-1},{0,1}};

bool isvalid(int i,int j,int n,int m)
{
    if(i >=0&&i<n&&j>=0&&j<m)
    {
        return true;
    }
    return false;
}

int main()
{
    int n,m;
    cin>>n>>m;
    pii start,end;
    cin>>start.first>>start.second;
    start.first--;
    start.second--;
    cin>>end.first>>end.second;
    end.first--;
    end.second--;
    vector<vector<char>> board(n,vector<char>(m));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>board[i][j];
        }
    }
    vector<vector<int>> dist(n,vector<int>(m,MAX));
    dist[start.first][start.second] = 0;
    deque<pii> que;
    que.push_front(start);
    while(!que.empty())
    {
        pii curr = que.front();
        que.pop_front();
        for(int id =0;id <4;id++)
        {
            int newx = curr.first + dir[id].first;
            int newy = curr.second + dir[id].second;
            if(isvalid(newx,newy,n,m)&&board[newx][newy] == '.')
            {
                if(dist[newx][newy] > dist[curr.first][curr.second])
                {
                    dist[newx][newy] = dist[curr.first][curr.second];
                    que.push_front({newx,newy});
                }
            }
        }
        for(int i=-2;i<3;i++)
        {
            for(int j=-2;j<3;j++)
            {
                int newx = curr.first + i;
                int newy = curr.second + j;
                if(isvalid(newx,newy,n,m)&&board[newx][newy] == '.')
                {
                    if(dist[newx][newy] > dist[curr.first][curr.second] + 1)
                    {
                        dist[newx][newy] = dist[curr.first][curr.second] + 1;
                        que.push_back({newx,newy});
                    }
                }
            }
        }
    }
    // cout<<"test";
    if(dist[end.first][end.second] >= MAX)
        cout<<-1;
    else
    cout<<dist[end.first][end.second]<<endl;
}

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

using namespace std;

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

  int a, b, k;
  cin >> a >> b >> k;
  --k;

  bool ok = true;
  if (a + k >= b - k) {
    ok = false;
  }
  for (int i = a; i <= b; ++i) {
    if (ok && i > a + k && i < b - k) {
      i = b - k - 1;
      continue;
    }
    cout << i << '\n';
  }

  return 0;
}


Measured memory_bytes: 3648