akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>
   
using namespace std;

#define mod 1000000007

double solve(int tn, int cn, double t[8], double r[31][31], int s, int e)
{
    double result[(1 << tn)][cn + 1];
    // result[i][j] : i???????????°??¨?¨???????1????????£???????????¨???????????¬???????¶?????????????j???????????????????????????????????¢
    for(int i = 0; i < (1 << tn); i++){
        for(int j = 1; j <= cn; j++){
            result[i][j] = mod + 0.0;
        }
    }
    result[0][s] = 0.0;
    for(int i = 0; i < (1 << tn); i++){
        for(int j = 1; j <= cn; j++){
            // cout << result[i][j] << " ";
            // ???????????????j????????????????????£?????¬???????????±???i
            // ?????????????????¬???????±???????
            for(int k = 0; k < tn; k++){
                if((i & (1 << k)) != 0) continue;
                // ??????????????????????±???????
                for(int l = 1; l <= cn; l++){
                    if(r[j][l] == mod) continue;
                    result[(i | (1 << k))][l] = min(result[(i | (1 << k))][l], result[i][j] + r[j][l] / t[k]);
                }
            }
        }
        // cout << endl;
    }
    double ans = mod + 0.0;
    for(int i = 0; i < (1 << tn); i++){
        ans = min(ans, result[i][e]);
    }
    return ans;
}

int main()
{
    int n, m, p, a, b;
    while(1){
        cin >> n >> m >> p >> a >> b;
        if(n == 0) break;
        double tichet[8];
        double road[31][31];
        for(int i = 0; i < n; i++){
            cin >> tichet[i];
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= m; j++){
                road[i][j] = mod + 0.0;
            }
        }
        for(int i = 0; i < p; i++){
            int x, y;
            double z;
            cin >> x >> y >> z;
            road[x][y] = z;
            road[y][x] = z;
        }
        double ans = solve(n, m, tichet, road, a, b);
        if(ans == mod) cout << "Impossible" << endl;
        else printf("%.3f\n", ans);
    }
    return 0;
}

Measured memory_bytes: 3268
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(2)]
sum0 = []
sum1 = []


for ind,i in enumerate(A[0]):
    if(ind==0):
        sum0.append(i)
    else:
        sum0.append(sum0[ind-1]+i)
for ind,i in enumerate(reversed(A[1])):
    if(ind==0):
        sum1.append(i)
    else:
        sum1.append(sum1[ind-1]+i)

ans = 0
for i in range(N):
    ans = max(sum0[i]+sum1[N-1-i],ans)

print(ans)


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

using namespace std;
using LL = long long;

constexpr int N = 1e5 + 5;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    LL A, B;
    cin >> A >> B;

    int res = 1;

    for (LL i = 2; i * i <= A; i++) {
        if (A % i == 0) {
            if (B % i == 0) res++;
            while (A % i == 0) A /= i;
        }
    }

    if (A > 1 && B % A == 0) res++;

    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
 
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(b-a==c-b){
        cout<<"YES"<<endl;
        
    }
    else{
        cout<<"NO"<<endl;
    }
}

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

int main(void) {
    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    sort(vec.begin(), vec.end());
    int sum = 0;
    for (int i = 0; i < k; i++) sum += vec[i];
    cout << sum << "\n";
    return 0;
}



Measured memory_bytes: 3156
# encoding: utf-8
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N + M - 1)]

# find start node
E = [[] for i in range(N)]
nE = [0] * N
for A, B in AB:
    E[A - 1].append(B)
    nE[B - 1] += 1

# print("#", E)
# print("#", nE)
    
S = []
for i in range(N):
    if nE[i] < 1: S.append(i + 1)

# print("#", S)
    
L = []
while len(S) > 0:
    Si = S.pop()
    L.append(Si)
    # print("##", Si)
    for Eij in E[Si - 1]:
        if nE[Eij - 1] == 1: S.append(Eij)
        nE[Eij - 1] -= 1
    else:
        E[Si - 1] = []

# print("#", L)

mapL = [0] * N
for i, Li in enumerate(L): mapL[Li - 1] = i + 1

ans = [0] * N
for Ai, Bi in AB:
    # print("##", Ai, Bi, ans[Bi - 1], mapL[Bi - 1])
    if ans[Bi - 1] < 1 or mapL[ans[Bi - 1] - 1] < mapL[Ai - 1]: ans[Bi - 1] = Ai

for ansi in ans: print(ansi)

Measured memory_bytes: 41720
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
	int a = 0;
	string s;

	cin >> s;

	REP(i, 4){
		if (s[i] == '+') a++;
		else a--;
	}

	cout << a << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define MAX 2000

int c[MAX][MAX];
int lcs(string x, string y)
{
    int m = x.size();
    int n = y.size();
    int max1 = 0;
    x = ' '+x;
    y = ' '+y;
    for(int i=1; i<=m; i++)
        c[i][0] = 0;
    for(int j=1; j<=n; j++)
        c[0][j] = 0;
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(x[i] == y[j])
                c[i][j] = c[i-1][j-1]+1;
            else if(c[i-1][j]>=c[i][j-1])
                c[i][j] = c[i-1][j];
            else
                c[i][j] = c[i][j-1];
        }
    }
}
int main()
{
    int n, t;
    string s1, s2;
    cin >> n;
    while(n--)
    {
        cin >> s1 >> s2;
        lcs(s1,s2);
        cout << c[s1.size()][s2.size()] << endl;
    }
    return 0;
}

