akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define RREP(i,a,b) for (int i = a; i > (b); --i)
#define all(x) (x).begin(),(x).end()
const long long INF = 1000000007;
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int solve(){
  double a,b;
  cin >> a >> b;
  REP(i,1,10000){
    int I =  i * 0.08;
    int J =  i * 0.1;
    if(I == a && J == b){
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}
int main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

long long co=0;

void merge(vector<int> &da,int le,int mi,int ri){
    int n1=mi-le;
    int n2=ri-mi;
    vector<int> L(n1+1),R(n2+1);
    for(int i=0;i<n1;i++){
        L[i]=da[le+i];
    }
    for(int i=0;i<n2;i++){
        R[i]=da[mi+i];
    }
    L[n1]=INT_MAX;R[n2]=INT_MAX;
    int i=0,j=0;
    for(int k=le;k<ri;k++){
        if(L[i]<R[j]){
            da[k]=L[i];
            i++;
        }
        else{
            da[k]=R[j];
            j++;
        }
        co++;
    }
}

void mergesort(vector<int> &da,int le,int ri){
    if (le+1<ri){
        int mi=(le+ri)/2;
        mergesort(da,le,mi);
        mergesort(da,mi,ri);
        merge(da,le,mi,ri);
    }
}

int main(){
    int n;
    cin >> n;
    vector<int> da(n);
    for(int i=0;i<n;i++){
        cin >> da[i];
    }
    mergesort(da,0,n);
    for(int i=0;i<n;i++){
        if(i!=n-1){
            cout << da[i] << ' ';
        }
        else{
            cout << da[i] << endl;
        }
    }
    cout << co << endl;
}


Measured memory_bytes: 6812
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  cout << vec.at(N / 2) - vec.at(N / 2 - 1) << endl;
}

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

typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    ll ans = A[0] - 1;
    ll k = 2;
    for (int i = 1; i < N; i++) {
        if (A[i] == k) {
            k++;
            continue;
        }
        if (A[i] % k == 0) {
            ans += A[i] / k - 1;
        } else {
            ans += A[i] / k;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
N = int(input())
P = list(map(int, input().split()))    
Q = list(map(int, input().split()))

queue = [i for i in range(1, N+1)]
b = []

def pq(n,q):
    a = len(q) - 1
    if a == 0:
        n += q[0]
        return n
    else:
        plus = q.pop(0)
        return pq(n+plus*10**a, q)


def nBinarius(a, q):
    n = len(q) - 1
    if n == 0:
        b.append(a + q[0])
    else:
        j = 0
        for i in q:
            q.remove(i)
            nBinarius(a + i*(10**n), q)
            q.insert(j, i)
            j += 1
    return


p = pq(0, P)
q = pq(0, Q)
nBinarius(0, queue)
pn = 0
qn = 0
n = 0
for i in b:
    if p == i:
        pn = n
    if q == i:
        qn = n
    n += 1
        
print(abs(pn-qn))

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

int w[100000],n,k;
int cntp(int p)
{
	int cnt=1,wgh=0;
	for(int i=0;i<n;)
	{
		if(wgh+w[i]<=p)
		{
			wgh+=w[i++];
		}
		else
		{
			if(wgh>0)cnt++;
			else return k+1; 
			wgh=0;
		}
	}
	return cnt;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;scanf("%d",w+i++));
	int l=0,r=1000000000,m;
	while(l<r)
	{
		m=(l+r)/2;//printf("%d %d %d %d\n",l,m,r,cntp(m));
		if(cntp(m)>k)l=m+1;
		else r=m;
	}
	for(m-=20;;m++)
	{
		//printf("%d %d\n",m,cntp(m));
		if(cntp(m)<=k)break;
	}
	printf("%d\n",m);
	return 0;
}

Measured memory_bytes: 3092
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <utility>
#include <set>
#include <unordered_map>

#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 IPSILON 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main(){
  int A, B;
  cin >> A >> B;
  if(1 <= A && A<= 9){
    if(1 <= B && B <= 9){
      cout << A*B << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <set>
using namespace std;
typedef long long int ll;

int main(){
	int k,x; cin >> k >> x;
	int i=0;
	while(i<k+k-1){
		cout << x-k+1+i << endl;
		i++;
	}
}

Measured memory_bytes: 256
// file creato da gio il 2020-04-20 19:47:11.170774

#include <bits/stdc++.h>
#define FAST 

#ifdef FAST
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#define S second
#define F first
#define PB push_back
using namespace std;
int arr [200000];

int main(){
	//freopen("output","w",stdout);
	//freopen("input","r",stdin);
#ifdef FAST
	ios::sync_with_stdio(0);
  	cin.tie(0);
#endif

	int n;
	cin >> n;
	for(int i =0 ; i<n-1;i++){
		int tmp;
		cin >>tmp;
		arr[tmp-1]++;
	}
	for(int i=0;i<n;i++)cout <<arr[i]<<"\n";

}

Measured memory_bytes: 4444
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define MOD 1000000007
#define MAX 100010
#define aout(a) REP(i,sizeof(a)) cout << a[i] << " "; cout << endl;
#define vout(v) REP(i,v,size()) cout << v[i] << " "; cout << endl;
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(){
  string S,T; cin>>S>>T;
  int ans = 100000;
  int sum = 0;
  int s_s = S.size();
  int t_s = T.size();
  REP(i,s_s - t_s + 1){
    sum = 0;
    REP(j,t_s){
      if(S[i+j] != T[j]) sum++;
    }
    ans = min(ans, sum);
  }
  cout << ans;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct edge {
  int to, cost;
  edge() {}
  edge(int to, int cost): to(to), cost(cost) {}
};

const ll INF = 1LL << 50;
int n, m, s, t;
int u[100010], v[100010], a[100010], b[100010];
vector<edge> G[2][100010];
ll dis[2][100010];

void dijkstra(int idx, int s) {
  fill_n((ll*)dis[idx], 100010, INF);
  dis[idx][s] = 0;
  using P = pair<ll, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  que.emplace(0, s);
  while (!que.empty()) {
    P p = que.top();
    que.pop();
    int cur = p.second;
    if (dis[idx][cur] < p.first) continue;
    for (edge &e : G[idx][cur]) {
      if (dis[idx][e.to] > dis[idx][cur] + e.cost) {
        dis[idx][e.to] = dis[idx][cur] + e.cost;
        que.emplace(dis[idx][e.to], e.to);
      }
    }
  }
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  cin >> n >> m >> s >> t;
  s--; t--;
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i] >> a[i] >> b[i];
    u[i]--; v[i]--;
    G[0][u[i]].emplace_back(v[i], a[i]);
    G[0][v[i]].emplace_back(u[i], a[i]);
    G[1][u[i]].emplace_back(v[i], b[i]);
    G[1][v[i]].emplace_back(u[i], b[i]);
  }  
  dijkstra(0, s);
  dijkstra(1, t);
  ll cost = INF;
  vector<ll> ans;
  for (int i = n - 1; i >= 0; i--) {
    cost = min(cost, dis[0][i] + dis[1][i]);
    ans.emplace_back(cost);
  }
  for (int i = n - 1; i >= 0; i--) {
    cout << (ll)1e15 - ans[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 18812
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define ull unsigned long long
#define dd double
#define oo 1001007000
#define ff float
#define ooo 4223352036854775007
#define iii pair<ll,ll>
#define vii vector<ll>
#define viii vector<iii>
#define sss pair<str,str>
#define str string
#define sii set<ll>
#define siii set<iii>
#define r0 return 0
#define pb push_back
#define sz size
using namespace std;

const char E='\n';
const int N=10005;
const int NN=2005;
const ll md=998244353;


int main(){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    iii a[N];
    int n;
    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> a[i].first >> a[i].second;
    }
    string ans="No";
    for (int i=2;i<n;i++){
        if (a[i].first==a[i].second && a[i-1].first==a[i-1].second && a[i+1].first==a[i+1].second)
            ans="Yes";
    }
    cout << ans << E;
    r0;
}
/*








*/


Measured memory_bytes: 3808
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k == 0: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ
        else: # k >= 1
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]

#print(dp)
print(dp[m][0][K] + dp[m][1][K])


Measured memory_bytes: 9272
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	int a[100];
	int ans=INF;
	scan(N);
	rep(i,N) scan(a[i]);
	for(int A=-100;A<=100;A++){
		int sum=0;
		rep(i,N){
			sum+=(a[i]-A)*(a[i]-A);
		}
		ans=min(ans,sum);
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n;
  cin >> n;

  vll as(3 * n);
  rep(i, 3 * n) cin >> as[i];

  vll lef(n+1);
  ll sum = 0;
  priority_queue<ll, vll, greater<ll>> pql;
  rep(i, n) {
    sum += as[i];
    pql.emplace(as[i]);
  }
  lef[0] = sum;
  repLRE(i, n, 2 * n - 1) {
    ll t = pql.top();
    if (t < as[i]) {
      pql.push(as[i]);
      pql.pop();
      sum += as[i] - t;
    }
    lef[i - n + 1] = sum;
  }

  vll rig(n+1);
  sum = 0;
  priority_queue<ll> pqr;
  rep(i, n) {
    sum += as[3*n - 1 - i];
    pqr.emplace(as[3*n - 1 - i]);
  }
  rig[n] = sum;
  rrepLRE(i, 2 * n - 1, n) {
    ll t = pqr.top();
    if (t > as[i]) {
      pqr.push(as[i]);
      pqr.pop();
      sum += as[i] - t;
    }
    rig[i - n] = sum;
  }
  ll ans = LONG_LONG_MIN;
  rep(i, n+1) chmax(ans, lef[i] - rig[i]);

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

Measured memory_bytes: 6516
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
int main() {
vector<int> a(5);
rep(i, 5) cin >> a[i];
 int k;
 cin >> k;
bool f = true;
for (int i = 0; i < 5; i++) {
  for (int j = i + 1; j < 5; j++) {
    if (abs(a[i]-a[j]) > k) f = false;
  }
}

if(f) cout << "Yay!" << endl;
else cout << ":(" << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int s[N];
int main(){
	int n,k,q;
	cin >> n >> k >> q;
	int z;
	for(int i=1;i<=q;i++){
		cin >> z;
		s[z]++;
	}
	for(int i=1;i<=n;i++){
		if(q-s[i]<k) cout << "Yes" <<endl;
		else  cout << "No" <<endl;	
	}
	return 0;
} 

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, n) for (int i = (n)-1; i >= 0; i--)
#define pp(v) cout << #v << "=" << (v) << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)

int main() {
  // input
  int n,m; cin >> n >> m;
  vector<int> x(m);
  rep(i,m) cin >> x[i];
  sort(x.begin(), x.end());

  // 区間列を生成
  vector<int> gaps(m-1);
  rep(i,m-1) gaps[i] = x[i+1] - x[i];
  sort(gaps.begin(), gaps.end());

  // 区間数m-1から、コマの数n-1この区間を飛ばして累積
  int sum = 0;
  rep(i,m-n) sum += gaps[i];
  // rep(i,m) pp(x[i]);
  // rep(i,m-1) pp(gaps[i]);

  cout << sum << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000001
#define MAXN        200005
#define mod         1000000007
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,a,b,ans;
    cin>>n>>a>>b;
    ans=n/(a+b);
    ans=ans*a;
    n=n%(a+b);
    if(n>=a){
        ans+=a;
    }
    else{
        ans+=n;
    }
    cout<<ans;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public void main(Scanner sc) {
        int n = sc.nextInt();
        long a[] = new long[n];

        for (int i = 0; i < n; i++) {
            a[sc.nextInt() - 1] = i;
        }

        TreeSet<Long> set = new TreeSet<>();

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long num = a[i];
            Long l = set.lower(num);
            Long r = set.higher(num);

            l = (l == null ? -1 : l);
            r = (r == null ? n : r);

            ans += (i + 1) * (num - l) * (r - num);

            set.add(num);
        }

        System.out.println(ans);
    }

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


Measured memory_bytes: 88992
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

final class Solver {
	static final Solver INSTANCE = new Solver();

	void solve(Scanner sc) {
		int N = Integer.parseInt(sc.next());
		for (int i = 1; i <= N; i++) {
			long sum = (i * (i + 1L)) / 2;
			if (N <= sum) {
				System.out.println(IntStream.rangeClosed(1, i).filter(j -> j != (sum - N)).mapToObj(String::valueOf).collect(Collectors.joining("\n")));
				return;
			}
		}
	}
}

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

		Solver.INSTANCE.solve(in);

		in.close();
	}
}

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

#define MAX 1005
#define INF (1e9)
int t[MAX];
int u[MAX];
int dp[MAX][MAX];
int N,M;

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

  for(int i=0;i<=N;i++)
    for(int j=0;j<=M;j++)
      dp[i][j]=INF;
  dp[0][0]=0;
  
  for(int i=0;i<N;i++)cin>>t[i];
  for(int i=0;i<M;i++)cin>>u[i];
  
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      if(dp[i][j]==INF)continue;
      dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+t[i]*u[j]);
      dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
    }
  }

  int ans=INF;
  for(int i=0;i<=M;i++)
    ans=min(ans,dp[N][i]);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4360
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<list>
#include<bitset>
using namespace std;

