akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
long long c[200006]={0},d,n,j,k,i,l,t=0,ma=0;
struct bian{
	long long x,h;
}b[200006];
bool cmp(bian a,bian b)
{
	return a.x<b.x;
}

int main()
{
	scanf("%lld%lld%lld",&n,&d,&j);
	d=d*2;
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&b[i].x,&b[i].h);
		b[i].h=(b[i].h+j-1)/j;
	}
	sort(b +1,b+n+1 ,cmp);
	queue<long long> q;
	map<long long , long long> m;
	for(i=1;i<=n;i++)
	{
		if(t)
		while(!q.empty())
	    {
	    	if(q.front()<b[i].x)
	    	{
				t-=m[q.front()];
				q.pop();
			}
			else break;
		    
	    }
	    		if(t<b[i].h)
	    		{
					ma+=b[i].h-t;	
					q.push(b[i].x+d);
					m[b[i].x+d]=b[i].h-t;
					t=b[i].h;
					
				}
			
	}
	printf("%lld",ma);

}

Measured memory_bytes: 16896
from sys import stdin
from math import log10
def LI(): return list(map(int,stdin.readline().rstrip().split()))

tmp = LI()
n,a,b = [tmp.pop(0) for _ in range(3)]

ans = 0

for i in range(1,n+1):
    tmp = i
    x = 0
    for _ in range(int(log10(i)+1)):
        x+=tmp%10
        tmp = tmp//10
    if a<=x and x<=b:
        ans+=i
print(ans)

Measured memory_bytes: 3316
#include<iostream>

int main(){
  int N;
  std::cin >> N;
  int A[200010] = {0};
  long long ans = 0;
  for (int i=1;i<=N;i++) {
    std::cin >> A[i];
  }
  if (A[1]>0) ans = -1;     //要素1は必ず０ではなくてはならない

  for (int i=2;i<=N;i++) {
    if (ans==-1) break;

    if (A[i]-A[i-1]==1) {
      ans++;
    }
    else if (A[i]<=A[i-1]) {
      ans+=A[i];
    } else {
      ans=-1;
    }
  }

  std::cout << ans << '\n';

}


Measured memory_bytes: 1024
#include<iostream>
#include<fstream>
#include<sstream>

using namespace std;

template <typename T> std::string tostr(const T& t){
    std::ostringstream os; os<<t; return os.str();
}

