akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<char> Vc;
typedef vector<string> Vs;
typedef vector<bool> Vb;
typedef vector<vector<int>> VVi;
typedef vector<vector<ll>> VVl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> P;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }
inline void YES() { cout << "YES" << endl; }
inline void Yes() { cout << "Yes" << endl; }
inline void NO() { cout << "NO" << endl; }
inline void No() { cout << "No" << endl; }

const int inf = 1 << 30;
const ll linf = 1LL << 60;
const int MOD = 1000000007;

#include <limits.h>

template <class T>
struct CumSum2D {
private:
	const int h, w;
	vector<vector<T>> data;
public:
	CumSum2D(int h, int w) : data(h + 1, vector<T>(w + 1, (T)0)), h{ h + 1 }, w{ w + 1 } {}
	void add(int i, int j, T val) { if ((i + 1) < h && (j + 1) < w) data[i + 1][j + 1] += val; }
	void cumulate() { REP1O(i, h) REP1O(j, w) data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1]; }

	// [s, g) , s : btm-left, g : top-right
	T get(int si, int sj, int gi, int gj) { return data[gi][gj] + data[si][sj] - data[gi][sj] - data[si][gj]; }
};

int n, k;
Vi vx, vy;
VVi pts;

void init()
{
	cin >> n >> k;
	vx.resize(n); vy.resize(n);
	pts.resize(n, Vi(2));
	REP(i, n) 
	{
		cin >> vx[i] >> vy[i];
		pts[i][0] = vx[i];
		pts[i][1] = vy[i];
	}

	sort(ALL(vx)); sort(ALL(vy));
}


int main()
{
	init();

	ll ans = LLONG_MAX;

	CumSum2D<int> cum(n, n);
	REP(i, n)
	{
		int i_x = lower_bound(ALL(vx), pts[i][0]) - vx.begin();
		int i_y = lower_bound(ALL(vy), pts[i][1]) - vy.begin();
		cum.add(i_x, i_y, 1);
	}
	cum.cumulate();

	REP(l, n - 1)
		for (int r = l + 1; r < n; ++r)
		REP(d, n - 1)
			for (int u = d + 1; u < n; ++u)
			{
				int n = cum.get(l, d, r + 1, u + 1);
				if (n >= k)
					chmin(ans, (ll)(vx[r] - vx[l])* (ll)(vy[u] - vy[d]));
			}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;
ll const MAX_N = 510000;
ll const MOD = 1000000007;

int main() {
    ll N, K;
    string S;
    cin >> N >> S >> K;

    char c = S[K - 1];
    rep(i, S.length()) {
        if (c != S[i])
            cout << "*";
        else
            cout << c;
    }

    cout << endl;

    return 0;
}


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

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll mx = max(a * c, max(a * d, max(b * c, b * d)));
  cout << mx << endl;
  return 0;
}


Measured memory_bytes: 3620
N,M=[int(i) for i in input().split()]
Ai = []
Bi = []
for i in range(N):
  A,B = list(map(int, input().strip().split(' ')))
  Ai.append(A)
  Bi.append(B)
  c = zip(Ai,Bi)
C=sorted(c)
Ai,Bi=zip(*C)

n=0
p=0
r=M

while 1:
  if r<=Bi[n]:
    p += Ai[n]*r
    break
  else :
    p += Ai[n]*Bi[n]
    r -= Bi[n]
    n += 1
print(p)


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

int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> in(n,0);
    for(int i=0;i<k;i++){
      int d;
      cin>>d;
      int t;
      for(int j=0;j<d;j++){
        cin>>t;
        in[t-1]++;
      }
    }
    int ans=0;
    for(auto x:in){
      if(x==0){
        ans++;
      }
    }
    cout<<ans<<endl;


    return 0;
}


Measured memory_bytes: 3636
package main

import (
	"fmt"
	"strings"
)

var (
	o   string
	e   string
	ans string
)

func main() {
	fmt.Scan(&o)
	fmt.Scan(&e)
	O := strings.Split(o, "")
	E := strings.Split(e, "")
	if len(O) == len(E) {
		for i := 0; i < len(O); i++ {
			ans += O[i] + E[i]
		}
	} else {
		for i := 0; i < len(E); i++ {
			ans += O[i] + E[i]
		}
		ans += O[len(O)-1]
	}
	fmt.Println(ans)

}


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

const int mod = 998244353;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int fastpow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}