int main() {

	int N, M;
	cin >> N >> M;

	int L = 0;
	int R = N;
	int Li = 0;
	int Ri = N;
	for (int i = 0; i < M; i++) {
		cin >> Li >> Ri;
		L = max(L, Li);
		R = min(R, Ri);
	}

	int ans = R - L + 1;

	if (ans < 0) {
		ans = 0;
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,e)

void vprn(vector<int> &v){ for(int i=0;i<v.size();i++) cout<<v[i]<<(i<v.size()-1?",\t":"\n"); }///

int main(){
	int N; cin>>N;
	string S; cin>>S;
	vi E(N+1), W(N+1);//累積和
	rpz(i,N){
		if(S[i]=='E'){
			E[i+1] = E[i] + 1;
		}
		else{
			E[i+1] = E[i];
		}
		if(S[i]=='W'){
			W[i+1] = W[i] + 1;
		}
		else{
			W[i+1] = W[i];
		}
	}
	// vprn(E);//
	// vprn(W);//
	int mini = INT_MAX;
	rp(leader,1,N+1){
		mini = min(mini, (E[N]-E[leader])+(W[leader-1]));
	}
	ote(mini);
}


Measured memory_bytes: 3076
#include <cstdio>
using namespace std;
#define MAX_N (105)
#define INF (10000)
int n;
int G[MAX_N][MAX_N];
bool MST[MAX_N];
int DIST[MAX_N];		// MST??¨????????¢
int NEIGH[MAX_N];		// ??£??????

int main()
{
    scanf("%d", &n);
    for ( int i = 0; i < n; i++ ) {
	for ( int j = 0; j < n; j++ ) {
	    int d;
	    scanf("%d", &d);
	    G[i][j] = ( d == -1 ) ? INF : d;
	}
    }

    int r = 0;
    int size_mst = 1;

    MST[r] = true;
    
    for ( int i = 0; i < n; i++ ) {
	if ( i == r ) continue;
	DIST[i] = G[r][i];
	NEIGH[i] = r;
    }

    int ans = 0;

    while ( size_mst < n ) {
	int u = 0;
	int min_dist = INF;
	// ????°????????????¢???
	for ( int i = 0; i < n; i++ ) {
	    if ( !MST[i] ) {
		if ( DIST[i] < min_dist ) {
		    u = i;
		    min_dist = DIST[i];
		}
	    }
	}

	ans += min_dist;
	
	MST[u] = true;
	size_mst++;

	// MST??¨????????¢?????´??°
	for ( int i = 0; i < n; i++ ) {
	    if ( !MST[i] ) {
		if ( G[u][i] < DIST[i] ) {
		    DIST[i] = G[u][i];
		    NEIGH[i] = u;
		}
	    }
	}
    }

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

    return 0;
}

Measured memory_bytes: 1072
n, m, q = map(int, input().split())
s = [input() for _ in range(n)]
a = [[0] * (m + 1) for _ in range(n + 1)]
b = [[0] * (m + 1) for _ in range(n + 1)]
c = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(m):
        a[i + 1][j + 1] = a[i + 1][j]
        if s[i][j] == '1':
            a[i + 1][j + 1] += 1
for i in range(m + 1):
    for j in range(n):
        a[j + 1][i] += a[j][i]
for i in range(n):
    for j in range(1, m):
        b[i + 1][j + 1] = b[i + 1][j]
        if s[i][j] == s[i][j - 1] == '1':
            b[i + 1][j + 1] += 1
for i in range(m + 1):
    for j in range(n):
        b[j + 1][i] += b[j][i]
for j in range(m):
    for i in range(1, n):
        c[i + 1][j + 1] = c[i][j + 1]
        if s[i][j] == s[i - 1][j] == '1':
            c[i + 1][j + 1] += 1
for j in range(n + 1):
    for i in range(m):
        c[j][i + 1] += c[j][i]
for _ in range(q):
    x1, y1, x2, y2 = map(int, input().split())
    x1 -= 1
    y1 -= 1
    print((a[x2][y2] - a[x1][y2] - a[x2][y1] + a[x1][y1]) -
          (b[x2][y2] - b[x1][y2] - b[x2][y1 + 1] + b[x1][y1 + 1]) -
          (c[x2][y2] - c[x1 + 1][y2] - c[x2][y1] + c[x1 + 1][y1]))


Measured memory_bytes: 176608
#include<bits/stdc++.h>
#include <chrono>
#define INFTY 10000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const int MOD=1000000007;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
double f(double x){
    return exp(x);
}
int main(){
    ll a;
    double b;
    cin>>a>>b;
    ll c = b*100+0.1;
    a *= c;
    a/=100;
    cout<<a<<endl;
    return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1ll<<30;
const ll longINF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

string L;
ll dp[112345][2][2];

ll dfs(int pos, int ismax, int leadzero) {
	ll &res = dp[pos][ismax][leadzero];
	if (~res) return res;
	if (pos == L.size()) return !leadzero;
	
	res = 0;
	
	// 10, 01
	if (!(ismax && L[pos] == '0')) res = (res + dfs(pos + 1, ismax, 0) * 2) % MOD;
	// 00
	res = (res + dfs(pos + 1, ismax && L[pos] == '0', leadzero)) % MOD;
	
	return res;
}

int main() {
	cin >> L;
	
	memset(dp, -1, sizeof(dp));
	ll ans = dfs(0, 1, 1) + 1 % MOD;
	cout << ans << endl;
	
	return 0;
}


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

#define ll long long
#define str string

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

vector < pair<ll, ll> > v;
ll Y[10000000], X[10000000] = {},m = 0,a = 0,b = 0,n = 0, x = 0,y = 0,sum = 0;
str S,Sa;
bool ans = false;

int findSumOfDigits(int n) {
	int sum = 0;
	while (n > 0) {
		
		sum += n%10;
		n /= 10;
	}
	return sum;
}

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
		//Code Line
		for(int i = 0;i < 1000;i++){
		Y[i] = 99999999;
		}
cin >> n >> m >> x >> y;
for(int i = 0;i < n;i++)cin >> X[i];
for(int i = 0;i < m;i++)cin >> Y[i];

for(int i = x + 1;i <= y;i++){
	int count = 0;
for(int j = 0;j < max(n, m);j++){
if(i > X[j] && i <= Y[j]);
else{
  count = -1;
}
}
if(count == 0)ans = true;
}
if(ans)cout << "No War" << endl;
else cout << "War" << endl;

		//Code Line
return 0; 
}


Measured memory_bytes: 2304
import itertools
n = int(input())
t = 1
for i in range(1,n+1):
  t *= i
L = []
for i in range(n):
  L.append(list(map(int,input().split())))
seq = []
for i in range(n):
  seq.append(i)
K = list(itertools.permutations(seq))
ans = 0
keiro = []
for i in range(n):
  T = [0 for j in range(n)]
  keiro.append(T)
for i in range(n):
  for j in range(n):
    keiro[i][j] = ((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2)**0.5
for i in range(len(K)):
  cur = 0
  for j in range(len(K[i])-1):
    cur += keiro[K[i][j]][K[i][j+1]]
  ans += cur
print(ans/t)

Measured memory_bytes: 48108
package main

import "fmt"

func main() {
	var N, M int
	var T int
	var P, X int
	fmt.Scanf("%d", &N)
	initTime := []int{}
	tmpOut := 0
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &T)
		initTime = append(initTime, T)
		tmpOut += T
	}
	fmt.Scanf("%d", &M)
	for i := 0; i < M; i++ {
		fmt.Scanf("%d %d", &P, &X)
		fmt.Println(tmpOut - initTime[P-1] + X)
	}
}


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

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	ll N;
	cin>>N;
    // if(N==1){
    //     cout<<'a'<<"\n";
    //     return 0;
    // }else if(N==2){
    //     cout<<'aa'<<"\n";
    //     cout<<'ab'<<"\n";
    //     return 0;
    // }
    set<string> ans;
    deque<string> q;
    q.push_back("a");
    string s,tmp_s;
    char max_c;
    char c;

    while(!q.empty()){
        s = q.front();q.pop_front();
        if(s.length()==N){
            ans.insert(s);
            continue;
        }
        max_c = 'a';
        rep(i,s.length()){
            if(max_c<s[i]){
                max_c = s[i];
            }
        }
        c = 'a';
        q.push_back(s+c);
        ++c;
        while(max_c+2!=c){
            q.push_back(s+c);
            ++c;
        }
    }
    for(auto v:ans){
        cout<<v<<"\n";
    }   
    return 0;
}

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

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



    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    /////////////////////
    int A,B;

    cin>>A>>B;

    if(A*B%2==1){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
n=str(input())
fi=n[-1:]
n_1=['2','4','5','7','9']
n_2=['0','1','6','8']
n_3=['3']
if fi in n_1:
  print('hon')
elif fi in n_2:
  print('pon')
elif fi in n_3:
  print('bon')

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

#define INF (1<<20)
int h,w,s;
int u[32][32];
struct Group{
	int n,yobi;
}dp[32][32][32][32];

int total[32][32];
int calc(int y1,int y2,int x1,int x2){
	int a,b,c,d;
	b=c=d=0;
	a = total[y2][x2];
	if(x1)b = total[y2][x1-1];
	if(y1)c = total[y1-1][x2];
	if(y1&&x1)d = total[y1-1][x1-1];
	return a-b-c+d;
}
Group dfs(int y1,int y2,int x1,int x2){
	if(dp[y1][y2][x1][x2].n!=-1)return dp[y1][y2][x1][x2];
	Group res={-1,-1},a,b,t;
	if(s<total[h-1][w-1]-calc(y1,y2,x1,x2)){
		res.n = -INF;
		return dp[y1][y2][x1][x2]=res;
	}
	res.n = 1;
	res.yobi = s-(total[h-1][w-1]-calc(y1,y2,x1,x2));
	for(int i=x1;i<x2;i++){
		a = dfs(y1,y2,x1,i);
		b = dfs(y1,y2,i+1,x2);
		t.n = a.n+b.n;
		t.yobi = min(a.yobi,b.yobi);
		if(res.n < t.n)res = t;
		else if(res.n==t.n && res.yobi<t.yobi)res=t;
	}
	for(int i=y1;i<y2;i++){
		a = dfs(y1,i,x1,x2);
		b = dfs(i+1,y2,x1,x2);
		t.n = a.n+b.n;
		t.yobi = min(a.yobi,b.yobi);
		if(res.n < t.n)res = t;
		else if(res.n==t.n && res.yobi<t.yobi)res=t;
	}
	return dp[y1][y2][x1][x2]=res;
}
int main(){
	
	while(cin>>h>>w>>s,h|w|s){
		for(int y=0;y<h;y++)
			for(int x=0;x<w;x++){
				cin>>u[y][x];
				total[y][x] = u[y][x];
			}
		for(int y=1;y<h;y++)total[y][0] += total[y-1][0];
		for(int x=1;x<w;x++)total[0][x] += total[0][x-1];
		for(int y=1;y<h;y++)
			for(int x=1;x<w;x++)
				total[y][x] += total[y-1][x]+total[y][x-1]-total[y-1][x-1];
		memset(dp,-1,sizeof(dp));
		Group ans = dfs(0,h-1,0,w-1);
		cout<<ans.n<<' '<<ans.yobi<<endl;
	}
	return 0;
}

Measured memory_bytes: 9372
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
  for(;;) {
    int n;
    cin >> n;
    if(n == 0) break;
    vector<int> ss;
    for(int i = 0; i < n; i++) {
      int s;
      cin >> s;
      ss.push_back(s);
    }
    sort(ss.begin(), ss.end());
    int sc = 0;
    for(int i = 1; i < n-1; i++) {
      sc += ss[i];
    }
    cout << (sc / (n-2)) << endl;
  }
  return 0;
}