int main(){
    int n, m;
    string ns, ms;
    int l = 0, u = 1000000;
    int cnt = 0;
    string str;

    while(cin >> ns >> ms){
        cnt++;
        if(cnt >= 200) break;
        sscanf(ns.c_str(),"%d",&n);
        sscanf(ms.c_str(),"%d",&m);
        if(l<= n && n <= u && l <= m && m <= u){
            cout << tostr(n+m).size() << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ll long long int
using namespace std;
ll ans = 0, sum = 0, n, k, counter = 0, w, h;
string s;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(50, vector<ll>(50, INF));

int main()
{
	ll m;
	ll bene = 0;
	cin >> n >> m;
	v.resize(n);
	REP(i, n) cin >> v[i];
	ll mini=v[0];
	FOR(i,1,v.size())
	{
		if (mini > v[i]) mini = v[i];
		else
		{
			if (bene == v[i] - mini) ans++;
			else if (bene < v[i] - mini) {
				ans = 1;
				bene = v[i] - mini;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int c=0, i, j, k, f, r;
		for(i=0;i<n;i++){
			String t = sc.next();
			for(j=0;j<t.length();j++){
				for(k=1;;k++){
					if(t.length() <= j+k*(s.length()-1)){
						break;
						}
					f = 1;
					for(r=0;r<s.length();r++){
						if(s.charAt(r)!=t.charAt(j+k*r)){
							f = 0;
							break;
							}
						}
					if(f==1){
						c = c + 1;
						j = t.length();
						break;
						}
					}
				}
			}
		System.out.println(c);
		}
	}

Measured memory_bytes: 20592
#include <bits/stdc++.h>
using namespace std;
int Salto[100011]  , costos[100011];
 
int main() {
	int n  , k ; 	
	cin>>n;
	cin>>k;
	for (int i =0 ; i<n ; ++i) {
		cin >> Salto[i]; 
	}
	costos[0] = 0 ;
	for (int i =1 ; i<n ; ++i){
		costos[i] = 1e9 ; 
	}
	for (int i = 1 ; i<n ; ++i){
		for (int j = i-1 ; j>=max(0 , i-k) ; --j){
			int minimizar = abs(Salto[i]- Salto[j]) ;
			costos[i] = min(costos[i] , minimizar+costos[j]) ;  
		}
	}
	cout<< costos[n-1]<< endl; 
	return 0;
}

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

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

  int n;
  cin >> n;
  int a, b;
  int d[300005] = {};

  int ma = 0;
  for(int i = 0;i < n;++i){
    cin >> a >> b;
    ++d[a + b];
    ma = max(ma, a + b);
  }

  for(int i = 0;i <= 300000;++i){
    d[i + 1] += (d[i] / 2);
    d[i] %= 2;
  }

  for(int i = 0;i <= 300000;++i){
    if(d[i] == 1){
      cout << i << " 0" << endl;
    }
  }

  return 0;
}



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

using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
#define INF 1e9

 
int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    
    int x = 0;
    int cnt = 0;
    rep(i,n) {
        if(a[i] == x+1){
            x++;
            cnt++;
        }
    }
    if(cnt == 0){
        cout << -1 << endl;
        return 0;
    }
    
    cout << n-cnt << endl;
    
    
}


Measured memory_bytes: 1024
import sys
import itertools as it


N = int(sys.stdin.readline().strip())

M = 10 ** 9 + 7


def pow(x, n):
    if n == 0:
        return 1
    ret = pow(x, n // 2)
    if n % 2 == 0:
        return (ret * ret) % M
    else:
        return (ret * ret * x) % M


ret = pow(10, N) - 2 * pow(9, N) + pow(8, N)
print(ret % M)


Measured memory_bytes: 9200
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define PI 3.1415926535897932384626433
#define ceil1(a,b)   (a+(b-1))/b
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define base ios_base::sync_with_stdio(false);cin.tie(0);
#define open freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
using namespace std;
const int mo=1e9+7;
int nxt(){int x;cin>>x;return x;}
int mod(int n,int m){int ans=n%m;if(ans<0)ans+=m;return ans;}
int32_t main(){
    base
    string s,t;
    cin>>s>>t;
    int Min=1e18;
    for(int i=0;i<=s.size()-t.size();i++){
        int cnt=0;
        for(int j=0;j<t.size();j++){
            cnt+=s[i+j]!=t[j];
        }
        Min=min(Min,cnt);
    }
    cout<<Min;
    return 0;
}


Measured memory_bytes: 3660
#include <algorithm>
#include <vector>

#include <math.h>
#include <stdio.h>

using namespace std;

typedef long long ll;

#define MAX_N 100
#define DIST_TWICE(x, y) ((x) * (x) + (y) * (y))

class Point {
    public:
        ll x;
        ll y;
};

int n;
vector<Point> rockets(MAX_N * 2);

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

    for (int i = 0; i < n; i++) {
        ll x, y;
        scanf("%lld", &x);
        scanf("%lld", &y);
        rockets[i].x = x;
        rockets[i].y = y;
    }

    sort(&rockets[0], &rockets[n], [](const Point &a, const Point &b) {
            return atan2(a.y, a.x) < atan2(b.y, b.x);
    });

    for (int i = 0; i < n; i++) {
        rockets[n + i] = rockets[i];
    }

    ll max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < i + 1 + n; j++) {
            // printf("%d, %d\n", i, j);

            Point acc;
            acc.x = 0;
            acc.y = 0;
            for (int k = i; k < j; k++) {
                acc.x += rockets[k].x;
                acc.y += rockets[k].y;
            }

            // printf("acc: %lld\n", DIST_TWICE(acc.x, acc.y));

            if (DIST_TWICE(acc.x, acc.y) > max) {
                max = DIST_TWICE(acc.x, acc.y);
            }
        }
    }

    printf("%11.11f\n", sqrt(max));

    return 0;
}


Measured memory_bytes: 640
sk = input().split()
s = sk[0]
K = int(sk[1])
mod = 998244353

x = [0]
for si in s:
    if(si=='0'):
        x.append(0)
    else:
        x[-1] += 1

while(x):
    if(x[-1] == 0):
        x.pop()
    else:
        break
x = x[::-1]
len_x = len(x)
ones = min(K,sum(x))
dp = [[] for _ in range(len_x+1)]

for i in range(len_x+1):
    dp[i] = [[0] * (ones+1) for _ in range(ones+1)]

dp[0][0][0] = 1
for i,xi in enumerate(x):
    cumsum_y = [[0] * (ones+2) for _ in range(ones+2)]
    cumsum_xy = [[0] * (ones+2) for _ in range(ones+2)]

    for j in range(ones+1):
        for k in range(ones+1):
            cumsum_y[j+1][k+1] = (cumsum_y[j][k+1] + dp[i][j][k])%mod
            cumsum_xy[j+1][k+1] = (cumsum_xy[j][k] + dp[i][j][k])%mod

    for j in range(ones+1):
        for k in range(j,ones+1):
            dp[i+1][j][k] += cumsum_y[k+1][k+1] - cumsum_y[j][k+1]
            dp[i+1][j][k] += cumsum_xy[j][k] - cumsum_xy[max(0,j-xi)][max(0,j-xi) + k-j]
            dp[i+1][j][k] %= mod

ans = 0
for k in range(ones+1):
    ans += dp[-1][0][k]
    ans %= mod

print(ans)

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

#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define SIZE(array) (sizeof(array) / sizeof(array[0]))

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

#define MAX_V 100000

#define MOD 1000000007L
#define INF 2147483647

signed main() {
	string s;
	cin >> s;
	while (s != "") {
		if (s.size() >= 7 && s.substr(s.size() - 7) == "dreamer") {
			s = s.substr(0, s.size() - 7);
		} else if (s.size() >= 6 && s.substr(s.size() - 6) == "eraser") {
			s = s.substr(0, s.size() - 6);
		} else if (s.size() >= 5 && s.substr(s.size() - 5) == "dream") {
			s = s.substr(0, s.size() - 5);
		} else if (s.size() >= 5 && s.substr(s.size() - 5) == "erase") {
			s = s.substr(0, s.size() - 5);
		} else {
			break;
		}
	}
	cout << (s.size() == 0 ? "YES" : "NO") << endl;
}


Measured memory_bytes: 512
import java.util.Scanner;


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

		int H = sc.nextInt();
		int W = sc.nextInt();

		String S[] = new String[50];

		for (int i = 0; i < H; i++) {
			S[i] = sc.next();
		}

		for (int i = 0; i < H; i++) {
			StringBuilder sb = new StringBuilder();
			for (int j = 0; j < W; j++) {
				if (S[i].charAt(j) == '#') {
					sb.append("#");
					continue;
				}

				int mineNum = 0;

				for (int x = i - 1; x < i + 2; x++) {
					for (int y = j - 1; y < j + 2; y++) {
						if (x >= 0 && x < H && y >= 0 && y < W
								&& S[x].charAt(y) == '#') {
							mineNum++;
						}
					}
				}

				sb.append(String.valueOf(mineNum));
			}
			S[i] = sb.toString();
		}

		for (int i = 0; i < H; i++) {
			System.out.println(S[i]);
		}
	}
}