const int MAXN = 1000010;
int fac[MAXN], inv[MAXN], n, K;
int C(int a, int b) { return (LL) fac[a] * inv[b] % mod * inv[a - b] % mod; }
int main() {
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i != MAXN; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXN; ++i)
		inv[i] = mul(inv[i - 1], inv[i]);
	std::cin >> K >> n;
	int ans = 0;
	for (int A = 0; A <= n; ++A) {
		int B = n - A;
		if (B >= K) {
			reduce(ans += C(n, A) - mod);
			if (A >= B - K + 1) {
				reduce(ans -= C(n, A - B + K - 1));
			}
		}
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 8064
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const double EPS=1e-8;
typedef vector<double>vec;
typedef vector<vec>mat;
inline double ABS(double a){return max(a,-a);}
vec gauss_jordan(const mat &A,const vec &b){
	int n=A.size();
	mat B(n,vec(n+1));
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)B[i][j]=A[i][j];
	for(int i=0;i<n;i++)B[i][n]=b[i];
	for(int i=0;i<n;i++){
		int pivot=i;
		for(int j=i;j<n;j++){
			if(ABS(B[j][i])>ABS(B[pivot][i]))pivot=j;
		}
		swap(B[i],B[pivot]);
		if(ABS(B[i][i])<EPS)break;
		for(int j=i+1;j<=n;j++)B[i][j]/=B[i][i];
		for(int j=0;j<n;j++){
			if(i!=j){
				for(int k=i+1;k<=n;k++)B[j][k]-=B[j][i]*B[i][k];
			}
		}
	}
	vec x(n);
	for(int i=0;i<n;i++)x[i]=B[i][n];
	return x;
}
char sA[7][7];
char sB[7][7];
vector<int>v[400];
map<vector<int>,int>m;
int sz;
int perm[7];
int h,w;
void calc(int a,int b){
	if(a==h){
		vector<int>tmp;
		for(int j=0;j<a;j++)tmp.push_back(perm[j]);
		v[sz]=tmp;
		m[tmp]=sz++;
		return;
	}
	for(int i=b;i<=w;i++){
		perm[a]=i;
		calc(a+1,i);
	}
}
int t[7][7];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		h=a;w=b;
		for(int i=0;i<a;i++)scanf("%s",sA+i);
		for(int i=0;i<a;i++)scanf("%s",sB+i);
		m.clear();
		sz=0;
		calc(0,0);
		//printf("%d\n",sz);
		mat A(sz,vec(sz));
		vec B(sz);
		for(int i=0;i<sz;i++){
			if(v[i][0]==w){
				A[i][i]=1;
				continue;
			}
			A[i][i]=a*b*2;
			for(int j=1;j<=a;j++)for(int k=1;k<=b;k++){
				B[i]+=j*k;
				for(int x=0;x<a;x++)for(int y=0;y<b;y++)t[x][y]=0;
				for(int l=0;l<a;l++)for(int o=0;o<v[i][l];o++)t[l][b-1-o]=1;
				for(int x=0;x<j;x++)for(int y=0;y<k;y++){
					if(sB[x][y]=='B')t[x][y]=1;
					else t[x][y]=0;
				}
				vector<int>to(a);
				for(int l=a-1;l>=0;l--){
					int r=0;
					for(int o=b-1;o>=0;o--){
						if(!t[l][o])break;
						r++;
					}
					if(l<a-1)r=min(r,to[l+1]);
					to[l]=r;
				}
				int tv=m[to];
				A[i][tv]-=1;
			}
			for(int j=1;j<=a;j++)for(int k=1;k<=b;k++){
				B[i]+=j*k;
				for(int x=0;x<a;x++)for(int y=0;y<b;y++)t[x][y]=0;
				for(int l=0;l<a;l++)for(int o=0;o<v[i][l];o++)t[l][b-1-o]=1;
				for(int x=0;x<j;x++)for(int y=0;y<k;y++){
					if(sB[x][y]=='W')t[x][y]=1;
					else t[x][y]=0;
				}
				vector<int>to(a);
				for(int l=a-1;l>=0;l--){
					int r=0;
					for(int o=b-1;o>=0;o--){
						if(!t[l][o])break;
						r++;
					}
					if(l<a-1)r=min(r,to[l+1]);
					to[l]=r;
				}
				int tv=m[to];
				A[i][tv]-=1;
			}
		}
	//	for(int i=0;i<sz;i++){
		//	for(int j=0;j<sz;j++)printf("%.2f ",A[i][j]);
	//		printf("%.2f\n",B[i]);
		//}
		vec x=gauss_jordan(A,B);
		
		vector<int>ans(a);
		for(int i=a-1;i>=0;i--){
			int r=0;
			for(int j=b-1;j>=0;j--){
				if(sB[i][j]!=sA[i][j])break;
				r++;
			}
			if(i<a-1)r=min(r,ans[i+1]);
			ans[i]=r;
		}
		printf("%.12f\n",x[m[ans]]);
	}
}

Measured memory_bytes: 2060
#include <iostream>
using namespace std;
int main(void){
  int W;
  int H;
  int x;
  int y;
 int r;
  cin>>W;
  cin>>H;
  cin>>x;
  cin>>y;  
  cin>>r;
  


  

  
  if((x-r)>=0&&(x+r)<=W&&(y-r)>=0&&(y+r)<=H){
      cout<<"Yes"<<endl;
  }
  else{
      cout<<"No"<<endl;
  }

}