Measured memory_bytes: 3004
// Problem : A - Duplex Printing
// Contest : AtCoder Beginner Contest 157
// URL : https://atcoder.jp/contests/abc157/tasks/abc157_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cp-editor)

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb emplace_back
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
using namespace std;
using namespace __gnu_pbds;
template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }
double pi=acos(-1.0);
int md=1000000007;
int abst(int a)
{return a<0?-a:a;}
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
struct HASH{
  size_t operator()(const pii &x)const{
    return (size_t) x.first * 37U + (size_t) x.second;}};

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int Pow(int n,int x){int ans=1;
 while(x>0)
 {if(x&1)ans=(ans*n)%md;n=(n*n)%md;x=x>>1;}
 return ans;}

 vi fact,inv;
void inverse(int n)
{inv.resize(n+1);inv[0]=1;
for(int i=1;i<=n;i++)inv[i]=Pow(fact[i],md-2);}
void factorial(int n)
{fact.resize(n+1);fact[0]=1;
for(int i=1;i<=n;i++)fact[i]=(fact[i-1]*i)%md;}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

void solve()
{
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;cin>>n;
cout<<n/2+n%2;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
while(t--)
{
    solve();
}
}


Measured memory_bytes: 256
'''
Created on Mar 11, 2013

@author: wukc
'''