Measured memory_bytes: 22868
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e9
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R;
ll A;
ll B[200001];
ll ansmap[90001];
ll ans;
string S;
ll K;
ll mx[90001];
ll my[90001];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
int main() {
	cin >> H >> W >> D;
	rep(i, 0, H) {
		rep(j, 0, W) {
			cin >> A;
			mx[A]= i;
			my[A]= j;
		}
	}
	rep(i, D+1, H*W+1) {
		ansmap[i] = ansmap[i - D] + abs(mx[i] - mx[i - D]) + abs(my[i] - my[i - D]);
	}
	cin >> Q;
	while (Q--){
		cin >> L >> R;
		cout << ansmap[R] - ansmap[L] << endl;
	}
	cin >> ans;
	return 0;
}

Measured memory_bytes: 3200
#include<iostream>
using namespace std;
int main() {
	//freopen("in","r",stdin);
	while(1) {
		int a, b; cin>>a>>b;
		if(a==b&&a==0) break;
		int cnt = 0;
		for(int i=1;i<=a;i++) {
			for(int j=i+1;j<=a;j++) {
				for(int k=j+1;k<=a;k++) {
					if(i+j+k==b) cnt++;
				}
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}


Measured memory_bytes: 3008
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

double foo(int K, double L, double R, double P, double E, double T) {
	if (L - T > E || T - R > E) return 0;
	if (abs(L - T) <= E && abs(R - T) <= E) return 1;
	double H = (L + R) / 2;
	if (K == 0) return abs(H - T) <= E ? 1 : 0;
	double p = (H >= T ? 1 - P : P);
	double res = p * foo(K - 1, L, H, P, E, T);
	res += (1 - p) * foo(K - 1, H, R, P, E, T);
	return res;
}

int main() {
	int K, L, R; cin >> K >> L >> R;
	double P, E, T; cin >> P >> E >> T;
	printf("%.10f\n", foo(K, L, R, P, E, T));
}

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

namespace Competitive
{
    internal class Solution
    {
        public void Run()
        {
            int N = Input.ReadInt();
            int A = Input.ReadInt();

            Console.WriteLine(N % 500 <= A ? "Yes" : "No");

        }

    }

    internal static class Input
    {
        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }
    }

    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 11092
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int s['z'-'a'+1]={}, i;

 while((i = getchar()) != EOF)
  s[i-'a']=1;

 for(i=0; i<='z'-'a'; i++){
  if(s[i]==0){
   printf ("%c\n", 'a'+i);
   exit(0);
  }
 }
  puts("None");
 return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {

    	Main main=new Main();

    	main.run();

    }

    void run() {
    	Scanner sc=new Scanner(System.in);
    	
    	String s=sc.next();
    	
    	int counter=0;
    	for(String str:s.split("")){
    		if(str.equals("1")) {
    			counter++;
    		}
    	}
    	
    	System.out.println(counter);
    }

}







Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T &  a, U &  ... b) { cin >> a; IN_(b ...); };
template<typename T                > void OUT(T && a            ) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

template<typename T> istream & operator>>(istream & s, vector<T> & v) { RF(e, v) { s >> e; } return s; }
template<typename T> ostream & operator<<(ostream & s, vector<T> const & v) {
	inc(i, SI(v)) { s << (i == 0 ? "" : " ") << v[i]; }
	return s;
}

int main() {
	IN(LL, n, k);
	vector<int> a(n);
	cin >> a;
	RF(e, a) { e--; }
	
	vector<int> id(n, -1), ans;
	int p = 0, x = -1, y = 0;
	while(true) {
		ans.PB(p);
		id[p] = y++;
		p = a[p];
		if(id[p] > -1) { x = id[p]; break; }
	}
	OUT(k < x ? ans[k] + 1 : ans[(k - x) % (y - x) + x] + 1);
}


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

namespace ConsoleApplication1
{
    class Node
    {
        internal int key;
        internal Node left, right;

        public Node(int key)
        {
            this.key = key;
        }
    }

    class Program
    {
        static StringBuilder sb = new StringBuilder();
        static Node root;

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            for(int i = 0; i < n; i++)
            {
                string[] input = Console.ReadLine().Split(' ');

                switch (input[0][0])
                {
                    case 'i':
                        Insert(int.Parse(input[1]));
                        break;
                    case 'f':
                        sb.AppendLine(find(root, int.Parse(input[1])) ? "yes" : "no");
                        break;
                    default:
                        Inorder(root);
                        sb.AppendLine();
                        Preorder(root);
                        sb.AppendLine();
                        break;
                }
            }
            Console.Write(sb);
        }

        static bool find(Node u,int k)
        {
            while (u != null)
            {
                if (k == u.key) return true;
                u = k < u.key ? u.left : u.right;
            }
            return false;
        }
        
        static void Insert(int k)
        {
            Node x = root;
            Node y = null;
            Node z = new Node(k);

            while (x != null)
            {
                y = x;
                x = z.key < x.key ? x.left : x.right;
            }

            if (y != null)
            {
                if (z.key < y.key) y.left = z;
                else y.right = z;
            }
            else root = z;
        }

        static void Inorder(Node u)
        {
            if (u == null) return;

            Inorder(u.left);
            sb.Append(" " + u.key);
            Inorder(u.right);
        }

        static void Preorder(Node u)
        {
            if (u == null) return;

            sb.Append(" " + u.key);
            Preorder(u.left);
            Preorder(u.right);
        }
    }
}