Measured memory_bytes: 3116
#include <iostream>
using namespace std;
int n, c[505], s[505], f[505];
int main() {
	int i, j, t;
	cin>>n;
	for(i=0; i<n-1; i++) cin>>c[i]>>s[i]>>f[i];
	for(i=0; i<n; i++) {
		for(j=i, t=0; j<n-1; j++) t = max(s[j], (t+f[j]-1)/f[j]*f[j]) + c[j];
		cout<<t<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main(){
string S,T;
cin >> S >> T;
int n = S.size();
string ans = "No";
for(int i = 0; i < n; i++){
string s = S;
for(int j = 0; j < n; j++){
if(j == n-1)S[0] = s[j];
S[j+1] = s[j];
}
if(S == T)ans = "Yes";

}
cout << ans << endl;
}

Measured memory_bytes: 256
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

llong M = 1000000007;

int main(){
    int N;
    cin >> N;
    
    llong current = 1;

    REP(i, N) {
        current *= i+1;
        current %= M;
    }

    cout << current << endl;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
v = list(map(int, input().split()))

v1 = [v[2 * i] for i in range(len(v) // 2)]
v2 = [v[2 * i + 1] for i in range(len(v) // 2)]

v1in = {}
v2in = {}

for i in range(len(v1)):
    if v1[i] in v1in:
        v1in[v1[i]] += 1
    else:
        v1in[v1[i]] = 1

    if v2[i] in v2in:
        v2in[v2[i]] += 1
    else:
        v2in[v2[i]] = 1

if (len(v1in) == 1) and (len(v2in) == 1):
    if v[0] == v[1]:
        print(len(v1))
    else:
        print(0)
elif (len(v1in) == 1) and (len(v2in) != 1):
    max_k = max(v2in, key=v2in.get)
    if max_k == v[0]:
        del v2in[max_k]
        print(len(v2) - max(v2in.values()))
    else:
        print(len(v2) - v2in[max_k])
elif (len(v1in) != 1) and (len(v2in) == 1):
    max_k = max(v1in, key=v1in.get)
    if max_k == v[1]:
        del v1in[max_k]
        print(len(v1) - max(v1in.values()))
    else:
        print(len(v1) - v1in[max_k])
else:
    v1max_k = max(v1in, key=v1in.get)
    v2max_k = max(v2in, key=v2in.get)

    if v1max_k == v2max_k:
        v1max = v1in[v1max_k]
        del v1in[v1max_k]
        v1max2 = max(v1in.values())

        v2max = v2in[v2max_k]
        del v2in[v2max_k]
        v2max2 = max(v2in.values())

        print(min(len(v1) - v1max + len(v2) - v2max2,
                  len(v1) - v1max2 + len(v2) - v2max))
    else:
        print(len(v1) - v1in[v1max_k] + len(v2) - v2in[v2max_k])


Measured memory_bytes: 17408
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

int main() {
    int r, c, n;
    cin >> r >> c >> n;
    
    vector<pair<int, int>> p(n * 2);
    int k = 0;
    for (int i = 0; i < n; i++) {
        int m = 0;
        for (int j = 0; j < 2; j++) {
            int x, y;
            cin >> x >> y;
            if (x == 0 || x == r || y == 0 || y == c) {
                int u;
                if (y == 0) u = x;
                else if (x == r) u = r + y;
                else if (y == c) u = r + c + (r - x);
                else if (x == 0) u = r + c + r + (c - y);
                p[k++] = { u, i };
                m++;
            }
        }
        if (m < 2) k -= m;
    }

    sort(p.begin(), p.begin() + k);

    vector<int> v;
    set<int> s;
    for (int i = 0; i < k; i++) {
        if (s.count(p[i].second) > 0) {
            if (p[i].second == v.back()) {
                v.pop_back();
                s.erase(p[i].second);
            } else {
                cout << "NO" << endl;
                quick_exit(0);
            }
        } else {
            v.push_back(p[i].second);
            s.insert(p[i].second);
        }
    }

    cout << "YES" << endl;

    return 0;
}

Measured memory_bytes: 4348
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int n = s.length();
    int m = n/2;

    int count = 0;
    rep(i,m)
    {
        if (s[i]!=s[n-1-i])
        {
            count++;
        }
    }
    cout << count << endl;
    
    
}




Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X, A):

    ans = sys.maxsize
    mc = [(sys.maxsize, -1)] * N
    for k in range(N):
        ac = 0
        for i in range(N):
            mc[i] = min(mc[i], (A[i-k], k), key=lambda x: x[0])
            ac += A[i-mc[i][1]]
        ac += k*X
        ans = min(ans, ac)

    return ans


def main():
    N, X = read_int_n()
    A = read_int_n()
    print(slv(N, X, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 62572
import sys
sys.setrecursionlimit(10**7)

n = int(input())
rev_g = [[] for _ in range(n+1)]
for i in range(n-1):
    a = int(input())
    rev_g[a].append(i+2)

def f(v):
    m = len(rev_g[v])
    if m == 0:
        return 0
    q = []
    for nv in rev_g[v]:
        q.append(f(nv))
    q.sort()
    dp = [0] * (m+1)
    for i in range(m):
        dp[i+1] = max(q[i]+1, dp[i]+1)
    return dp[m]


print(f(1))


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

int main(){
    string s;
    cin >> s;
    int start, end;
    for (int i = 0; i < s.size(); i++){
        if(s.at(i) == 'A'){
            start = i;
            break;
        }
    }
    for (int i = s.size() - 1; i >= 0; i--){
        if(s.at(i) == 'Z'){
            end = i;
            break;
        }
    }
    cout << end - start + 1<< endl;
}

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

using namespace std;

int main()
{
	string s;
	cin >> s;
	int ans = 0,max = 0,len = s.length();

	for (int i = 0; i < len; ++i)
	{
		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')
		{
			ans++;
		}
		else
		{
			ans = 0;
		}
		
		if (ans > max)
		{
			max = ans;
		}	
	}

	cout << max;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void)
{
	int i,n;
	char s[10000];
	cin>>n>>s;
	for(i=0;s[i]!='\0';i++){
		s[i]+=n;
		if(s[i]>90){
			s[i]-=26;
		}
	}
	cout<<s<<endl;
	return 0;
}

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

using ll= long long;
const ll INF=1LL<<60;
const ll MOD=1e9+7;

int main(){
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    int min1, min2;
    min1=H1*60+M1;
    min2=H2*60+M2;
    int res=0;
    res=min2-K-min1;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3632
import java.util.*;

class Main {
    private static int[][] c = new int[10][10];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt();
        int w = scanner.nextInt();
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[i].length; j++) {
                c[i][j] = scanner.nextInt();
            }
        }

        AllPairShortestPath all = new AllPairShortestPath(c.length);
        all.allPairShortestPath(c);
        int mp = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int num = scanner.nextInt();
                if (num != -1)mp += all.distancematrix[num][1];
            }
        }
        System.out.println(mp);
    }
}

class AllPairShortestPath {
    int distancematrix[][];
    private int numberofvertices;
//    public static final int INFINITY = 1001;
    AllPairShortestPath(int numberofvertices) {
        distancematrix = new int[numberofvertices][numberofvertices];
        this.numberofvertices = numberofvertices;
    }
    void allPairShortestPath(int adjacencymatrix[][]){
        for (int source = 0; source < numberofvertices; source++) {
            System.arraycopy(adjacencymatrix[source], 0, distancematrix[source], 0, numberofvertices);
        }
        for (int intermediate = 0; intermediate < numberofvertices; intermediate++) {
            for (int source = 0; source < numberofvertices; source++)
            {
                for (int destination = 0; destination < numberofvertices; destination++)
                {
                    if (distancematrix[source][intermediate] + distancematrix[intermediate][destination]
                            < distancematrix[source][destination])
                        distancematrix[source][destination] = distancematrix[source][intermediate]
                                + distancematrix[intermediate][destination];
                }
            }
        }
    }
}


Measured memory_bytes: 43408
"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs



mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

    if d == 0:
        print (pow(x,n,mod))
        continue
    elif x == 0:
        print (0)
        continue
    elif n == 1:
        print (x)
        continue

    fi = x * inverse(d,mod) % mod
    
    if fi+n-1 >= mod or fi % mod == 0:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    if fi >= 2:
        print (pow(d,n,mod) * fac[(fi+n-1) % mod] * inv[(fi-1) % mod] % mod)
    else:
        print (pow(d,n,mod) * fac[(fi+n-1) % mod]  % mod)
    


Measured memory_bytes: 115440
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc139
{
    class abc139b
    {
        static void Main(string[] args)
        {
            var buf = Console.ReadLine().Split();
            var a = int.Parse(buf[0]);
            var b = int.Parse(buf[1]);
            var r = Solve(a, b);
            Console.WriteLine(r);
        }

        static int Solve(int a, int b)
        {
            var n = 0;
            var r = 1;
            while(r < b) {
                ++n;
                r += a - 1;
            }
            return n;
        }
    }
}


Measured memory_bytes: 11092
<?php
$n = fgets(STDIN);
$line = fgets(STDIN);
$array = explode(" ", $line);

$count = 0;
for ($i = 0; $i <= count($array); $i = $i + 2) {
    if ($array[$i] % 2 != 0) {
        $count++;
    }
}

echo $count;


Measured memory_bytes: 16176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll W, H, x, y;
    cin >> W >> H >> x >> y;
    int a = 0;
    if(x+x==W&&y+y==H){
        ++a;
    }
    double b = ((double)W * (double)H) / 2;
    cout << b << " " << a << "\n";

    return 0;
}

Measured memory_bytes: 256
using System;

namespace AtCoder{
    public static class AtCoder{
        public static void Main(){
            var input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            int c = int.Parse(input[2]);
            int d = int.Parse(input[3]);

            while (true){
                c -= b;
                if (c <= 0){
                    Console.WriteLine("Yes");
                    break;
                }
                a -= d;
                if ( a <= 0){
                    Console.WriteLine("No");
                    break;
                }
            }
        }
    }
}

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

int main() {
  int n, x, t;
  cin >> n >> x >> t;
  if (n % x == 0) {
    cout << (n / x) * t;
  } else {
    cout << (n / x) * t + t;
  }
  return 0;
}


Measured memory_bytes: 3644
from fractions import gcd
H,W,T=map(int,input().split());M=10**9+7;a=gcd(H,T);b=gcd(W,T);H//=a;W//=b;print(pow(pow(2,H,M)+pow(2,W,M)+pow(2,gcd(H,W),M)-3,a*b,M))

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int n;
    cin >> n;
    LL s = 0;
    for(int i = 1; i <= n; ++i) {
        if(i % 3 != 0 && i % 5 != 0) s += i;

    }
    cout << s << endl;
    return 0;
}



Measured memory_bytes: 3656
#include "math.h"
#include <algorithm>
#include <complex>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define ifor(i, a, b) for (int i = (a); i < (b); i++)
#define rfor(i, a, b) for (int i = (b)-1; i >= (a); i--)
#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;
typedef long double ld;
typedef long long int lli;

lli n;
string str[2] = {"First", "Second"};
void solve(vector<lli> a, lli depth)
{
    bool flag = false;
    int odd = 0, even = 0;
    rep(i, n)
    {
        if (a[i] == 1) {
            flag = true;
        }
        if (a[i] & 1) {
            odd++;
        } else {
            even++;
        }
    }
    if (flag) {
        lli sum = 0;
        rep(i, n)
        {
            sum += a[i] - 1;
        }
        if (sum & 1) {
            cout << str[depth % 2] << endl;
        } else {
            cout << str[(depth + 1) % 2] << endl;
        }
        exit(0);
    }
    if (even % 2 == 1) {
        cout << str[(depth) % 2] << endl;
        exit(0);
    } else if (odd != 1) {
        cout << str[(depth + 1) % 2] << endl;
        exit(0);
    } else {
        rep(i, n) if (a[i] % 2) a[i]--;
        lli g = a[0];
        rep(i, n) g = __gcd(g, a[i]);
        rep(i, n) a[i] /= g;
        solve(a, depth + 1);
    }
}
int main()
{
    cin >> n;
    vector<lli> a(n, 0);
    rep(i, n) cin >> a[i];
    solve(a, 0);
}


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

int main(){
    int n,m,x;
    cin>>n>>m>>x;
    vector<int> c(n);
    int a[12][12];
    for(int i=0;i<n;++i){
        cin>>c[i];
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    ll csum;
    ll ans=1e9;
    bool ch=true;
    bool ok;
    vector<int> sum(m,0);
    for (int bit = 0; bit < (1 << n); ++bit) {
        sum.assign(m,0);
        ok=true;
        csum=0;
        for (int i = 0; i < n; ++i) {
            if (bit & (1 << i)){
                csum+=c[i];
                for(int j=0;j<m;++j)sum[j]+=a[i][j];
            }
        }
        for(int j=0;j<m;++j){
            if(sum[j]<x){
                ok=false;
                break;
            }
        }
        if(ok){
            ans=min(ans,csum);
            ch=false;
        }
    }
    if(ch)ans=-1;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
    int a[4],b[4];
    while (cin>>a[0]>>a[1]>>a[2]>>a[3]) {
        cin>>b[0]>>b[1]>>b[2]>>b[3];
        int hit = 0,blow = 0;
        for(int i=0;i<4;i++){
            for(int s=0;s<4;s++){
                if(a[i]==b[s])blow++;
            }
        }
        for(int i=0;i<4;i++)if(a[i]==b[i])hit++;
        cout << hit <<" "<< (blow-hit)<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin>>n;
  
  if(n==1) cout<<0<<endl;
  else cout<<1<<endl;
  
  
  return 0;
}

Measured memory_bytes: 3620
require 'set'

n = gets.to_i
n.times do
  s = gets.chomp

  set = Set.new
  (1..s.length-1).each do |i|
    p0, p1 = s[0...i], s[i...s.length]

    set << "#{p0}#{p1}" \
        << "#{p0}#{p1.reverse}" \
        << "#{p0.reverse}#{p1}" \
        << "#{p0.reverse}#{p1.reverse}" \
        << "#{p1}#{p0}" \
        << "#{p1}#{p0.reverse}" \
        << "#{p1.reverse}#{p0}" \
        << "#{p1.reverse}#{p0.reverse}"
  end

  puts set.length
end

Measured memory_bytes: 6468
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s= sc.next();
		for (int i=0;i<s.length();i++) {
			if (s.charAt(i)=='R'||s.charAt(i)=='L') {
				if (i%2==0&&s.charAt(i)!='R')	{
					System.out.println("No");
					return ;
				} else if (i%2==1&&s.charAt(i)!='L'){
					System.out.println("No");
					return ;
				}
			}
		}
		{
			System.out.println("Yes");
			return ;
		}
	}
}


Measured memory_bytes: 35548
#include<iostream>
#include<string>
#include<utility>
#include<algorithm>
#include<math.h>
using namespace std;

int main (){
    int N;
    int h[100007] = {};
    long long H[100007] = {};

    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> h[i];
    }

    H[0] = 0;
    H[1] = abs(h[1]-h[0]);

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

    cout << H[N-1] << endl;

}