Measured memory_bytes: 10960
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

	public static void main(String[] args) throws IOException{
		  BufferedReader r =new BufferedReader(new InputStreamReader(System.in), 1);
		                                        // ???????????\????????????
		  
		  String s =r.readLine();
		  int x = Integer.parseInt(s);
		System.out.println(x*x*x);
		
	}
}

Measured memory_bytes: 17028
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

#define FIRST "First"
#define SECOND "Second"

string s;

int main(int argc, char **argv) {
	cin >> s;
	if ((s[0] == s[s.length() - 1]) == (s.length() % 2 == 0)) {
		cout << FIRST << endl;
	}
	else {
		cout << SECOND << endl;
	}
	return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>

#define P 1000000007
#define int long long

using namespace std;

typedef long long ll;

char ch[77];

void add(int &x, int y) {
    x = (x + y) % P;
}

int n, K, Fac[333], Rev[333], X[77], C[333][333], ans = 0;

ll powmod(ll x, ll y = P - 2, ll p = P) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}
int ts = 0;
void calc(int sz) {
    ts++;
    int tb = 0, tr = 0;
    int used[77], TR[77], TB[77];
    memset(used, 0, sizeof used);
    for(int i = 1; i <= sz; i++) {
        tr++;
        while(tr <= K && ch[tr] != 'r') tr++;
        used[tr] = 1;
        if(X[i] > 1) {
            tb = max(tb + 1, tr);
            while(tb <= K && (ch[tb] != 'b' || used[tb])) tb++;
            used[tb] = 1;
            TR[i] = tr;
            TB[i] = tb;
        } else {
            TR[i] = tr;
            TB[i] = tr;
        }
        if(tr > K || tb > K) return;
    }
    for(int i = 1; i <= sz; i++) {
        int tt = TB[i];
        for(int j = 1; j <= X[i] - 2; j++) {
            while(tt <= K && used[tt]) tt++;
            used[tt] = 1;
            if(tt > K) return;
        }
    }
    int t = 0, rw = 0, bw = 0;
    for(int i = 1; i <= sz; i++)
        if(X[i] == 1) {
            rw++;
            t++;
        } else {
            bw += X[i] - 1;
            rw += X[i];
            t += X[i] * 2 - 3;
        }
    t = n + 1 - t - sz;
    if(t < 0) return;
    ll tmp = Fac[sz];
    X[sz + 1] = 0; //!!!
    for(int i = 2, lst = 1; i <= sz + 1; i++)
        if(X[i] != X[lst]) {
            tmp = tmp * Rev[i - lst] % P;
            lst = i;
        }
    for(int r = 0; r <= t; r++)
        for(int b = 0; r + b <= t; b++) {
            add(ans, (!rw ? !r : C[r + rw - 1][r]) * (!bw ? !b : C[b + bw - 1][b]) % P * C[sz + (t - r - b)][sz] % P * tmp);
        }
}

void Search(int x, int lst, int tbr, int tot = 0) {
    calc(x - 1);
    for(int i = 1; i <= lst && i + tbr <= K && max(2ll, i * 2 - 2) + tot <= n + 3; i++) {
        X[x] = i;
        Search(x + 1, i, tbr + i, tot + max(2ll, i * 2 - 2));
    }
}

#undef int
int main() {
#define int long long
    for(int i = 0; i < 333; i++)
        for(int j = 0; j <= i; j++)
            C[i][j] = !j ? 1 : (C[i - 1][j - 1] + C[i - 1][j]) % P;
    for(int i = 0; i < 333; i++) Fac[i] = !i ? 1 : Fac[i - 1] * i % P;
    for(int i = 332; i >= 0; i--) Rev[i] = i == 332 ? powmod(Fac[i]) : Rev[i + 1] * (i + 1) % P;
    scanf("%lld%lld", &n, &K);
    scanf("%s", ch + 1);
    Search(1, K, 0);
    //printf("%d\n", ts);
    printf("%lld\n", (ans % P + P) % P);
    return 0;
}

Measured memory_bytes: 1024
package main

import (
	"fmt"
	//"math"
)