Measured memory_bytes: 70172
#include <bits/stdc++.h>
#define rep(n) for(int I = 0; (I) < (n); ++(I) )
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    int n, m; cin >> n >> m;
    vector<lint> brightness(n); repeat(i, n) cin >> brightness[i];
    
    vector<lint> a(m+1, 0), b(m+1, 0), da(m+1, 0), db(m+1, 0), cost(m+1, 0);
    
    repeat(i, n-1) {
        lint s = brightness[i];
        lint t = brightness[i + 1];
        if (s < t) {
            da[s] += (-1);
            da[t] -= (-1);
            
            db[0] += (t - s);
            db[s] -= (t - s);
            db[s] += (t + 1);
            db[t] -= (t + 1);
            db[t] += (t - s);
        }
        else {
            da[0] += (-1);
            da[t] -= (-1);
            da[s] += (-1);
            
            db[0] += (t + 1);
            db[t] -= (t + 1);
            db[t] += (m + t - s);
            db[s] -= (m + t - s);
            db[s] += (m + t + 1);
        }
    }
    
    a[0] = da[0];
    b[0] = db[0];
    repeat_from(i, 1, m) {
        a[i] += a[i-1] + da[i];
        b[i] += b[i-1] + db[i];
    }
    
    cost[0] = numeric_limits<lint>::max();
    repeat_from_to(i, 1, m) {
        cost[i] = (a[i-1] * i) + b[i-1];
    }
    cout << *(min_element(cost.begin(), cost.end())) << endl;
    return 0;
}   

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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

#define rep(i, n) FOR(i, 0, n)
#define FOR(i, x, n) for (int i = (x); i < (n); ++i)
#define all(v) (v).begin(), (v).end()

using ll = long long;

template<class T> void chmax(T& a, T b){ a>b?:a=b; }
template<class T> void chmin(T& a, T b){ a<b?:a=b; }

int main() {
    int k;
    ll sum = 0;
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        for (int j = 1; j <= k; ++j) {
            for (int l = 1; l <= k; ++l) {
                sum += gcd(i, gcd(j, l));
            }
        }
    }
    cout << sum << endl;

    return 0;
}

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

int rec(std::vector<int> &h, std::vector<int> &dp, int i)
{
    // ベースケース
    if (i == 0) return dp[i] = 0;  // メモを取りながら返す

    // メモチェック
    if (dp[i] < INT_MAX) return dp[i];

    // 再帰関数
    if (i == 1) return dp[i] = (rec(h, dp, i-1) + abs(h[i] - h[i-1]));  // メモを取りながら返す
    if (i > 1)
    {
        int num1 = rec(h, dp, i-1) + abs(h[i] - h[i-1]);
        int num2 = rec(h, dp, i-2) + abs(h[i] - h[i-2]);
        return dp[i] = std::min(num1, num2);  // メモを取りながら返す
    }
    return 0;
}

int main()
{
    // 入力
    int N;
    std::cin >> N;
    std::vector<int> h(N);
    for (int i = 0; i < N; i++) std::cin >> h[i];
    
    // 問題を解く
    std::vector<int> dp(N, INT_MAX);
    int ans = rec(h, dp, N-1);

    // 出力
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 7296
# coding: utf-8
# Your code here!

n = int(input())

now = [0,0]
time = 0

flag = True

for i in range(n):
    t,x,y = map(int,input().split())
    if t-time >= abs((now[0]-x)+(now[1]-y)) and (t-time)%2==((now[0]-x)+(now[1]-y))%2:
        now = [x,y]
        time = t
    else:
        flag = False
        break
    
if flag:
    print("Yes")
else:
    print("No")

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

typedef long long int LL;
typedef long long int LLint;

//Faster Program
#define endl "\n"

//Faster Coding
#define ED return
#define GET(a) int a;cin >> a
#define DGET(a) double a;cin >> a
#define SGET(a) string a;cin >> a
#define CGET(a) char a;cin >> a
#define PRINT(a) cout << a << "\n"
#define ANS(a,b) int a;cin >> a;cout << b << "\n"
#define FOR(n) for(int i = 0;i < n;i++)
#define SORT(vec) sort(vec.begin(),vec.end())
#define REV(vec) reverse(vec.begin(),vec.end())

//As Function
#define UP(a,b) ((a+(b-1))/b)
#define ipow(x,y) LL(pow(x,y))

//Debug
#define TEST cout << "OK\n"

const double PI = M_PI;
const long long INF = int(999999999);
const long long MOD = int(1000000007);

//Settings
const bool DO_BENCHMARK = false;
const int DOUBLE_ACCURACY = 15;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(DOUBLE_ACCURACY);
    void solve();
    if(DO_BENCHMARK){
        clock_t clock_start = clock();
        solve();
        clock_t clock_end = clock();
        const double time = static_cast<double>(clock_end-clock_start)/CLOCKS_PER_SEC*1000.0;
        cout << "\n" << time << "[ms]\n";
    }
    else solve();
}

void solve(){
    int A, B;
    cin >> A >> B;
    vector<bool> vec (3,true);
    vec[A-1] = false;
    vec[B-1] = false;
    for(int i = 0;i < 3;i++){
        if(vec[i])cout << i+1 << endl;
    }
}



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