Measured memory_bytes: 1408
#include<stdio.h>
void main()
{
	int A, B, C, D;
	scanf("%d %d %d %d", &A, &B, &C, &D);
	while (1)
	{
		C -= B;
		if (C <= 0)
		{
			printf("Yes");
			break;
		}
		A -= D;
		if (A <= 0)
		{
			printf("No");
			break;
		}
	}
}

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


int main() {
    int a,b;
    cin >> a >> b;
    int ans = 0;
    rep(i,b - a) {
        ans += i;
    }
    cout << ans - a << endl;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;

inline ll read(){
    ll Hashimoto=0;
	bool Kanna=1;
    char I_Love=getchar();
    while(I_Love<'0'||I_Love>'9'){
        if(I_Love=='-')Kanna=0;
        I_Love=getchar();
    }
    while(I_Love>='0'&&I_Love<='9'){
        Hashimoto=Hashimoto*10+I_Love-'0';
        I_Love=getchar();
    }
    return (Kanna?Hashimoto:-Hashimoto);
}
template<typename T1,typename T2> inline void Umax(T1 &a,T2 b){
	if(a<b)a=b;
}
template<typename T1,typename T2> inline void Umin(T1 &a,T2 b){
	if(a>b)a=b;
}

#define I_Love_Hashimoto_Kanna main
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
#define file freopen("I_Love_Hashimoto_Kanna.out","w",stdout);
#define RE cout<<"I_Love_Hashimoto_Kanna"<<endl;
#define Tone(Kanna) cout<<Kanna<<endl;
#define Tall(Hashimoto,Kanna) for(int I_Love=0;I_Love<(Kanna);++I_Love)cout<<Hashimoto[I_Love]<<(I_Love==(Kanna)-1?"\n":" ");
#define FOR(I_Love,Hashimoto,Kanna) for(int I_Love=Hashimoto;I_Love<(Kanna);++I_Love)
#define MP(Hashimoto,Kanna) make_pair(Hashimoto,Kanna)
#define REV(Kanna) reverse(Kanna.begin(),Kanna.end());
#define SORT(Kanna) sort(Kanna.begin(),Kanna.end());
#define UNIQUE(Kanna) Kanna.erase(unique(Kanna.begin(),Kanna.end()),Kanna.end());
#define inf (int)1e9
#define linf (ll)1e18
#define mod (inf+7)

int n;
pli a[111111];
int s[111111];
int f[111111];

int I_Love_Hashimoto_Kanna() {
	//完全想清楚了再开始写。
	//写不顺、不知道怎么写、很乱的时候，停下来好好想想。
	//做得慢总比做不出好。
	fastio;
	n=read();
	FOR(i,0,n){
		a[i]={read(),i};
		s[i]=1;
	}
	sort(a,a+n);
	ll sum=0;
	for(int i=n-1;i>0;--i){
		int j=lower_bound(a,a+n,MP(a[i].first-(n-s[i]-s[i]),-1))-a;
		if(i==j||a[j].first!=a[i].first-(n-s[i]-s[i])){
			Tone(-1);
			return 0;
		}
		f[i]=j;
		s[j]+=s[i];
		sum+=s[i];
	}
	if(sum!=a[0].first){
		Tone(-1);
		return 0;
	}
	FOR(i,1,n){
		printf("%d %d\n",a[i].second+1,a[f[i]].second+1);
	}
	return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,ans=0;
	cin>>n;
	long long a[n+1],b[n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i]-i;
	}
	sort(b+1,b+n+1);
	long long mid;
	mid=b[(n+1)/2];
	for(int i=1;i<=n;i++)
		ans+=abs(b[i]-mid);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 6752
/*input
11
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5
*/
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define input(str) freopen(str,"r",stdin);
#define output(str) freopen(str,"w",stdout);
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define INF  3e16+1
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld\n",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define modd 1000000007
#define len(x) x.size()
#define all(v) (v.begin(),v.end())
#define ll int
#define pi 3.1415926535897932384626
#define ld double
#define endl '\n'
const int N =6e5+5;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
int powmod(int base,int exp,int mod)
{
	int res=1LL;
	while(exp>0)
	{
		if(exp&1LL)
			res=(res*base)%mod;
		exp/=2LL;
		base=(base*base)%mod;
	}
	return res%mod;
}
ld dp[3000][3000];
int n;
ld p[3000];
ld recur(int coin,int heads)
{
	if(coin==n&&heads<=(n/2))
		return (ld(0.00));
	else if(coin==n)
		return (ld(1.00));
	else if(dp[coin][heads]!=-1.00)
		return dp[coin][heads];
	else
	{
		ld temp1=1.00;
		ld temp2=1.00;
		temp1=(1-p[coin])*recur(coin+1,heads);
		temp2=(p[coin])*recur(coin+1,heads+1);
		return dp[coin][heads]=temp2+temp1;
	}
}
signed main()
{
	cin>>n;
	rep(i,n)
	{
		cin>>p[i];	
	}
	rep(i,3000)
	{
		rep(j,3000)
		{
			dp[i][j]=-1.00;
		}
	}
	ld ans=recur(0,0);
	cout<<fixed<<setprecision(12);
	cout<<ans<<endl;
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

int k, x;

int main(void) {
  // Here your code !
  scanf("%d %d", &k, &x);

  for (int i = -1000000; i <= 1000000; ++i) {
    if (abs(i - x) <= k - 1) {
      printf("%d ", i);
    }
  }
  printf("\n");
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << (x) << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

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

    if (a + b == c || a + c == b || b + c == a) {
        OUT("Yes");
    } else {
        OUT("No");
    }

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
const int MAX = 1e5 + 10;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
typedef long long ll;
using namespace std;
#define mul(a, b) (((i64)(a) * (b) ) % MOD)
#define sum(a, b) (((a) + (b) ) % MOD)

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

	#define endl '\n'

	#ifdef LOCAL_DEBUG
		freopen("data.in", "r", stdin );
	#endif
	int n; cin >> n;
	vector<string> ar(n);
	for(int i = 0; i <n; i++)
		cin >> ar[i];
	int ans = 0;
	vector<vector<int>> H(n, vector<int>(n));

	for(int ba = -(n - 1); ba <= n - 1; ba++){
		bool ok = true;;
		for(int i = 0; i <n ;i++)


			for(int j = 0;j < n; j++){
				if(ar[i][j] != ar[(j + ba + n) % n][(i - ba + n) % n]){
					ok = false;
					j = i = n;
				}
			}
		if(ok){
			if(ba < 0){
				ans += n + ba;
			}
			else{
				ans += n - ba;
			}
		}

	}
	cout << ans << endl;


}


Measured memory_bytes: 768
#include<stdio.h>
#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

int prim(){
  int i,u,minv,d[MAX],p[MAX],color[MAX],sum = 0;
  for(i = 0 ; i < n ; i++){
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }
  d[0] = 0;
  while(1){
    minv = INFTY;
    u = -1;
    for(i = 0 ; i < n ; i++){
      if(minv > d[i] && color[i] != BLACK){
	u = i;
	minv = d[i];
      }
    }
    if(u == -1)break;
    color[u] = BLACK;
    for(i = 0 ; i < n ; i++){
      if(color[i] != BLACK && M[u][i] != INFTY){
	if(d[i] > M[u][i]){
	  d[i] = M[u][i];
	  p[i] = u;
	  color[i] = GRAY;
	}
      }
    }
  }
  for(i = 0 ; i < n ; i++){
    if(p[i] != -1)sum += M[i][p[i]];
  }
  return sum;
}

int main(){
  int i,j,e;
  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    for(j = 0 ; j < n ; j++){
      scanf("%d",&e);
      M[i][j] = (e == -1) ? INFTY : e;
    }
  }
  printf("%d\n",prim());
  return 0;
}



Measured memory_bytes: 2112
#全体的な方針
#浅いほうから貪欲に頂点を倍化していく
#現在見ている段の頂点数がそれより深い段の葉の数を超えると余ってしまう
#よって、minで押さえつける必要がある(累積和で高速化が必要)


#累積和の定義
def Csum(a):
    b,c=[],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b

#n:二分木の深さ
#a:それぞれの段数の葉の数
#s:aの累積和をとったもの(その深さよりも浅い葉の数)
#su:aの総和(全体の葉の数)
#b:現在の深さの頂点数
#c:現在までの頂点数

n=int(input())
a=list(map(int,input().split()))
s,su,b,c=Csum(a),sum(a),1,0
for i in range(n+1):
    #頂点数カウントに現在の段を加算
    #葉の数だけ親の候補を減らしておく
    c+=b
    b-=a[i]
    #最後まで頂点を使い切ったならcを出力
    #途中で頂点が足りなくなったら-1を出力
    if b<=0:
        if i==n and b==0:
            print(c)
        else:
            print(-1)
        break
    #次の段の頂点数の更新
    #iより深い葉の数(su-s[i])を超えないようにする
    b=min(b*2,su-s[i])

Measured memory_bytes: 20080
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] r = "AAA:AA:A:B:C:D:E".split(":");
        double[] m1 = { 35.5, 37.5, 40, 43,50, 55, 70 };
        double[] m2 = { 71, 77, 83, 89, 105, 116, 148 };
        out:while (sc.hasNext()) {
            double a = sc.nextDouble();
            double b = sc.nextDouble();
            for (int i = 0; i < m1.length; i++) {
                if (a < m1[i] && b < m2[i]) {
                    System.out.println(r[i]);
                    continue out;
                }
            }
            System.out.println("NA");
        }
    }
}