import sys

N=999999+1
prime=[True for i in range(N)]
cnt=[0 for i in range(N)]
prime[0:2]=[False,False]

for i in range(2,N):
    cnt[i]=cnt[i-1]
    if prime[i]:
        cnt[i]+=1
        for j in range(2*i,N,i): prime[j]=False
        
for l in sys.stdin:
    n=int(l)
    print cnt[n]        
    
#print prime

Measured memory_bytes: 67760
n,m,*a=map(int,open(0).read().split())
mod=10**9+7
p=[1]
a=iter(a)
b=next(a,-1)
if 1==b:
    p.append(0)
    b=next(a,-1)
else:
    p.append(1)
for i in range(2,n+1):
    if i==b:
        p.append(0)
        b=next(a,-1)
    else:
        p.append((p[i-1]+p[i-2])%mod)
print(p[-1])

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

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

  if ((n % 500) == 0) {
    cout << "Yes" << endl;
  } else if ((n % 500) <= a) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
    
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int cnt=0;
        int a=sc.nextInt();
        cnt+=a;
        int b=sc.nextInt();
        cnt+=b*5;
        int c=sc.nextInt();
        cnt+=c*10;
        int d=sc.nextInt();
        cnt+=d*50;
        int e=sc.nextInt();
        cnt+=e*100;
        int f=sc.nextInt();
        cnt+=f*500;
        
        if(cnt/1000!=0){
            System.out.println("1");
        }else{
            System.out.println("0");
        }
    }
}


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