namespace debug
{
    class ProgramC
    {
        static void Main(string[] args)
        {
            //入力
            int n = int.Parse(Console.ReadLine());

            string[] a = Console.ReadLine().Split(' ');
            int[] boss = new int[n];
            for (int i = 0; i < n -1; i++)
            {
                boss[int.Parse(a[i]) - 1]++;

            }
            for (int i = 0; i < n; i++)
            {
                //sの位置に応じて場合分けする
                Console.WriteLine(boss[i]);
            }
            
        }
    }

}


Measured memory_bytes: 42300
N = int(input())

flag = False

for i in range(N//4+1):
    a = 4 * i
    for j in range(N//7+1):
        b = 7 * j
        if a+b==N:
            flag = True
        elif a+b>N:
            break

if flag:
    print("Yes")
else:
    print("No")

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		a[i] %= b[i];
	}
	int64_t m = 0;
	for (int i = n - 1; i >= 0; i--) {
		if ((a[i] + m) % b[i] != 0) {
			m += b[i] - (a[i] + m) % b[i];
		}
	}
	cout << m << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include<iomanip>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(int argc, const char * argv[]) {
    int a, b;
    cin >> a >> b;
    if ((a * b) % 2 == 0) {
        cout << "Even" << endl;
    } else {
        cout << "Odd" << endl;
    }
    return 0;
}


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

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 200005;


int main(){
  string s; cin >> s;
  int N = s.size();
  vvi c(N+1,vi(26));
  vi dp(N+2,0),temp(26,N);
  rrep(i,N-1){
    temp[int(s[i]-'a')] = i;
    c[i] = temp;
  }
  dp[N] = 1;
  rrep(i,N-1){
    int nex = INF;
    rep(j,26){
      nex = min(nex,dp[c[i][j]+1]);
    }
    dp[i] = nex + 1;
  }
  // cout << s << endl;
  // rep(i,N+2) cout << dp[i];
  // cout << "" << endl;
  string ans = "";
  int now = 0;
  rep(i,dp[0]){
    int j = 0;
    for(;j<26;j++) if(dp[c[now][j]+1]==dp[now]-1) break;
    ans += char('a'+j);
    now = c[now][j] + 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 27908
#include <iostream>
#include <string>
#include <queue>
using namespace std;

struct Process{
	string name;
	int time;
};

int main(void)
{	
	queue<Process> que;
	
	int n, q;
	cin >> n >> q;
	
	for(int i = 0; i < n; i++){
		
		Process P;
		cin >> P.name >> P.time;
		que.push(P);
	}
	
	int count_time = 0;
	
	while(true){
	
		Process P = que.front();
		que.pop();
		
		if(P.time < q){
			count_time += P.time;
		}
		else{
			count_time += q;
		}

		P.time = P.time - q;
		
		if(P.time <= 0){
			cout << P.name << " " << count_time << endl;
		} 
		else{
			que.push(P);
		}
		if(que.empty() == true){
			break;
		}
		
	}

	return 0;
}

Measured memory_bytes: 6228
#include<iostream>
#include<iomanip>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<algorithm>
#include<cmath>
#include<memory>
#include<string>

using namespace std;

int main()
{
  int n;
  string s;
  cin >> n;
  
  for ( auto i = 0; i < n; ++i )
    {
      cin >> s;
      string ss(s);
      sort( ss.begin(), ss.end() );
      string rs(ss);
      reverse( rs.begin(), rs.end() );
      cout << stoi( rs ) - stoi( ss ) << endl;
    }
  
  return 0;
}

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

using namespace std;
typedef long long LL;

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

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}


int a[1123456];
int pos[1123456];
int l[1123456];
int r[1123456];
int main() {
	int N, Q;
	cin >> N >> Q;
	REP(i, N) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	int lmost = a[0];
	int rmost = a[N - 1];
	l[a[0]] = -1;
	r[a[N - 1]] = -1;
	REP(i, N - 1) {
		r[a[i]] = a[i + 1];
	}
	FOR(i, 1, N) {
		l[a[i]] = a[i - 1];
	}
	while (Q--) {
		int p;
		cin >> p;
		int next_lmost = r[p];
		if (next_lmost == -1)next_lmost = p;
		int next_rmost = l[p];
		if (next_rmost == -1)next_rmost = p;
		if (rmost != p) {
			r[rmost] = p;
			l[r[p]] = -1;
		}
		if (lmost != p) {
			l[lmost] = p;
			r[l[p]] = -1;
		}
		

		if (lmost == p) {
			r[p] = -1;
		}else {
			r[p] = lmost;
		}
		
		if (rmost == p) {
			l[p] = -1;
		}else {
			l[p] = rmost;
		}

		lmost = next_lmost;
		rmost = next_rmost;
	}
	string sp(N, ' ');
	sp[N-1] = '\n';

	
	REP(i, N) {
		cout << lmost << sp[i];
		lmost = r[lmost];
	}
	return 0;
}



Measured memory_bytes: 4776
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define rep(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
long long h,w,ans;
int main()
{
	//freopen("std.in","r",stdin);
	cin>>h>>w;
	ans=min(h,w);
	if(h%3);else ans=0;
	if(w%3);else ans=0;
	for(int i=1;i<h;i++)
	{
		if(w%2)ans=min(ans,max(abs(h-i),
			max(abs(i*w-(h-i)*(w/2)),abs(i*w-(h-i)*(w+1)/2))));
		else ans=min(ans,abs(i*w-(h-i)*w/2));
	}
	for(int i=1;i<w;i++)
	{
		if(h%2)ans=min(ans,max(abs(w-i),
			max(abs(i*h-(w-i)*(h/2)),abs(i*h-(w-i)*(h+1)/2))));
		else ans=min(ans,abs(i*h-(w-i)*h/2));
	}
	cout<<ans;
	return 0;
}


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

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define ALL(c)  (c).begin(),(c).end()


int N, M, Q;
int l[200000], r[200000];
int p[100000], q[100000];

int ans[100000];

template <typename T>
class fenwick_tree_1 { // 1-base
    vector<T> x;
 public:
    fenwick_tree_1(int n) : x(n+1,0) { }
    void add(int k, T a=1) { for (; k<=x.size(); k+=k&-k) x[k] += a; }
    T sum(int i, int j) {
        if (i == 1) {
            T S = 0; for (; j>0; j-=j&-j) S += x[j]; return S;
        } else {
            return sum(1, j) - sum(1, i-1);
        }
    }
};

void solve() {
    vector<ii> lines(M);
    rep(i,M) {
        lines[i] = ii(r[i], l[i]); // (Ri, Li)
    }
    sort(ALL(lines)); // 右端で昇順ソート

    map<int, vector<ii>> queries;
    rep(query_id, Q) {
        // クエリを右端ごとにまとめる (query_group)
        queries[q[query_id]].push_back(ii(p[query_id], query_id));
    }

    fenwick_tree_1<int> ft(511);

    int last_line_id = 0;
    for (auto query_group : queries) {
        int q = query_group.first;
        // vector<ii> g = query_group.second;

        while (last_line_id < M && lines[last_line_id].first <= q) {
            int l = lines[last_line_id].second;
            ft.add(l);
            ++last_line_id;
        }

        // この時点でFTに入ってるのは、r <= q なlineのみ
        // なので、p が与えられたとき [p, q] の間の個数を数えれば良い
        for (ii p_i : query_group.second) {
            int p = p_i.first, query_id = p_i.second;
            ans[query_id] = ft.sum(p, q);
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &Q);
    rep(i,M) {
        scanf("%d %d", &l[i], &r[i]);
    }
    rep(i,Q) {
        scanf("%d %d", &p[i], &q[i]);
    }

    solve();

    rep(i,Q) {
        printf("%d\n", ans[i]);
    }

    return 0;
}


Measured memory_bytes: 6260
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <math.h>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define rev(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = INT_MAX;






int main() {

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

    sort(a, a+n);

    int ans = 0;
    int tmp = 1;
    rep(i,n-1) {
        if (a[i] == a[i+1]) {
            ++tmp;
        }
        else {
            if (tmp % 2 == 1) ++ans;
            tmp = 1;
        }
    }
    if (tmp%2 == 1) ++ans;

    out(ans);


    return 0;
}




//              g++ -std=c++1z






Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    int l, r, d;
    cin >> l >> r >> d;
    int ans = 0;
    for (int i=l; i<=r; i++) {
        if (i % d == 0) ans++;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const int MOD = 1000000007;

class Combination_Mod{
    public:
        Combination_Mod(long long MAX, long long MOD) : fact(MAX + 1), inv(MAX + 1), finv(MAX + 1), MAX(MAX + 1), MOD(MOD){
            init();
        }

        void init(){
            fact[0] = fact[1] = 1;
            finv[0] = finv[1] = 1;
            inv[1] = 1;
            for(long long i = 2; i < MAX; ++i){
                fact[i] = fact[i - 1] * i % MOD;
                inv[i] = MOD - inv[MOD % i] *  (MOD / i) % MOD;
                finv[i] = finv[i - 1] * inv[i] % MOD;
            }
        }

        long long bin(long long n, long long r){
            if(n < r || n < 0 || r < 0) return 0;
            return fact[n] * (finv[r] * finv[n - r] % MOD) % MOD;
        }

        long long perm(long long n, long long r){
            return (bin(n, r) * fact[r]) % MOD;
        }

        long long factorial(long long n){
            return fact[n];
        }

        long long modinv(long long n){
            return inv[n];
        }

        long long modfinv(long long n){
            return finv[n];
        }

    private:
        vector<long long> fact;
        vector<long long> inv;
        vector<long long> finv;
        const long long MAX;
        const long long MOD;
};


ll N, M;
ll fact[1000010];

signed main(){
    cin >> N >> M;
    fact[0] = 1;
    for(ll i = 0; i < N; i++) fact[i + 1] = (fact[i] * (i + 1)) % MOD;
    Combination_Mod cm(M + 1, MOD);
    // M_P_N
    ll ans = 0, sgn = 1;
    // cerr << ans << endl;
    for(ll i = 0; i <= N; i++){
        ll x = sgn * (cm.bin(N, i) * cm.perm(M, i) % MOD) * (cm.perm(M - i, N - i) * cm.perm(M - i, N - i) % MOD) % MOD;
        ans = (ans + x + MOD) % MOD;
        sgn *= -1;
    }
    PRINT(ans);
    return 0;
}

Measured memory_bytes: 18688
#include<stdio.h>
#include<algorithm>
using namespace std;
int p[10005][105];
int w[105];
int v[105];
int main()
{
    int n;
    int W;
    int sum=0;
    scanf("%d%d",&n,&W);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }
    for(int i=1;i<=n;i++)
          p[0][i]=0;
    for(int i=1;i<=W;i++)
    {
        for(int j=1;j<=n;j++)
        {
            p[i][j]=p[i][j-1];
            if(w[j]>i)
                continue;
            else
            p[i][j]=max(p[i][j-1],p[i-w[j]][j-1]+v[j]);
        }
    }
    printf("%d\n",p[W][n]);
    return 0;
}

Measured memory_bytes: 6852
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  rep(i, N){
    cin >> A.at(i);
  }
  vector<int> num(N, 0);
  rep(i, N){
    num.at(A.at(i)-1)++;
  }
  sort(all(num));
  reverse(all(num));
  int pos = N;
  rep(i, N){
    if(num.at(i) == 0){
      pos = i;
      break;
    }
  }
  int cnt = 0;
  if(pos <= K){
    cout << 0 << endl;
  }
  else{
    while(pos > K){
      cnt += num.at(pos-1);
      pos--;
    }
    cout << cnt << endl;
  }
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 25 18:20:35 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
def input():
    return sys.stdin.readline()[:-1]
mod = 10**9+7

#N = int(input())
N, K = map(int,input().split())
A = np.array(list(map(int,input().split())))
#N, K, *A = map(int, open(0).read().split())

dp = [True for i in range(K + A[-1] + 1)]
for i in range(K):
    if dp[i]:
        for a in A:
            dp[i + a] = False

#    print(i, dp[i],A+i,dp[A+i])
#print(dp)

if dp[K]:
    ans = 'Second'
else:
    ans = 'First'
print(ans)

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

using namespace std;

int main(){
	int n;
	while(cin>>n && n!=0){
		vector <int> a;
		for(int i=0;i<n;i++){
			int b;
			cin>>b;
			a.push_back(b);
		}
		sort(a.begin(),a.end());

		int ans=0;
		for(int i=0;i<n-2;i++){
			ans+=a[i+1];
		}
		cout<<ans/(n-2)<<endl;
	}
	return 0;
}

Measured memory_bytes: 1220
#include<stdio.h>
int main()
{
  long long int a,b,x;
  long long int con;
  
  scanf("%lld %lld %lld",&a,&b,&x);
  
  con=b/x-(a-1)/x;
  if(a==0&&x!=1) con++;
  
  printf("%lld",con);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
lint lcm(lint a,lint b){
      return a/__gcd(a,b)*b;
  }
 
  int main(){
     lint N;
     cin>>N;
     lint a,b;
     cin>>a>>b;
     rep(i,N-1){
         lint x,y;
         cin>>x>>y;
         lint l=max((a+x-1)/x,(b+y-1)/y);
         a=x*l;b=y*l;
     }
     cout<<a+b;

}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>
#include <limits>
#include <iostream>

using namespace std;

int L[501][501];
int v[501][501];
int dist[501][501];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dist[i][j] = min(i, min(j, min(n - i - 1, n - j - 1)));
      v[i][j] = -1;
      L[i][j] = 0;
    }
  }
  long long ans = 0;
  vector<pair<int, int>> q;
  for (int i = 0; i < n*n; i++) {
    int ind;
    cin >> ind;
    ind--;

    {
      int r = ind / n, c = ind % n;
      ans += dist[r][c];
      L[r][c] = 1;
      q.clear();
      q.emplace_back(r, c);
      v[r][c] = i;
    }
    for (int h = 0; h < q.size(); h++) {
      int r, c;
      tie(r, c) = q[h];
      // recalc
      int newdist = 1 - L[r][c] + dist[r][c];
      if (r > 0 && v[r - 1][c] < i && dist[r - 1][c] > newdist) {
        dist[r - 1][c] = newdist;
        q.emplace_back(r - 1, c);
        v[r - 1][c] = i;
      }
      if (c > 0 && v[r][c - 1] < i && dist[r][c - 1] > newdist) {
        dist[r][c - 1] = newdist;
        q.emplace_back(r, c - 1);
        v[r][c - 1] = i;
      }
      if (r + 1 < n && v[r + 1][c] < i && dist[r + 1][c] > newdist) {
        dist[r + 1][c] = newdist;
        q.emplace_back(r + 1, c);
        v[r + 1][c] = i;
      }
      if (c + 1 < n && v[r][c + 1] < i && dist[r][c + 1] > newdist) {
        dist[r][c + 1] = newdist;
        q.emplace_back(r, c + 1);
        v[r][c + 1] = i;
      }
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 8140
N,M,L,Q;
D[301][301];
i,j,k;
a,b,c;
main()
{
	scanf("%d%d%d",&N,&M,&L);
	for(i=1;i<=N;i++)for(j=i+1;j<=N;j++)D[i][j]=D[j][i]=1000000001;
	for(i=0;i<M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		D[a][b]=D[b][a]=c;
	}
	for(k=1;k<=N;k++)for(i=1;i<=N;i++)for(j=1;j<=N;j++)
		if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];
	for(i=1;i<=N;i++)for(j=1;j<=N;j++)
	{
		if(i!=j)D[i][j]=(D[i][j]>L)*1000000000+1;
	}
	for(k=1;k<=N;k++)for(i=1;i<=N;i++)for(j=1;j<=N;j++)
		if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];
	scanf("%d",&Q);
	for(i=0;i<Q;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",D[a][b]<1000000000?D[a][b]-1:-1);
	}
}

Measured memory_bytes: 768
// AOJ 2607: Invest Master
// 2017.10.8 bal4u@uu

#include <stdio.h>

int p[11][11];
int dp[100002];

int main()
{
	int n, d, x, i, j, k, t;

	scanf("%d%d%d", &n, &d, &x);
	for (i = 0; i < d; i++) for (j = 0; j < n; j++) scanf("%d", &p[i][j]);
	for (i = 0; i < d-1; i++) {
		for (j = 0; j <= x; j++) dp[j] = j;
		for (j = 0; j < n; j++) for (k = 0; k <= x; k++) if (k >= p[i][j]) {
			t = dp[k-p[i][j]] + p[i+1][j];
			if (t > dp[k]) dp[k] = t;
		}
		for (t = 0, j = 0; j <= x; j++) if (dp[j] > t) t = dp[j];
		x = t;
	}
	printf("%d\n", x);
	return 0;
}

Measured memory_bytes: 1884
//Code is like humor. When you have to explain it, it’s bad.
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define MOD 1000000007
#define int long long
using namespace std;
#define s second
#define f first

int modexp(int a, int n)
{
    int res=1;
    while(n)
    {
        if(n&1) res=(res*a)%MOD;
        n>>=1;
        a=(a*a)%MOD;
    }
    return res;
}
int32_t main()
{
    fastio;
    int T,n,m,i,j,k,a,b,c;
    T=1;
    while(T --> 0)
    {
        cin>>n>>k;
        int A[n+1];
        A[0]=0;
        for(i=1;i<=n;i++)
            A[i]=A[i-1]+i;
        int ans=0;    
        for(i=k;i<=n;i++)
        {
            a =(A[n]-A[n-i]-A[i-1]+1);
            ans=(ans+a)%MOD;
        }
        cout<<(ans+1)%MOD;
    }
    return 0;
}

Measured memory_bytes: 5220
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <bits/stdc++.h>
#include <string>
using namespace std;
using ll = long long;
const ll MOD = 1000000007; 
int N,M;

int dfs(vector<vector<int>> v,vector<bool> reach,int now){
    reach[now] = true;
    bool flag_reach = true; 
    for(auto i=0;i<N;i++){
        if(!reach[i]){
            flag_reach=false;
        }
    }
    if(flag_reach) return 1;
    int sum = 0;
    for(long i=0;i<N;i++){
        if(v[now][i]==1&&!reach[i]){
            sum += dfs(v,reach,i);
        }
    }
    return sum;
}

int main(){   
    cin>>N>>M;
    vector<vector<int>> v(N,vector<int>(N,0));
    for(auto i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        v[a][b] = 1;
        v[b][a] = 1;
    }
    vector<bool> reach(N,false);

    int res = dfs(v,reach,0);
    cout<<res<<endl;

}


Measured memory_bytes: 256
def push(S, top, x):
      S.append(x)
      top = top + 1

def pop(S, top):
      t = int(S[top-1])
      del S[top-1]
      top = top -1
      return t

if __name__ == "__main__":
      top = 0
      inpt = (input()).split()
      n = len(inpt)
      S = []
      for i in range(0,n):
            if inpt[i] == "+":
                  b = pop(S, top)
                  a = pop(S, top)
                  c = a + b
                  push(S, top, c)
            elif inpt[i] == "-":
                  b = pop(S, top)
                  a = pop(S, top)
                  c = a - b
                  push(S, top, c)
            elif inpt[i] == "*":
                  b = pop(S, top)
                  a = pop(S, top)
                  c = a * b
                  push(S, top, c)
            else :
                  push(S, top, int(inpt[i]))
      print(S[top-1])

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

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

    string S;
    ll AB = 0;
    ll lastA = 0;
    ll frontB = 0;
    ll both = 0;
    for(ll j = 0; j < N; j++){
        cin >> S;
        ll size = S.size();
        if(S[0] == 'B') frontB++;
        if(S[size-1] == 'A') lastA++;
        if(S[0] == 'B' && S[size-1] == 'A') both++;
        bool preIsA = false;
        
        for(ll i = 0; i < size; i++){
            if(preIsA && S[i] == 'B'){
                AB++;
            }
            if(S[i] == 'A'){
                preIsA = true;
            }else{
                preIsA = false;
            }
        }
    }

    ll ans = AB;
    if(both > 0){
        ans += both - 1;
        lastA -= both -1;
        frontB -= both - 1;
        both = 1;
    }
    
    if(!(frontB == lastA && lastA == both))
        ans += min(frontB,lastA);
    cout << ans <<  "\n";
    return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>					
using namespace std;
	
int main()	
{	int n;
cin>>n;
float a[10001];
for(int i= 0;i<n;i++){
	cin>>a[i];
}
float ans = 0;
if(n==2){
	cout<<(a[0]+a[1])/2;return 0;
}else{
	sort(a,a+n);
	ans=(a[0]+a[1])/2;	
	for(int i = 2;i<n;i++){
		ans=(ans+a[i])/2; 
	}
cout<<ans;															
	return 0;} 									
 } 

Measured memory_bytes: 256
#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
using namespace std;
int main(){

	int n;
	bool p[300002]={false};
	
	p[2]=true;
	p[3]=true;
	
	for(int i=3;i<=300000;i+=2){
		bool f=false;
		for(int j=3;j<=sqrt(i);j+=2){
			if(i%j==0){
				f=true;
				break;
			}
			
		}
		if(!f)
			p[i]=true;
	}
	
	long long s=0;

	
	while(cin>>n,n!=0){
		long long s=0;
		if(n>=1){
			s+=2;
			n--;
		}
		for(int j=3;j<=300000;j+=2){
			if(n<=0)
				break;
			else if(p[j]){
				s+=j;
				n--;
			}
		}
		cout<<s<<endl;
	}


}

Measured memory_bytes: 1456
#include <stdio.h>

int main(void)
{       
  int a,b,c,d;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  if(a==b&&c==d||a==c&&b==d||a==d&&b==c){
  	printf("yes\n");
  }
  else {
  	printf("no\n");
  }
	return 0;
}


Measured memory_bytes: 2104