func main() {
	var a, b int
	fmt.Scanf("%d %d", &a, &b)
	if (a+b)%2 == 0 {
		fmt.Print((a + b) / 2)
	} else {
		fmt.Print("IMPOSSIBLE")
	}
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
typedef vector<vi> vvi;
typedef vector<ll> vl;
const ll N=100005;
ll h[N],mh[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=0;i<m;i++){
        ll x,y;cin>>x>>y;
        mh[x]=max(h[y],mh[x]);
        mh[y]=max(h[x],mh[y]);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(mh[i]==0 || mh[i]<h[i])ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 5220
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <cstdio>
#include <cmath>

using namespace std;

/**
 * Sieve of Eratosthenes
 */
template <size_t N>
struct Sieve {
  using Integer = int;
  bool is_prime[N + 1];
  constexpr Sieve() : is_prime() {
    Integer sqrt_N = sqrt(N);

    for (Integer i = 0; i <= N; i++) is_prime[i] = true;

    is_prime[1] = false;
    is_prime[2] = true;

    for (Integer p = 2; p <= sqrt_N; p++) {
      if (is_prime[p] == false) continue;

      is_prime[p] = true;

      for (Integer i = p + 1; i <= N; i++) {
        if (i % p == 0) is_prime[i] = false;
      }
    }
  }
};

/**
 * Legendre's theorem
 * Count the number of p in prime factors of N!
 */
int legendre (int N, int p) {
  int res = 0, k = 1, pk = p;
  while (pk <= N) {
    res += (int) N / pk;
    pk *= p;
  }
  return res;
}

/**
 * main
 */
int main () {
  constexpr auto sieve = Sieve<100>();

  int N;
  scanf("%d", &N);

  int d[7] = {0, 0, 0, 0, 0, 0, 0};
  for (int p = 2; p <= N; p++) {
    if (!sieve.is_prime[p]) continue;

    int pe = legendre(N, p);

    if (pe >= 24) d[0]++;
    if (2 <= pe && pe < 24) d[1]++;
    if (pe >= 14) d[2]++;
    if (4 <= pe && pe < 14) d[3]++;
    if (pe >= 4) d[4]++;
    if (2 <= pe && pe < 4) d[5]++;
    if (pe >= 74) d[6]++;
  }

  int ans = d[0] * (d[0] - 1) + d[1] * d[0]
    + d[2] * (d[2] - 1) + d[3] * d[2]
    + d[4] * (d[4] - 1) * (d[4] - 2) / 2 + d[5] * d[4] * (d[4] - 1) / 2
    + d[6];

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

  return 0;
}


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


using namespace std;


double dp[3000][3000];
double chance[3000];

int main(){
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++)
        cin >> chance[i];
    
    dp[0][0] = 1.0;
    
    // throwing ith coin
    for(int i=1; i<=n; i++){
        dp[i][0] = dp[i-1][0] * (1-chance[i-1]);
        // chance of in ith throw, getting j heads
        for(int j=1; j<=i; j++){
            // 
            dp[i][j] = dp[i-1][j-1] * chance[i-1] + dp[i-1][j] * (1.0-chance[i-1]);
        }
    
    }
    
    double sum = 0;
    
    for(int j=(n+1)/2; j<=n; j++){
        sum += dp[n][j];
    }
    cout << setprecision(10);
    cout << sum << endl;

}

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

//#define int long long
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

// 例えばex1の1,2,1の部分和を昇順に列挙すると
// 0, 1, 1, 2, 2, 3, 3, 4
// i番目と8-i番目の和は常に4つまりAの総和Sであることがわかる
// (i-8番目がi番目の補集合に対応してるから当然)
// つまり求めるものはS/2以上の最小の部分和

int n, a[2000], s;
bitset<2020*2000> b;

signed main() {
	cin >> n;
	rep(i,n) cin >> a[i];
	s = accumulate(a, a+n, 0);
	s = (s+1)/2;
	b[0] = 1;
	rep(i,n) b |= b<<a[i];
	while (!b[s]) s++;
	cout << s << ln;
}

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

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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


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

	int n;
	cin >> n;

	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; i++) {
		int a;
		cin >> a;
		a--;
		g[a].emplace_back(i + 1);
	}

	vector<int> dp(n);
	function<void(int)> go = [&](int i) {
		if (g[i].empty()) {
			return;
		}
		vector<int> acc;
		for (auto j : g[i]) {
			go(j);
			acc.emplace_back(dp[j]);
		}

		sort(begin(acc), end(acc));
		reverse(begin(acc), end(acc));
		for (int j = 0; j < acc.size(); j++) {
			acc[j] += j + 1;
		}
		dp[i] = *max_element(begin(acc), end(acc));
	};

	go(0);
	cout << dp[0] << endl;
	return 0;
}


Measured memory_bytes: 15488
N, Y = map(int, input().split())
_10000 = -1
_5000 = -1
_1000 = -1
for i in range(N+1):
    for j in range(N - i+1):
        k = N - i - j
        if i * 10000 + j * 5000 + k * 1000 == Y:
            _10000 = i
            _5000 = j
            _1000 = k
            break
    else:
        continue
    break
print(_10000, _5000, _1000)

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

int partion(int *A, int p, int r){
    int x = A[r];
    int i,j,k;
    i=p-1;
    for(j=p;j<r;j++){
        if(A[j]<=x){
            i++;
            swap(A[j], A[i]);
        }
    }

    swap(A[i+1], A[r]);
    return i+1;
}

int main(){
    int n, A[1000000];
    scanf("%d", &n);
    for(int k=0;k<n;k++) scanf("%d", &A[k]);

    int m=partion(A, 0, n-1);
    for(int j=0;j<n;j++){
        if(j==m) cout<<"["<<A[j]<<"]"<<" ";
        else if(j==n-1) cout<<A[j]<<endl;
        else cout<<A[j]<<" ";
    }

    return 0;
}


Measured memory_bytes: 3448
#include <bits/stdc++.h>
using namespace std;
#define itn int
#define nibu(K,x) binary_search(K.begin(),K.end(),x)
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define out(x) cout<<x<<endl
#define put(x) out(x)
#define in(x) cin>>x
#define maxx(a,b,c) max(a,max(b,c))
#define minn(a,b,c) min(a,min(b,c))
using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
const double pi = 3.14159265358979;