int main(){
	int N, max = 0, step = 0;
	vector<int> H, answer;
	
	cin >> N;
	for(int i = 0; i < N; i++){
		int tmp;
		cin >> tmp;
		H.push_back(tmp);
	}
	
	for(int i = 1; i < N; i++){
		if(H[i-1] >= H[i]) step++;
		else{
			if(step > max) max = step;
			step = 0;
		}
	}
	
	
	if(step > max) max = step;
	
	cout << max << endl;
	
	return 0;
}

Measured memory_bytes: 892
# DP, 累積和
n, k = list(map(int, input().split()))
s = list()
for i in range(k):
     l, r = list(map(int, input().split()))
     s.append((l, r))

mod = 998244353
i = 1
dp = [0] * (n+1)
dp[1] = 1
dpsum = [0] * (n+1)
dpsum[1] = 1
for i in range(2, n+1):
    for l, r in s:
        li = i-r
        ri = i-l
        if ri < 1: continue
        li = max(li, 1)
        dp[i] = (dp[i] + dpsum[ri] - dpsum[li-1]) % mod
    dpsum[i] = (dpsum[i-1] + dp[i]) % mod
    
print(dp[n])


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

int A[20], n, q, k;

bool Comb(int i, int m){
  if(m == 0) return true;
  if(i == n) return false;
  return Comb(i + 1, m - A[i]) || Comb(i + 1, m);
}

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

  cin >> q;
  for(int i = 0; i < q; i++){
    cin >> k;
    if(Comb(0, k)) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
from sys import stdin


def main():
    input()
    A = tuple(map(int, stdin.readline().split()))
    B = tuple(map(int, stdin.readline().split()))
    pre = A[0]
    ans = 0
    for a, b in zip(A[1:], B):
        tmp1 = pre if pre < b else b
        b -= tmp1
        tmp2 = a if a < b else b
        ans += tmp1 + tmp2
        pre = a - tmp2
    print(ans)
    return


main()


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second

//int dxy[5] = {0, 1, 0, -1, 0};
// assign avl ncm dijkstra geo2 kruskal graph uf lca BIT
// matrix dinic next_combination topcoder lcm

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

    Int(N);
    for (int n = 1; n <= 3500; n++) { 
        for (int w = 1; w <= 3500; w++) {
            int kyoko = N * n * w;
            int yui = 4 * n * w - N * w - N * n;
            if (yui >= 1 && kyoko % yui == 0) {
                cout << kyoko / yui << " " << n << " " << w << endl;
                return 0;
            }
        }
    }


    return 0;
}


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