Measured memory_bytes: 28660
#include <iostream>
using namespace std;
     
int main() {
    
    long long n, m, l;
    cin >> n >> m >> l;
    
	long long a[n][m];
	long long b[m][l];
	long long c[n][l] = {};
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
		    cin >> a[i][j];
		}
	}
	
	for(int i = 0; i < m; i++){
		for(int j = 0; j < l; j++){
		    cin >> b[i][j];
		}
	}	
	

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
		    for(int k = 0; k < l; k++){
		    c[i][k] += a[i][j] * b [j][k];
		    }
		}
	}
	
    for(int i = 0; i < n; i++){
		for(int j = 0; j < l; j++){
		    cout << (j == 0 ? "": " ") << c[i][j];
		}
		cout << endl;
	}
	return 0;
}



Measured memory_bytes: 3328
#include<bits/stdc++.h>
    using namespace std;
  #define int long long int
    #define endl "\n"
    #define MOD 1000000007
    #define mod 1000000007
    #define M 1000000007
    
    #define pb push_back
    #define take(a,b,c) for(int b=0;b<c;b++) cin>>a[b]
  //  #define mp make_pair
  #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  #define mx 400005
  #define fiint(a,b) memset(a,b,sizeof(a))  
  #define bitcount __builtin_popcount
  #define fori(i,a,b) for(int i=a;i<b;i++)
  #define ford(i,a,b) for(int i=a;i>=b;i--)
  #define debug(x) cout<<x<<endl;
  #define cases(t) int t; cin>>t; while(t--)
  #define inf1 INT_MAX
  #define all(a) a.begin(),a.end()
  #define vec vector<int>
  #define pii pair<int,int>
  #define plii pair<int,int>
  #define pint pair<int,int>
  #define ff first
  #define ss second
  #define lb lower_bound
  #define ub upper_bound
  #define bs binary_search
  #define sz(x) (int)x.size()