double kyori(int ax,int ay,int bx,int by){
return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}

int main() {
int N;
  in(N);
  double wa=0;
  vl x(N),y(N);
  rep(i,N) in(x[i]>>y[i]);
  rep(i,N){
   rep(j,N){
    if(i != j){
     wa += kyori(x[i],y[i],x[j],y[j]);
    }
   }
  }
  double ans = wa / N;
  cout << fixed << setprecision(10)<<ans <<endl;;
}

Measured memory_bytes: 256
#include <stdint.h>

#include <algorithm>
#include <bitset>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

bool check(std::string &s) {
  for (int i = 0; i <= s.size() / 2; i++) {
    if (s[s.size()-1-i] != s[i]) return false;
  }
  return true;
}

int main(int argc, char *argv[]) {
  std::string s;
  std::cin >> s;
  std::string s2 = s.substr(0, s.size() / 2);
  std::string s3 = s.substr(s.size() / 2 + 1, s.size() / 2);

  std::cout << ((check(s) && check(s2) && check(s3)) ? "Yes" : "No")
            << std::endl;

  return 0;
}


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)

int main() {
    fastio
    long long t1, t2, a1, a2, b1, b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
    
    long long fi, se;
    fi = t1*(a1- b1);
    se = t2*(a2- b2);
    long long diff = fi + se;
    if(diff == 0 ){
        cout<<"infinity"<<endl;
    }
    else{
        long long res = 0;
        if( (fi<0 && diff < 0) || (fi>0 && diff > 0)  )
            cout<<res<<endl;
        else{
            fi = abs(fi);
            diff = abs(diff);
            res = fi/diff;
            
            res = 2*res;
            res++;
            if(fi%diff == 0)
                res--;
            cout<<res<<endl;
        }
    }
        
    
	return 0;
}






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