int a, b;
string str1, str2, str3;

int main()
{
	cin >> str1 >> str2;
	scanf("%d%d", &a, &b);
	cin >> str3;
	if (str1 == str3) a--;
	else b--;
	printf("%d %d", a, b);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}


int main() {
    int n,k;
    cin >> n >> k;
    int v[n];
    rep(i,n){
        cin >> v[i];
    }
    int ans = 0;
    rep(i,k+1){
        if(i==0){
            continue;
        }
        if(i>n){
            continue;
        }
        int w[i];
        rep(j,i+1){
            rep(l,j){
                w[l] = v[l];
            }
            rep(l,i-j){
                w[i-1-l] = v[n-1-l];
            }
            sort(w,w+i);
            int tmp = 0;
            rep(l,i){
                //cout << w[l] << ' ';
                tmp += w[l];
            }
            rep(l,min(k-i,i)){
                if(w[l]<0){
                    tmp -= w[l];
                }else{
                    break;
                }
            }
            ans = max(ans,tmp);
            //cout << endl;
        }
    }


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


Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse = True)
bc = [0] * M
for i in range(M):
  bc[i] = list(map(int, input().split()))
bc = sorted(bc, key = lambda x:x[1], reverse = True)


#めぐる式二分探索
#indexが条件を満たすか判定
def isOK(index, key, A):
  if A[index] < key:
    return True
  else:
    return False
  