#define PI                    3.14159265359

bool prime[10000001];

void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}



signed  main() 
{ 
	int n,k;cin>>n>>k;
	vec v(n);
	int ma = 0 ;
	fori(i,0,n){cin>>v[i]; ma= max(ma,v[i]); }
	int dp[k + 1];
	dp[0]=0;

	fori(i,0,k+1)
		dp[i]=-1;
	fori(i,0,n)
		dp[v[i]]=1;
	fori(i,0,ma + 1)
		if(dp[i]==-1)
			dp[i]=0;
	fori(i,0,k+1)
	{

		for(int j=0;j<n;j++)
		{
			
			if( i - v[j] >=0  && dp[i- v[j]]==0)
				dp[i] = 1; 

		}
		if(dp[i]!=1)
			dp[i]=0;
	}
	// fori(i,0,k+1)
	// 	cout<<i<<" " <<dp[i]<<endl; 
	if(dp[k]==1)
		cout<<"First"<<endl;
	else 
		cout<<"Second"<<endl;


}




 


Measured memory_bytes: 1024
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
print((N-2)*180)

Measured memory_bytes: 21588
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = [0] * 1000000
for i in range(N):
    s[i+1] = s[i] + A[i]

max_s = 0
for i in range(N):
    if max_s < s[i+K] - s[i]:
        max_s = s[i+K] - s[i]