int main(){
  ll n;
  cin>>n;
  vector<ll> v(n);
  rep(i,n){
    cin>>v.at(i);
  }
  bool ok = true;
  for (int i = n-2;i>=0;i--){
    if (v.at(i) > v.at(i+1)){
      if (v.at(i)-v.at(i+1) > 1){
        ok = false;
        break;
      }
      v.at(i)--;
    }
  }
  if (ok){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> P;
typedef pair<ll,ll> PLL;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
//int dp[100050];

int main(){
    int X,N;
    cin >> X >> N;
    vector<int> p(N);
    rep (i,N) cin >> p.at(i);
    vector<bool> list(105,true);
    rep (i,N) list.at(p.at(i)) = false;
    int pmax,pmin;
    for (int i = X; i < 103; i++) {
        if (list.at(i)) {
            pmax = i;
            break;
        }
    }
    for (int i = X; i >= 0; i--) {
        if (list.at(i)) {
            pmin = i;
            break;
        }
    }
    if (X - pmin > pmax - X) cout << pmax << endl;
    else cout << pmin << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

int x[10], y[10];

double dist(int i, int j){
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}

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

    rep(i, n) cin >> x[i+1] >> y[i+1];
    
    int array[n];
    rep(i, n) array[i] = i + 1;
    long double ans = 0;
    do{
        rep(i, n - 1) ans += dist(array[i], array[i+1]);
    }while(next_permutation(array,array+n));
    int f = 1;
    rep(i, n) f *= i + 1;

    cout << fixed << setprecision(10) << ans / f << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i=int(a); i<int(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define y0 snowy0
#define y1 snowy1
#define rank snowrank
#define next snownext
#define prev snowprevc

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

#ifdef LOCAL
  #define db cout << "L" << __LINE__ << ": "
  #define dv(v) << #v << "->" << v << " "
  #define de << endl
#else
  #define db
  #define dv(v)
  #define de
#endif

#define MAX_N 100000
int par[MAX_N];
int rank[MAX_N];
int club[MAX_N];

void init(int n) {
  rep(i, n) {
    par[i] = i;
    rank[i] = 0;
  }
}

pair<int, int> find(int x) {
  if (par[x] == x) {
    return mp(x, club[x]);
  } else {
    pair<int, int> p = find(par[x]);
    par[x] = p.F;
    club[x] = p.S;
    return p;
  }
}
bool add_member(int student, int c) {
  pair<int, int> p = find(student);
  if (club[student] != 0 && club[student] != c) {
    return false;
  }
  if (p.S != 0 && p.S != c) {
    return false;
  }
  club[p.F] = c;
  club[student] = c;
  return true;
}

bool unite(int nx, int ny) {
  pair<int, int> x = find(nx);
  pair<int, int> y = find(ny);
  if (x.F == y.F) return true;

  if (rank[x.F] < rank[y.F]) {
    par[x.F] = y.F;
    if (y.S == 0) {
      club[y.F] = x.S;
    } else if (club[x.F] == 0) {
      club[x.F] = y.S;
    } else if (club[x.F] != y.S) {
      return false;
    }
  } else {
    par[y.F] = x.F;
    if (x.S == 0) {
      club[x.F] = y.S;
    } else if (club[y.F] == 0) {
      club[y.F] = x.S;
    } else if (x.S != 0 && club[y.F] != x.S) {
      return false;
    }
    if (rank[x.F] == rank[y.F]) rank[x.F]++;
  }
  return true;
}

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

int N;
int M;
int K;

void debug_club() {
  rep(i, N) {
    cout << club[i] << " ";
  }
  cout << endl;
}

int main() {
  N = in();
  M = in();
  K = in();
  init(N);
  rep(i, K) {
    int t = in();
    int a = in();
    int b = in();
    if (t == 1) {
      if (!unite(a-1, b-1)) {
        cout << i+1 << endl;
        return 0;
      }
    } else if (t == 2) {
      if (!add_member(a-1, b)) {
        cout << i+1 << endl;
        return 0;
      }
    }
  }
  cout << 0 << endl;
  return 0;
}




Measured memory_bytes: 4264
#include <cstdio>
#include <iostream>
#define MN 410
#define MM 101000

int n, m;
int x[MM], y[MM];
bool used[MN][MN], ok[MN];

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
		scanf("%d%d", &x[i], &y[i]);
	for(int i = 1; i <= n; i++)
	{
		used[i][i] = 1;
		for(int j = m; j >= 1; j--)
		{
			if(used[i][x[j]] && used[i][y[j]]) {ok[i] = 1; break;}
			else if(used[i][x[j]]) used[i][y[j]] = 1;
			else if(used[i][y[j]]) used[i][x[j]] = 1; 
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++)
		{
			if(ok[i] || ok[j]) continue;
			bool okk = 0;
			for(int k = 1; k <= n; k++)
				if(used[i][k] && used[j][k]) okk = 1;
			if(!okk) ans++;
		}
	printf("%d\n", ans);
}

Measured memory_bytes: 1152
board=[[0]*10 for i in range(10)]
ink=[[[0,0,0,0,0],[0,0,1,0,0],[0,1,1,1,0],[0,0,1,0,0],[0,0,0,0,0]],
[[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0]],
[[0,0,1,0,0],[0,1,1,1,0],[1,1,1,1,1],[0,1,1,1,0],[0,0,1,0,0]]]

while True:
    try:
        x,y,s=map(int,input().split(","))
    except:
        break
    for i in range(5):
        for j in range(5):
            if 0<=i+y-2<=9 and 0<=j+x-2<=9:
                board[i+y-2][j+x-2]+=ink[s-1][i][j]
    
flat=sum(board,[])
print(flat.count(0))
print(max(flat))

Measured memory_bytes: 7696
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;

int n, dep[maxn];
vector<int> edge[maxn];

void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    for (int& v: edge[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 2, u, v; i <= n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v); edge[v].push_back(u);
    }
    dfs(1, 0);
    int rt, mx = 0;
    for (int i = 1; i <= n; i++) if (dep[i] > mx) mx = dep[i], rt = i;
    dfs(rt, 0);
    mx = 0; for (int i = 1; i <= n; i++) mx = max(mx, dep[i]);
    if (mx % 3 != 2) puts("First");
    else puts("Second");
    return 0;
}

Measured memory_bytes: 21376
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on("data",function(chunk){
    var line = chunk.trim().split(" ");
    var men;
    var syu;
    men = (line[0]*1) * (line[1]*1);
    syu = (line[0]*2) + (line[1]*2);
    console.log(men.toString()+" "+syu.toString());
});

Measured memory_bytes: 15492
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int n, a, b, c, ans = 1e9;
int l[8];
void dfs(int i, int lenA, int lenB, int lenC, int cnt) {
    if (i >= n) {
        if (min({lenA, lenB, lenC}) > 0)
            ans = min(ans, 10 * (cnt - 3) + abs(a - lenA) + abs(b - lenB) + abs(c - lenC));
        return;
    }
    dfs(i + 1, lenA + l[i], lenB, lenC, cnt + 1);
    dfs(i + 1, lenA, lenB + l[i], lenC, cnt + 1);
    dfs(i + 1, lenA, lenB, lenC + l[i], cnt + 1);
    dfs(i + 1, lenA, lenB, lenC, cnt);
    return;
}

int main() {
    cin >> n >> a >> b >> c;
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    dfs(0, 0, 0, 0, 0);
    OUT(ans);
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}

int main()
{
        //input->compute->output//
        int A,B,C;
        cin >> A>>B>>C;
        int ma = max({A, B, C});
        cout<<ma*9+A+B+C<<endl;

        return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n),b(n);
    for(int i = 0;i < n;i++){
        cin >> a.at(i);
        b.at(i) = a.at(i);
    }
    /**/
    sort(a.begin(),a.end());
    for(int i = 0;i < n;i++){
        if(b.at(i) == a.at(n - 1)){
            cout << a.at(n - 2) << endl;
        }
        else{
            cout << a.at(n - 1) << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;


int main(){
    string S; cin >> S;
    set<char> ST; for(auto c : S) ST.insert(c);
    ll ans = 1e9;
    for(auto ch : S){
        ll Min=0;
        string S_ = S;
        while(1){
            
            bool flag = true;
            string tmp="";
            for(int i = 0; i < S_.size(); i++){
                if(S_[i] != ch) flag = false;
                if(i == S_.size()-1) continue;
                if(S_[i] == ch || S_[i+1] == ch) {
                    tmp+=ch;
                }
                else {
                    tmp += S_[i];
                    flag = false;
                }
            }
            if(flag) break;
            //cout << tmp << " " << Min+1 << endl;
            S_ = tmp;
            
            Min++;
        }
        ans = min(ans, Min);
    }
 
    cout << ans <<endl;
}

Measured memory_bytes: 256
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n,m;
    cin>>n>>m;
    ll ans=0;
    ans+=((n*(n-1))/2);
    ans+=((m*(m-1))/2);
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    //cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

int main()
{
    int n, l;
    int i, s;

    cin >> n;
    cin >> l;

    s = 0;
    for(i=0;i<n;i++){
        s += l + i;
    }

    if(l >= 0){
        cout << s - l;
    }else{
        if(abs(l) < n){
            cout << s;
        }else{
            cout << s - (l + n - 1);
        }
    }

    return 0;
}

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

int main()
{
  int n, m;
  cin >> n >> m;
  int64_t ans = 0, su = 0;
  vector<pair<int64_t, int>> AB;
  for (int i = 0; i < n; ++i)
  {
    int64_t a;
    int b;
    cin >> a >> b;
    AB.push_back(make_pair(a, b));
  }
  sort(AB.begin(), AB.end());

  int i = 0;
  while (su != m)
  {
    int tmp;
    if (AB[i].second < m - su) tmp = AB[i].second;
    else tmp = m - su;
    ans += AB[i].first * tmp;
    su += tmp;
    ++i;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2420
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  var line, lines = chunk.split("\n"),
      i, len = lines.length, j, jLen,
      deg, pow, max;

  for (i=0; i<len; i++) {
    line = lines[i];
    if (line == "#") {
      break;
    }

    line = line.replace(/north/g, 0);
    line = line.replace(/west/g, 1);

    deg = 0;

    jLen = line.length;
    pow = line.length - 1;
    max = 90 * Math.pow(2, pow);
    for (j=jLen; j>=0; j--) {
      if (line[j]*1) {
        if (deg < max) {
          deg += 90 * Math.pow(2, j);
        }   
      } else {
        if (deg > 0) {
          deg -= 90 * Math.pow(2, j);
        }
      }
    }

    while(pow > 0 && deg % 2 === 0) {
      deg = deg / 2;
      pow--;
    }
    
    if (pow > 0) {
      console.log(deg + "/" + Math.pow(2, pow));
    } else {
      console.log(deg);
    }
  }
});

Measured memory_bytes: 16048
#include <iostream>
#include<map>
using namespace std;
typedef long long ll;
ll n,s[26],d[365][26],t[365],ans,u[26],q,a,b,c,MAX=-10000000,L,A[365],M,MM,ok,MAZ=-10000000,p,B[365];
int main(void){
    cin>>n;
    for(int i=0;i<26;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        M=0;
        for(int j=0;j<26;j++){
            cin>>d[i][j];
            if(M<d[i][j]){MM=j;M=d[i][j];}
        }
        A[i]=t[i]=MM+1;
    }
    
    p=10;
    while(p--){
        
        for(int i=0;i<n;i++){
                t[i]=A[i];
            }
            
            
        q=20000;
        while(q--){
            a=rand()%n;
            b=rand()%26;
            ans=0;
            for(int i=0;i<26;i++)u[i]=0;
            
            c=t[a];
            t[a]=b+1;
            
            for(int i=0;i<n;i++){
                ans+=d[i][t[i]-1];
                u[t[i]-1]=i+1;
                for(int j=0;j<26;j++){
                    ans-=s[j]*(i+1-u[j]);
                }
            }
            if(ok==0){MAX=ans;ok=1;}
            if(MAX<ans){
                MAX=ans;
            }
            else t[a]=c;
        }
        
        if(MAZ<MAX){
            MAZ=MAX;
            for(int i=0;i<n;i++){
                B[i]=t[i];
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<B[i]<<endl;;
    }
    //cout<<MAZ<<endl;
}


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

int main(){
	ll x,y;
	cin>>x>>y;
	if(y%2!=0){
		cout<<"No"; 
		return 0;
	}

	ll t = y/2 - x;
	ll c = x-t;
	if(t>=0 && c>=0){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
}

Measured memory_bytes: 3508
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
int int_max = 2147483647;
int max_n = 1e5;
using mat2d_t = std::vector<std::vector<int64_t>>;



int main(int argc, char **argv) {
    int n, k;
    cin >> n >> k;

    int ans{0};
    while (n) {
        n /= k;
        ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>  
using namespace std;  
  
bool isprime(int n){  
    int m = sqrt(n);  
    for(int i = 2; i <= m; i++){  
        if(n % i == 0) return 0;  
    }  
    return 1;  
}  
  
int main()  
{  
    int n;  
    cin >> n;  
    int k = 11;  
    while(n){  
        if(isprime(k) && k % 10 == 1){  
            cout << k << ' ';  
            n--;  
        }  
        k += 10;  
    }  
    cout << endl;  
    return 0;  
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,tp[N],c[3],v,e;
vector<int> I[N],O[N];
bool ok,vis[N];
ll ans;
void dfs(int x,int h){
    tp[x]=h%3;
    c[tp[x]]++;
    vis[x]=1;
    v++;
    e+=O[x].size();
    for (int i=0;i<O[x].size();i++){
        int v=O[x][i];
        if (!vis[v]) dfs(v,h+1);else
        if ((tp[v]-tp[x]+3)%3!=1) ok=0;
    }
    for (int i=0;i<I[x].size();i++){
        int v=I[x][i];
        if (!vis[v]) dfs(v,h+2);else
        if ((tp[v]-tp[x]+3)%3!=2) ok=0;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        O[u].push_back(v);
        I[v].push_back(u);
    }
    for (int i=1;i<=n;i++)
    if (!vis[i]){
        ok=1;c[0]=c[1]=c[2]=v=e=0;
        dfs(i,0);
        if (!ok) ans+=1ll*v*v;else
        if (c[0]&&c[1]&&c[2]) ans+=1ll*c[0]*c[1]+1ll*c[1]*c[2]+1ll*c[2]*c[0];
        else ans+=e;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 19456
import sys
n = int(input())
p = list(map(int, input().split()))
sum_p = sum(p)-1
ans = 1
tmp = 1 - p[0]
if n==0 and p[0]==1:
    print(1)
    sys.exit()
elif n == 0:
    print(-1)
    sys.exit()

for i in range(n):
    if sum_p:
        if sum_p < tmp:
            tmp += sum_p
            sum_p = 0
        else:
            sum_p -= tmp
            tmp *= 2    
    ans += tmp
    tmp -= p[i+1]
    if tmp < 0 or (tmp==0 and i<n-1):
        print(-1)
        sys.exit()
print(ans)

Measured memory_bytes: 20152
#include <bits/stdc++.h>
using namespace std; 
#define int int64_t
#define itn int
#define fi first
#define se second
#define mod 1000000007
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h,w;
  int c[10][10];
  int a[300][300],b;
  cin>>h>>w;
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      cin>>c[i][j];
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>a[i][j];
    }
  }
  for(int k=0;k<10;k++){
    for(int i=0;i<10;i++){
      for(int j=0;j<10;j++){
	c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
      }
    }
  }
  int ans=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]!=-1) ans+=c[a[i][j]][1];
    }
  }
  cout<<ans<<"\n";
  return 0;
}


Measured memory_bytes: 4100
H, N = map(int, input().split())
magics = []
for n in range(N):
    A, B = map(int, input().split())
    magics.append([A, B])
#print(magics)  
maxa = max(A for A, _ in magics)  
#print(maxa)
point = [0]*(H+maxa)
for i in range(1, H+maxa):
    point[i] = min(point[i-a]+b for a,b in magics)
print(min(point[H:]))    

Measured memory_bytes: 3572
#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string,int> table;
int main () {
  string word, frequent, longest;
  size_t N=0; //??????????????????
  while (cin >> word) {
    table[word] += 1;
    if (table[word] > N) {
      N = table[word];
      frequent = word;
    }
    if (word.size() > longest.size()) longest = word;
  }
  cout << frequent << " " << longest << endl;
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	cin >> a;
	int yes = 1;
	for(int i = 0; i<3; i++)
	{
		if(a[i] == a[i+1]) yes = 0;
	}
	if(yes) printf("Good");
	else    printf("Bad");
	printf("\n");
	return 0;
}

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

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))    
#define OUT(P) cout << (P) << endl    
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl    
#define PRINT_ARRAY(P) for(int i=0; i<P.size(); i++) cout << P[i] << endl;    
#define PRINT_ARRAY_INLINE(P) do { for(int i=0; i<P.size(); i++) cout << P[i] << " "; cout << endl; } while(0)    
#define PRINT_ARRAY_WITH_LABEL(L, P) do { cout << L << ": "; PRINT_ARRAY_INLINE(P); cout << endl; } while(0)    
typedef long long ll;    
const long DIVIDE = 1e9+7;

int sum_digits(int num);    
template <class T>    
vector<T> copy_vector(vector<T> vec);    
long gcd(long a, long b);    
long lcm(long a, long b);
vector<vector<long>> comb(long n, long r);
// ****** print functions ****** //
template <class T, class U>
void print_pairs(const vector<pair<T, U>> pairs);
template <class K, class V>
void print_map(const map<K, V> m);

int main() {    
    int a, b, c;
    cin >> a >> b >> c;

    string ans = (a + b >= c)? "Yes" : "No";

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

/******************************/    
/***** DECRARED FUNCTIONS *****/    
/******************************/    

int sum_digits(int num) {    
    int rtn = 0;    
    while(num != 0) {    
        int tmp = num % 10;    
        rtn += tmp;    
        num /= 10;    
    }    
    return rtn;    
}    

// vectorのコピー    
template <class T>    
vector<T> copy_vector(vector<T> vec) {    
    vector<T> rtn;    
    rtn.reserve(vec.size());    
    copy(vec.begin(), vec.end(), back_inserter(rtn));    
    return rtn;    
}    

long gcd(long a, long b) {    
    if(b==0) return a;    
    else return gcd(b, a % b);    
}

long lcm(long a, long b) {
    long gcd_ = gcd(a, b);
    return (a * b) / gcd_;
}

vector<vector<long>> comb(long n, long r) {                                                                             
    vector<vector<long>> v(n+1, vector<long>(n+1, 0));    
    for(int i=0; i<v.size(); i++) {    
        v[i][0] = 1;    
        v[i][i] = 1;    
    }    
    for(int i=1; i<v.size(); i++) {    
        for(int j=1; j < i; j++) {    
            v[i][j] = (v[i-1][j-1] + v[i-1][j]) % DIVIDE;    
        }    
    }    
    return v;    
} 

template <class T, class U>
void print_pairs(const vector<pair<T, U>> &pairs) {
    for(int i=0; i<pairs.size(); i++) { 
        cout << "(" << pairs[i].first << ", " << pairs[i].second << ")" << " "; 
    } 
    cout << endl;
}

template <class K, class V>
void print_map(const map<K, V> &m) {
    for(auto it=m.cbegin(); it!=m.cend(); it++) {
        cout << it->first << ": " << it->second << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int a,b,c;
  /*cin>>a>>b>>c;
  if(a>b) cout<<"NO"<<'\n';
  else if(a+b>=c) cout<<"YES"<<'\n';
  else cout<<"NO"<<'\n';*/
  cin>>a>>b;
  cout<<a-b+1<<'\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int n, k, q;

int main()
{
	cin >> n >> k >> q;
	int x;
	// 先全部减完， 
	for(int i = 1; i <= n; i++)
	{
		a[i] += k-q;
	}
	//答对的人再把分数补回来 
	while(q--)
	{
		cin >> x;
		a[x] += 1;
	}
	for(int i = 1; i <= n; i++)
	{
		cout << (a[i]>0?"Yes":"No") << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
const int mod = 1000000007;

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  map<pii, int> d, nd;
  d[pii(0, 0)] = 1;
  for (int i = 0; i < n; ++i) {
    nd.clear();
    for (int t = 0; t < 2; ++t) {
      if (s[i] != '?' && s[i] != '0' + t) continue;
      for (const auto & it : d) {
        int l = it.first.first, mask = it.first.second;
        mask += t << l;
        ++l;
        while (l > 2) {
          if ((mask & 3) == 3) {
            mask = 3;
            l = 2;
          } else {
            int t1 = (bool)(mask & (1 << (l - 3)));
            int t2 = (bool)(mask & (1 << (l - 2)));
            int t3 = (bool)(mask & (1 << (l - 1)));
            int sum = t1 + t2 + t3;
            if (sum == 0 || sum >= 2 || (l > 3 && t1 == 1)) {
              for (int j = 1; j <= 3; ++j) mask &= ~(1 << (l-j));
              mask |= (sum / 2) << (l - 3);
              l -= 2;
            } else {
              break;
            }
          }
        }
        nd[pii(l, mask)] += it.second;
        if (nd[pii(l, mask)] >= mod) nd[pii(l, mask)] -= mod;
      }
    }
    d.swap(nd);
  }
  ll res = 0;
  for (const auto & it : d) {
    if (it.first.first == 1 && it.first.second) res += it.second;
    else if (it.first.first > 1 && (it.first.second & 3) == 3) res += it.second;
  }
  cout << (res % mod + mod) % mod << endl;
  return 0;
}

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

using namespace std;

#define fread(x)        freopen(x,"r",stdin)
#define fwrite(x)       freopen (x,"w",stdout)

#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define MEMSET(a,x)     memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))
#define keepunique(v)   (v).erase(unique(all(v)),v.end())

#define white           1
#define grey            2
#define black           3

#define ll              long long
#define pb              push_back
#define pf              push_front
#define INF             9e18
#define PI              acos(-1.0)
#define pii             pair<int,int>
#define pll             pair<ll, ll>

#define all(v)          v.begin(), v.end()

#define fastread        ios_base::sync_with_stdio(0);cin.tie(nullptr);
int on(int N,int pos){return N=N | (1<<pos);}
int off(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int lcm(int a, int b){return (a*b)/__gcd(a, b);}
//======================= let the game begin ====================//
const int maxn = 1e5 + 5;
int dis[maxn];
#define inf 1000005

int main(){
	fastread
	int k;
	cin>>k;
	for(int i=0; i<k; i++){
		dis[i]=inf;
	}
	dis[1]=1;
	deque<int>que;
	que.push_back(1);
	while(!que.empty()){
		int s = que.front();
		que.pop_front();
		if(dis[(s+1)%k] > dis[s]+1){
			dis[(s+1)%k]=dis[s]+1;
			que.pb((s+1)%k);
		}
		if(dis[(s*10)%k] > dis[s]){
			dis[(s*10)%k]=dis[s];
			que.pf((s*10)%k);
		}
	}
	cout<<dis[0]<<endl;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define ll long long
#define sz size
#define pb push_back
#define er erase
#define in insert
#define fr first
#define sc second
#define mp make_pair
#define pi pair
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
#define rc(s) return cout<<s,0
const int mod=1e9+7;
const int inf=1e5;
using namespace std;

long long  n,k,rez,rema,pop;

int main(){ _
    cin >> n >> k;
    if(k==0) rc(n*n);
    for(int i=1;i<=n;i++){
            long long q=n/i;
            rema=n%i;
           rez+=q*max(0LL,i-k);
           rez+=max(0LL,rema-k+1);
    }
    rc(rez);
}


Measured memory_bytes: 256