#にぶたん
#A : 配列
def binary_search(key, A):
  N = len(A)
  ng = -1
  ok = N
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    if isOK(mid, key, A):
      ok = mid
    else:
      ng = mid
  return ok
  
#a = [1, 14, 32, 51, 51, 51, 243, 419, 750, 910]

#print(A)
#print(binary_search(5, A))
#二分探索の結果がそれを超える枚数
fix = 0
fix2 = 0
fix3 = 0
ans = 0
for i in range(M):
  now = bc[i]
  x = binary_search(now[1], A)
  fix = x
  fix3 = now[0]
  #print(fix, fix2, fix3, ans)  
  if fix + fix2 + fix3 >= N:
    fix3 = N - fix - fix2
    ans += sum(A[:fix]) + now[1] * fix3
    print(ans)
    quit()
  else:
    fix2 += fix3
    ans += now[0] * now[1]

    
ans += sum(A[:(N - fix2)])
print(ans)
  
  
  



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

#define N 51

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const int MOD = 1e9 + 7;
int n;
ll k;

vvl operator*(vvl &a, vvl &b)
{
	vvl res(n, vl(n, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
				res[i][j] = (res[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
		}
	}
	return res;
}

vvl solve(vvl &a, ll d)
{
	if (d == 1)
		return a;
	vvl tmp = solve(a, d / 2);
	tmp = tmp * tmp;
	if (d & 1ll)
		return tmp * a;
	return tmp;
}

int main()
{
	vvl a(N, vl(N));
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	vvl res = solve(a, k);
	ll ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ans = (ans + res[i][j]) % MOD;
	cout << ans << endl;
	return 0;
}


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

#define F first
#define S second
#define prev azaza
#define MP make_pair
#define PB push_back

using namespace std;
typedef long long ll;
typedef long double ld;

const int max_n = 1011, inf = 1000111222;

char m[max_n][max_n];

int main()
{
    //freopen("input.txt", "r", stdin);
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    for (int j = 0; j < w; ++j) {
        for (int i = 0; i < h; ++i) {
            if (i < b) {
                m[i][j] = '1';
            } else {
                m[i][j] = '0';
            }
        }
    }
    for (int j = w - 1; j >= w - a; --j) {
        for (int i = 0; i < h; ++i) {
            m[i][j] = (m[i][j] == '0' ? '1' : '0');
        }
    }
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            printf("%c", m[i][j]);
        }
        printf("\n");
    }
    return 0;
}