print((max_s+K) / 2)

Measured memory_bytes: 25952
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <tuple>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[])
{
	int n, i, tmp, j;
	vector<int> x;
	ll tmpdis;
	ll answer = 0;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> tmp;
		x.push_back(tmp);
	}
	sort(x.begin(), x.end());
	
	for (i = x[0]; i <= x[n - 1]; i++) {
		tmpdis = 0;
		for (j = 0; j < n; j++) {
			tmpdis += (i - x[j]) * (i - x[j]);
		}
		if (i == x[0])
			answer = tmpdis;
		else {
			if (tmpdis < answer)
				answer = tmpdis;
		}
	}

	cout << answer << endl;
	
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
mul = 1
flag = 0
if 0 in a:
    flag = 2
    print(0)
else:
    for i in range(n):
        mul = mul * a[i]
        if mul > 10**18:
            print(-1)
            flag = 1
            break
if flag == 0:
    print(mul)

Measured memory_bytes: 21548
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use itertools::Itertools;
use std::process::exit;
use std::cmp::*;
use num::*;
use num::integer::Roots;

fn main() {
    input! {
    a:String,
    }
    let mut a=a.chars().collect_vec();
    let mut b=0;
    for i in 0..4 {
        a.push('0');
        if i==0&&a[i]=='Y'{b+=1}
        if i==1&&a[i]=='A'{b+=1}
        if i==2&&a[i]=='K'{b+=1}
        if i==3&&a[i]=='I'{b+=1}
    }
    println!("{}",if b==4{"Yes"}else{"No"})
}