Measured memory_bytes: 2176
# https://atcoder.jp/contests/abc106/tasks/abc106_b

require 'prime'

N = gets.to_i

if N < 105
  puts 0
  exit
end

ans = 1
(106..N).each do |x|
  ans += 1 if x.odd? && Prime.prime_division(x).inject(1) { |result, set| result * (set[1] + 1) } == 8
end

puts ans


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

int main() {
    int n;
    cin >> n;
    vector<int> edge(n);
    bool poly_flag = true;
    int sum = 0;
    for (int i=0; i < n; i++){
        int l_i;
        cin >> l_i; 
        edge[i] = l_i;
        sum = l_i + sum;
    }

    for (int i=0; i < n; i++){
        if (sum - edge[i] <= edge[i]){
            poly_flag = false;
            break;
        }
    }

    //cout << "get" << endl;


    if (poly_flag == true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
# coding: utf-8
import sys
from math import log10
from functools import reduce

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
log = 0.0
for a in A:
    if a == 0:
        print(0); exit()
    log += log10(a)

if log > 18:
    print(-1); exit()

answer = reduce(lambda x, y: x*y, A)
print(answer if answer <= 10 ** 18 else -1)


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

using namespace std;

int main() {
  long long x;
  cin >> x;

  long long r = x % 11;
  long long ans = x / 11 * 2;

  if (r == 0) {
    cout << ans << endl;
  } else if (r <= 6) {
    cout << ans + 1 << endl;
  } else {
    cout << ans + 2 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #B
    #input
    A, V = map(int, input().split())
    B, W = map(int, input().split())
    T = int(input())

    #output
    #A < Bの時
        #V <= Wであれば、相手はひたすら逃げれば良く、この時鬼は相手を捕まえられない。
        #V > Wであれば、鬼は1秒に相手との距離をV-Wだけ詰められる。
        #B-A//V-WがTより小さいか同じ場合は鬼は相手を捕まえられる。
    #A > Bの時
        #上の議論とほぼ同じ。

    if A < B:
        if V <= W:
            print("NO")
        else:
            if (V-W)*T >= B-A:
                print("YES")
            else:
                print("NO")
    elif A > B:
        if V <= W:
            print("NO")
        else:
            if (V-W)*T >= A-B:
                print("YES")
            else:
                print("NO")

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Measured memory_bytes: 9236
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#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;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;



int main(){
    int N;
    cin >> N;
    int p[N];
    REP(i,N) cin >> p[i],p[i]-=1;
    int num=0;
    bool exist=true;
    if(p[0]==0){
        ++num;
        swap(p[0],p[1]);
    }
    while(true){
        exist=true;
        for(int i=1;i<N;++i){
            if(p[i]==i){
                exist=false;
                if(p[i+1]==i+1){
                    swap(p[i],p[i+1]);
                    ++num;
                }
                else{
                    swap(p[i],p[i-1]);
                    ++num;
                }
            }
        }
        if(exist) break;
    }
    cout << num << endl;
}

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


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

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    string s, t;
    cin >> s >> t;

    map<char, ll> sc, tc;

    for (int i = 0; i < s.size(); i++)
    {
        sc[s[i]]++;
    }

    for (int i = 0; i < t.size(); i++)
    {
        tc[t[i]]++;
    }

    map<ll, ll> s1, t1;

    for (auto x : sc)
    {
        s1[x.second]++;
    }

    for (auto x : tc)
    {
        t1[x.second]++;
    }

    for (int i = 0; i <= s.size(); i++)
    {
        if (s1[i] != t1[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}


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

bool judge(ll N, vector<ll>& D){
    ll tmp = N;
    //vector<ll> v;
    while(tmp > 0){
        ll r = tmp % 10;
        rep(i,D.size()){
            if(r == D[i]){
                return false;
            }
        }
        //v.push_back(r);
        tmp /= 10;
    }
    return true;
}
int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> D(K);
    rep(i,K){
        cin >> D[i];
    }
    ll M = N;
    while(!judge(M,D)){
        M++;
    }
    cout << M << endl;
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,a,b,cnt=0;
	bool f=false;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		if(a==b){
			cnt++;
			if(cnt>=3) f=true;
		}else{
			cnt=0;
		}
	}
	if(f){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}


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

using namespace std;

int main() {
    int n = 4;
    vector<vector<int>> g(n, vector<int>(n, n));
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a - 1][b - 1] = 1;
        g[b - 1][a - 1] = 1;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                g[j][k] = min(g[j][k], g[j][i] + g[i][k]);
            }
        }
    }

    int d = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d = max(d, g[i][j]);
        }
    }

    cout << (d == n - 1 ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256