Measured memory_bytes: 2152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
vector<pair<ll, ll>> node[100002];
ll cost[100002];
ll check[100002];
void dfs(ll k, ll prev){
    if(check[k] == 1){
        return;
    }
    check[k] = 1;
    cost[k] = prev;

    fore(a, node[k]){
        dfs(a.first, cost[k] + a.second);
    }
}

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

    ll a[n], b[n], c[n];
    rep(i, 0, n - 1){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
        node[a[i]].push_back(pair<ll, ll>(b[i], c[i]));
        node[b[i]].push_back(pair<ll, ll>(a[i], c[i]));
    }


    ll q, k;
    cin >> q >> k;
    k--;
    ll x[q], y[q];
    rep(i, 0, q){
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }

    dfs(k, 0);

    rep(i, 0, q){
        cout << cost[x[i]] + cost[y[i]] << endl;
    }
}


Measured memory_bytes: 17408
#include <stdio.h>
int main(void){
	long long takahashi,aoki,k;
	scanf("%lld%lld%lld",&takahashi,&aoki,&k);
	if(takahashi>=k){
		takahashi-=k;
	}else if((takahashi+aoki)>k){
		aoki-=(k-takahashi);
		takahashi=0;
	}else{
		takahashi=0;
		aoki=0;
	}
	printf("%lld %lld",takahashi,aoki);
	return 0;
}

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

using namespace std;

#define ll long long

int main() {
    ll q,h,s,d,n;
    cin>>q>>h>>s>>d>>n;
    ll v1=min(4*q,min(2*h,s));
    ll v2=min(8*q,min(4*h,min(2*s,d)));
    if(v2<2*v1) {
        cout<<((n/2)*v2+(n%2)*v1)<<endl;
    }
    else cout<<n*v1<<endl;
    
    return 0;;
}

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

int main() {
  double W,H,x,y;
  cin >> W >> H >> x >> y;
  cout << fixed << setprecision(6);
  cout << W*H/2 ;
  if (x == W/2 && y == H/2) {
    cout << " " << "1" << endl;
  } else {
    cout << " " << "0" << endl;
  }
}


Measured memory_bytes: 256
from collections import deque

h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<=h-1 and 0<=nj<=w-1 and S[ni][nj]!="#":
                        if dist[ni][nj]>dist[si][sj]+1:
                            dist[ni][nj]=dist[si][sj]+1
                            ans=max(ans,dist[si][sj]+1)
                            que.append((ni,nj))

print(ans)

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

int main() {
  int n,k;
  double ans = -1.0;
  int p[200000];
  double z[200000];
  cin >> n >> k;
  rep(i,n) {
    int q;
    double r;
    cin >> q;
    p[i] = q;

    ll t= ((1+p[i])*p[i])/2; 
    z[i] = (double)t/p[i];

    if (i < k-1) continue;

    double h;
    if (i == k-1) {
      h = 0;
      rep(j,k){
        h += z[i-j];
      }
    } else if (i > k-1) {
      h -= z[i-k];
      h += z[i];
    }
    ans = max(ans,h);

  }
  cout << fixed;
  cout << setprecision(12) << ans;

  return 0;
}

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

int L, R, D;

int main() {
    cin >> L >> R >> D;
    int cnt = 0;
    for (int i=L; i<=R; i++) {
        if (i % D == 0) cnt++;
    }
    cout << cnt << endl;
    return 0; 
}


Measured memory_bytes: 3588
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 2e5 + 10;
int n,k,a[maxn];
bool check(int m){
  int cnt = 0;
  rep(i,1,n) cnt += max(0ll,(int)ceil((double)a[i] / (double)m) - 1);
  return cnt <= k;
}
signed main() {
  IO;
  cin >> n >> k;
  rep(i,1,n) cin >> a[i];
  int l = 1 ,r = INF,ans = 1;
  while (l <= r){
    int mid = (l + r) / 2;
    if(check(mid)) ans = mid,r = mid - 1;
    else l = mid + 1;
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 5296
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <unordered_map>

using namespace std;

typedef long long LL;

LL H, W;

int main() {
    int k;
    cin >> H >> W;
    if (H == 1 || W == 1) cout << 1 << endl;
    else cout << ((H * W + 1) >> 1) << endl;
    return 0;
}

Measured memory_bytes: 256
s = str(input())
q = int(input())
b = 1
x=''
y=''
for i in range(q):
  la = input()
  if la == "1":
    b ^= 1
  else:
    a,f,c=la.split()
    if f == "1":
      if b==1:x=c+x
      else:y=y+c
    else:
      if b==1:y=y+c
      else:x=c+x
s = x+s+y      
print(s if b==1 else s[::-1])

Measured memory_bytes: 4604