akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

int read() {
  int res = 0; char c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)) res = res * 10 + c - '0', c = getchar();
  return res;
}

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7, inv_2 = (mod + 1) / 2;
void Inc(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }
void Dec(int &x, int y) { x -= y, x += x < 0 ? mod : 0; }
int inc(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
int dec(int x, int y) { return x < y ? x - y + mod : x - y; }
int mul(int x, int y) { return 1LL * x * y % mod; }
int fastpow(int base, int x) {
  int res = 1;
  while(x) {
    if(x & 1) res = mul(res, base);
    base = mul(base, base), x >>= 1;
  }
  return res;
}

struct Bit {
#define lb (-x & x)
  int tree[maxn], lim;
  void init(int _l = 0) { memset(tree, 0, sizeof(tree)), lim = _l; }
  void Add(int x, int v) { while(x <= lim) Inc(tree[x], v), x += lb; }
  int Query(int x) { int res = 0; while(x) Inc(res, tree[x]), x -= lb; return res; }
  int _S(int l, int r) { return dec(Query(r), Query(l - 1)); }
#undef lb
} tree[3];

int N, x, S, ans;
int a[maxn], f[maxn], g[maxn], h[maxn];
int t[maxn], L[maxn], R[maxn];

int main() {
  N = read();
  tree[0].init(N);
  tree[1].init(N);
  tree[2].init(N);
  foru(i, 1, N) f[a[i] = read()]++;
  ford(i, N, 1) f[i] += f[i + 1];
  foru(i, 1, N) if((f[i] -= N - i) <= 0) return puts("0"), 0;
  S = g[0] = 1;
  foru(i, 1, N) {
    g[i] = fastpow(f[i], mod - 2), t[i] = t[i - 1];
    if(f[i] == 1) t[i]++;
    else g[i] = mul(g[i], f[i] - 1);
    g[i] = mul(g[i], g[i - 1]);
    h[i] = fastpow(g[i], mod - 2);
    S = mul(S, f[i]);
  }
  t[0] = t[N + 1] = -1;
  foru(i, 1, N) L[i] = (t[i] == t[i - 1] ? L[i - 1] : i);
  ford(i, N, 1) R[i] = (t[i] == t[i + 1] ? R[i + 1] : i);
  foru(i, 1, N) {
    x = a[i];
    Inc(ans, mul(g[x], tree[0]._S(L[x], x)));
    Dec(ans, mul(h[x], tree[1]._S(x + 1, R[x])));
    Inc(ans, tree[2]._S(x + 1, N));
    tree[0].Add(x, h[x]);
    tree[1].Add(x, g[x]);
    tree[2].Add(x, 2);
  }
  ans = mul(ans, S);
  ans = mul(ans, inv_2);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 8064
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
		int d = sc.nextInt();
		int t = sc.nextInt();
		int s = sc.nextInt();
 
		if (d <= t*s){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		
	}
}

Measured memory_bytes: 35640
#include <stdio.h>

long long int Lucas(int i)
{
    int o;
    long long int l[87];
    
    l[0] = 2;
    l[1] = 1;
    for(o = 2; o <= i; o++)
    {
        l[o] = l[o - 1] + l[o - 2];
    }
    
    return l[i];
}

int main()
{
    int N;
    
    scanf("%d", &N);
    printf("%lld\n", Lucas(N));
    
    return 0;
}

Measured memory_bytes: 128
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    P={i:[] for i in range(N)}
    Cities={i:[] for i in range(M)}
    for i in range(M):
        p,y=list(map(int, input().split()))
        P[p-1].append((i,y))
    for i,p in P.items():
        p.sort(key=lambda x:x[1])
        for id in range(len(p)):
            number=p[id][0]
            temp='{}'.format(i+1).zfill(6)
            temp+='{}'.format(id+1).zfill(6)
            Cities[number]=temp

    for i in range(M):
        print(Cities[i])

Measured memory_bytes: 89828
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}
int main() {
    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> X(N);
    REP(i, N) { cin >> X[i]; }

    ll cnt = 0;
    REP(i, N - 1) {
        ll diff = X[i + 1] - X[i];
        if(diff * A > B) {
            cnt += B;
        } else {
            cnt += diff * A;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0); cin.sync_with_stdio(false);
  long long n, K, L;
  cin >> n >> K >> L;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long N = n * (n + 1) / 2;
  auto ck = [&] (int m) -> bool {
    int crr = 0;
    long long ret = 0;
    for (int l = 0, r = 0; l < n; l++) {
      if (r <= l) {
        r = l;
        crr = 0;
      }
      for (; r < n; r++) {
        if (crr == K - 1 && a[r] <= m) break;
        if (a[r] <= m) crr++;
      }
      ret += r - l;
      if (a[l] <= m) crr--;
    }
    return N - ret >= L;
  };
  constexpr int inf = 1LL << 30;
  int ng = 0, ok = inf, md;
  while (ok - ng > 1) {
    md = (ng + ok) >> 1;
    if (ck(md)) ok = md;
    else ng = md;
  }
  cout << ok << endl;
  return 0;
}


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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

vector<vector<lli>> G;

lli dp[100100];
bool vis[100100];

lli func(lli now){
	if(vis[now])return dp[now];

	vis[now]=true;
	lli rtn=0;
	for(auto e:G[now]){
		chmax(rtn,func(e)+1);
	}
	return dp[now]=rtn;
}

int main(){

	lli n,m;
	cin>>n>>m;
	G.resize(n);

	REP(i,0,m){
		lli a,b;
		cin>>a>>b;
		a--,b--;
		G[a].push_back(b);
	}

	lli ans = 0;
	REP(i,0,n)chmax(ans,func(i));

	cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 8704
n = int(input())
a = [int(x) for x in input().split()]
avarage = sum(a) / len(a) 
index = float("inf")
value = float("inf")

for i in range(len(a)):
    if abs(a[i] - avarage) <= value and value != abs(a[i] - avarage):
        value = abs(a[i] - avarage)
        index = i
print(index)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
const int len=1000050;
 
inline int prev(int pos) {
    return (pos == 0) ? len - 1 : pos - 1;
}
 
inline int next(int pos) {
    return (pos == len - 1) ? 0 : pos + 1;
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
	int n;
	cin >> n;
	vector<int> list(len);
	int first=0, last=0;
	
	string op;
	int key;
	for(int i=0; i<n; i++){
		cin >> op;
		if(op == "insert"){
			cin >> key;
			first = prev(first);
			list[first] = key;
		} else if (op == "deleteFirst"){
			while(list[first] == -1){
				first = next(first);
			}
			first = next(first);
		} else if(op == "deleteLast"){
			while(list[prev(last)] == -1){
				last = prev(last);
			}
			last = prev(last);
		} else{
			cin >> key;
			for(int j=first; j != last; j=next(j)){
				if(list[j] == key){
					list[j] = -1;
					break;
				}
			}
		}
	}
	
	bool nospace = true;
    for (int i=first; i!=last; i=next(i)) {
        if (list[i] == -1) continue;
        if (nospace) {
            cout << list[i];
            nospace = false;
        } else {
            cout << " " << list[i];
        }
    }
    cout << endl;
}

Measured memory_bytes: 4900
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

int first_prime_factor(int n)
{
    int to = sqrt(n);

    if (n <= 1) return -1;

    for (int i = 2; i <= to; ++i) {
        if (n % i == 0) return i;
    }

    return n;
}

signed main()
{
    int n; cin >> n;
    cout << n << ": ";
    int cnt = 0;
    while (n != 1) {
        if (cnt) cout << ' ';
        int a = first_prime_factor(n);
        cout << a;
        n /= a;
        cnt += 1;
    }
    cout << endl;
}

Measured memory_bytes: 1168
#include <iostream>
#include <algorithm>
using namespace std;
int main (){ 
          int d;
          int a[30]={};
          for(int i=1;i<=30;i++){
                   cin>>d;
                   a[d]=d;
           }
           for(int j=1;j<=30;j++){
                   if(a[j]!=j){
                         cout<<j<<endl;
                    }
             }
            return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,s,s1,s2;
    cin>>n;
    s=n/500;
    s=s*1000;
    s1=n%500;
    s2=s1/5;
    s2=s2*5;
    cout<<s+s2<<endl;
}


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

int main(){
   string s;
   int k;
   cin>>k>>s;
   if(s.length()<=k)
   {
       cout<<s<<endl;
   }
   else
   {
       cout<<s.substr(0,k)<<"..."<<endl;
   }
   
    
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)

using namespace std;
using ll = long long;
typedef pair<int, int> Pair;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<pair<ll, ll>> f(ll n) {
  vector<pair<ll, ll>> res;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i != 0) continue;
    ll cnt = 0;
    while (n % i == 0) cnt++, n /= i;
    res.emplace_back(i, cnt);
  }
  if (n > 1) res.emplace_back(n, 1);
  return res;
}

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

  ll g = gcd(a, b);
  auto s = f(g);

  cout << s.size() + 1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int a[5];
	for(int i=0;i<5;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<5;i++)
	{
		if(a[i]==0)
		{
			cout<<i+1<<endl;
			break;
		}
	}
}

Measured memory_bytes: 3604
import java.io.*;
import java.util.*;

public class Main {
    FastScanner in;
    PrintWriter out;

    void solve() {
        int h = in.nextInt();
        int w = in.nextInt();
        char[][] s = new char[h][];
        for (int i = 0; i < h; i++) {
            s[i] = in.next().toCharArray();
        }
        int[][] dp = new int[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        }
        dp[0][0] = (s[0][0] == '.' ? 0 : 1);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i + 1 < h) {
                    int cost = s[i][j] == s[i + 1][j] ? 0 : 1;
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + cost);
                }
                if (j + 1 < w) {
                    int cost = s[i][j] == s[i][j + 1] ? 0 : 1;
                    dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + cost);
                }
            }
        }
        out.println((dp[h - 1][w - 1] + 1) / 2);
    }

    void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}

Measured memory_bytes: 21460
#include <stdio.h>
#include <string.h>
 
#define N 25
 
typedef struct{
  int par, left, right, status, depth, sibling, degree, height;
}Node;
 
Node tree[N];
int n;
char root[N];
 
void calc_depth(int p, int d){
  tree[p].depth = d;
  if(tree[p].right != -1) calc_depth(tree[p].right, d + 1);
  if(tree[p].left != -1) calc_depth(tree[p].left, d + 1);
}
 
int calc_height(int p){
  int a = 0, b = 0;
  if(tree[p].left != -1) a = calc_height(tree[p].left) + 1;
  if(tree[p].right != -1) b = calc_height(tree[p].right) + 1;
  if(a < b) tree[p].height = b;
  else tree[p].height = a;
  return tree[p].height;
}
 
main(){
  int i, r;
  scanf("%d", &n);
  memset(root, 1, n);
  for(i=0;i<n;i++) tree[i].left = tree[i].right = tree[i].sibling = -1;
  for(i=0;i<n;i++){
    int idx, l, r;
    scanf("%d %d %d", &idx, &l, &r);
    if(l != -1){
      tree[idx].left = l;
      tree[l].par = idx;
    }
    if(r != -1){
      tree[idx].right = r;
      tree[r].par = idx;
    }
    if(l == -1 && r == -1){
      tree[idx].status = 1;
      tree[idx].degree = 0;
    }else if(l == -1 || r == -1){
      tree[idx].status = 2;
      tree[idx].degree = 1;
    }else{
      tree[idx].status = 2;
      tree[idx].degree = 2;
      tree[l].sibling = r;
      tree[r].sibling = l;
    }
    root[l] = root[r] = 0;
  }
  for(i=0;i<n;i++) if(root[i]) r = i;
  tree[r].par = -1;
  tree[r].status = 0;
  calc_depth(r, 0);
  calc_height(r);
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ", i, tree[i].par, tree[i].sibling, tree[i].degree, tree[i].depth, tree[i].height);
    if(tree[i].status == 0) printf("root\n");
    else if(tree[i].status == 1) printf("leaf\n");
    else if(tree[i].status == 2) printf("internal node\n");
  }
  return 0;
}

Measured memory_bytes: 620
n, k = map(int, input().split(' '))
w = [int(input()) for i in range(n)]

max_w = 100000 * 10000
P = 0
left = 0
right = max_w

def check(p):
    sum = 0
    count = 1
    for i in range(n):
        if(sum + w[i] > p):
            count += 1
            sum = w[i]
            if(count > k or w[i] > p):
                return False
        else:
            sum += w[i]

    return True

while(right - left > 1):
    mid = (left + right) // 2
    if(check(mid)):
        right = mid
        P = mid
    else:
        left = mid

print(P)


Measured memory_bytes: 9560
#include <iostream>
#include <cstdio>
#include <complex>
#define _USE_MATH_DEFFINES
#include <cmath>
using namespace std;
typedef complex<double> P;

double convert(double angle) {
    return((M_PI * (angle / 180.0)));
}

P now(0, 0);
double angle = 0;

int main(void) {
    int fd, spin;
    
    while(scanf("%d,%d", &fd, &spin), fd + spin != 0) {
        double nextx = now.real() + fd * sin(convert(angle)),
        nexty = now.imag() + fd * cos(convert(angle));
        now = P(nextx, nexty);
        angle += spin;
    }
    cout << (int)now.real() << endl << (int)now.imag() << endl;
    return(0);
}

Measured memory_bytes: 1212
import bisect
import sys
input = sys.stdin.readline

a, b, q = map(int, input().split())

s = [-10**11]
t = [-10**11]
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(10**11)
t.append(10**11)

for i in range(q):
    x = int(input())
    zin = bisect.bisect_left(s, x)
    tera = bisect.bisect_left(t, x)
    ans = 10**11
    ans = min(ans, max(x-s[zin-1], x-t[tera-1]))
    ans = min(ans, min(s[zin]-x, x-t[tera-1])*2 + max(s[zin]-x, x-t[tera-1]))
    ans = min(ans, min(t[tera]-x, x-s[zin-1])*2 + max(t[tera]-x, x-s[zin-1]))
    ans = min(ans, max(s[zin]-x, t[tera]-x))
    print(ans)


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

int main() {
   int n,w;
   cin>>n>>w;
   vector<int>wt(n);
   vector<int>val(n);
   int totalValue=0;
   for(int i=0;i<n;i++) {
	   cin>>wt[i]>>val[i];
	   totalValue+=val[i];
   }
   int dp[n+1][totalValue+1];
   for(int i=1;i<=totalValue;i++) dp[0][i]=1e9+9;
//    for(int i=1;i<=n;i++) dp[i][0]=INT_MAX;
   dp[0][0]=0;
   int ans=0;
   for(int i=1;i<=n;i++){
	   for(int j=0;j<=totalValue;j++){	
		   if(j>=val[i-1]){
			   dp[i][j]=min(dp[i-1][j],dp[i-1][j-val[i-1]]+wt[i-1]);
		   }else{
			   dp[i][j]=dp[i-1][j];
		   }
         if(dp[i][j]<=w){
			 ans=max(ans,j);
		 }
	   }
   }
  cout<<ans;
}


Measured memory_bytes: 42956
def solve(a_list):
    if len(list(filter(lambda x: x >= 0, a_list))) == 0:
        return max(a_list)

    dp = [0] * len(a_list)
    dp[0] = a_list[0]
    for i in range(1, len(dp)):
        dp[i] = max(a_list[i], a_list[i] + dp[i - 1])
    return max(dp)


def main():
    while True:
        n = int(input())
        if n == 0:
            break
        a_list = [int(input()) for _ in range(n)]
        print(solve(a_list))


if __name__ == '__main__':
    main()

Measured memory_bytes: 7804
N,M=map(int,input().split())
from operator import mul
from functools import reduce
if M==1:
  print(1)
else:
  def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

  def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

  a=factorization(M)
  A=[]
  for i in range(len(a)):
    A.append(a[i][1])
  ans=1
  for i in A:
    d=cmb(i+N-1,i)
    ans*=d%(10**9+7)
  print(ans%(10**9+7))


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

using namespace std;

int dist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

pair<int, int> rotate(pair<int, int> a) {
	return make_pair(-a.second, a.first);
}

int main() {
	int n;
	while (cin >> n, n) {
		vector<vector<pair<int, int> > > p(n + 1);
		for (int i = 0; i <= n; ++i) {
			int m; cin >> m;
			for (int j = 0; j < m; ++j) {
				int x, y; cin >> x >> y;
				p[i].push_back(make_pair(x, y));
			}
		}
		for (int i = 1; i <= n; ++i) {
			if (p[0].size() != p[i].size()) continue;
			
			for (int j = 0; j < 4; ++j) {
				for (int k = 0; k < p[i].size(); ++k) p[i][k] = rotate(p[i][k]);
				bool flag = true;
				for (int k = 0; k < p[i].size(); ++k) {
					if (p[0][k].first - p[0][0].first != p[i][k].first - p[i][0].first) flag = false;
					if (p[0][k].second - p[0][0].second != p[i][k].second - p[i][0].second) flag = false;
				}
				if (flag) {
					cout << i << endl;
					break;
				}
				flag = true;
				for (int k = p[i].size() - 1; k >= 0; --k) {
					if (p[0][p[i].size() - k - 1].first - p[0][0].first != p[i][k].first - p[i][p[i].size() - 1].first) flag = false;
					if (p[0][p[i].size() - k - 1].second - p[0][0].second != p[i][k].second - p[i][p[i].size() - 1].second) flag = false;
				}
				if (flag) {
					cout << i << endl;
					break;
				}
			}
		}
		cout << "+++++" << endl;
	}

	return 0;
}


Measured memory_bytes: 3084
#include<cstdio>
#include<iostream>
#include<cstring>
#include<utility>
#include <vector>
using namespace std;
typedef pair<int,int>P;
const int MAXN=5e2+9;
int query[MAXN][MAXN];
int sum[MAXN][MAXN];
signed main()
{
    int N,M,Q;
    scanf("%d%d%d",&N,&M,&Q);
    for(int i=0;i<M;++i)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        query[l][r]++;
    }
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=N;++j)
        {
            sum[i][j]=sum[i][j-1]+query[i][j]+sum[i-1][j]-sum[i-1][j-1];
        }
    }
    for(int i=0;i<Q;++i)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",sum[r][r]+sum[l-1][l-1]-sum[l-1][r]-sum[r][l-1]);
    }
    return 0;
}


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

ll solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for ( int i = 0; i < N; i++ ) cin >> A[i];
    ll ans = 0;
    ll mx = A[0];
    for ( int i = 1; i < N; i++ ) {
        if ( A[i] < mx ) ans += mx - A[i];
        mx = max(mx, A[i]);
    }
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 4784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int n , m;
struct reg
{
	int l , r , x;
}R[310][310];
int cnt[310];
ll dp[310][310][310];
bool check(int i , int j , int k)
{
	int pos = max(max(i , j) , k);
	for (int p = 1; p <= cnt[pos]; p++)
	{
		reg tmp = R[pos][p];
		int l = tmp.l , r = tmp.r , x = tmp.x;
		int res = 0;
		if (i >= l)
		{
			res++;
		}
		if (j >= l)
		{
			res++;
		}
		if (k >= l)
		{
			res++;
		}
		if (res != x)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	scanf("%d%d" , &n , &m);
	for (int i = 1; i <= m; i++)
	{
		int l , r , x;
		scanf("%d%d%d" , &l , &r , &x);
		R[r][++cnt[r]] = {l , r , x};
	}
	dp[0][0][0] = 1;
	ll ans = 0;
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			for (int k = 0; k <= n; k++)
			{
				if (dp[i][j][k] == 0)
				{
					continue;
				}
				int pos = max(max(i , j) , k) + 1;
				if (!check(i , j , k))
				{
					dp[i][j][k] = 0;
					continue;
				}
				if (pos == n + 1)
				{
					ans += dp[i][j][k];
					ans %= mod;
				}
				dp[pos][j][k] += dp[i][j][k];
				dp[pos][j][k] %= mod;
				dp[i][pos][k] += dp[i][j][k];
				dp[i][pos][k] %= mod;
				dp[i][j][pos] += dp[i][j][k];
				dp[i][j][pos] %= mod;
			}
		}
	}
	printf("%lld\n" , ans);
}

Measured memory_bytes: 230016
"""
author : halo2halo
date : 23, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

S = list(readline().decode('utf8').rstrip())
bl = S[0] == 'A'
bl &= ('C' in S[2:-1])

if bl:
    S.remove('A')
    S.remove('C')

bl &= all('a' <= x <= 'z' for x in S)

print('AC' if bl else 'WA')


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    acc=[0]*(N+1)
    cur=0
    if K==1:
        print(0)
        return 

    for i,a in enumerate(A):
        cur+=a
        cur%=K
        acc[i+1]=(cur-i-1)%K

    j=1
    d=Counter()
    d[0]=1
    ans=0
    for i in range(N):
        d[acc[i]]-=1
        while j-i<K and j<N+1:
            d[acc[j]]+=1
            j+=1
        ans+=d[acc[i]]

    print(ans)
        
        



if __name__ == "__main__":
    main()

Measured memory_bytes: 142560
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
static ull tenq = 1000000000;
static ull mod = tenq + 7;

using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<ll> as(N);
  for (auto i = 0; i < N; i++) cin >> as[i];
  sort(as.begin(), as.end(), greater<ll>());
  ll w = 0;
  ll h = 0;
  for (auto i = 1; i < N; i++) {
    if (as[i] == as[i-1]) {
      if (w == 0) w = as[i];
      else if (h == 0) h = as[i];
      i++;
    }
  }

  cout << (w * h) << endl;

  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a[100010],ans[100010],sum=0,sum2=0;
    cin>>n;
    rep2(i,1,n+1){
        cin>>a[i];
        sum+=a[i];
        if(i%2==0) sum2+=a[i]*2;
    }
    ans[1]=sum-sum2;
    for(int i=2;i<n+1;i++){
        ans[i]=a[i-1]*2-ans[i-1];
    }
    rep2(i,1,n+1){
        if(i!=n){
            cout<<ans[i]<<" ";
        } else{
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
typedef pair<ll, ll> pl;
typedef pair<pl, ii> pli;
const int MAX = 2e2+2;
char s[MAX];
int N, L;

int main(int argc, char * * argv) {
	scanf("%d%d", &N, &L);
	vector<string> a;
	rep(i, 0, N) {
		scanf(" %s", s);
		a.pb(s);
	}
	sort(all(a));
	for(auto x : a)
	    printf(x.c_str());
	printf("\n");
	return 0;
}


Measured memory_bytes: 3772
using System;

namespace ConsoleApp1 {
    class Program {
        static void Main(string[] args) {
            string input = Console.ReadLine();

            int a = int.Parse(input.Split(' ')[0]);
            int b = int.Parse(input.Split(' ')[1]);

            Console.WriteLine(( a + b ) % 24);
        }
    }
}


Measured memory_bytes: 11092
n = input()
h = list(map(int,input().split()))
def ki(h):
    if h[0] > 1:
        h[0] = h[0] -1
    a=1
    for i in h[1:]:  
        if i < h[a-1] :  
            return("No")
        elif i != h[a-1]:  
            h[a] = h[a] - 1 
        a += 1
    return("Yes")
print(ki(h))

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

int main(){
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i = 0; i < N; i++)
        cin >> d[i];
    
    sort(d.begin(), d.end());
    cout << d[N/2] - d[N/2-1] << endl;

    return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main{
    void solve(){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = scan.nextInt() - 1;
        int out = 0;
        for(int i = 0; out < n; i = a[i]){
            if(i == 1){
                System.out.println(out);
                return;
            }
            out++;
        }
        System.out.println(-1);
        scan.close();
    }

    public static void main(String[] args){
        new Main().solve();
    }
}


Measured memory_bytes: 59176
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    a = kwargs["a"]
    res = a + a ** 2 + a ** 3
    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["a"] = [int(i) for i in cin][0]

    cout = main(kwargs)
    print(cout)

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

int main() {
 string a,b; cin >> a >> b;
 int n=a.size();
 int m=b.size();
 vector<char> ans(n+m);
  for(int i=0;i<n+m;i++){
   if(i%2==0)ans[i]=a[i/2];
   else ans[i]=b[(i-1)/2];
  }
  
  for(int i=0;i<n+m;i++){
  cout << ans[i];
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;


int main() {
    int N, A, B, P1 = 0, P2 = 0, P3 = 0;
    cin >> N >> A >> B;
    for (int i = 0; i < N; i++){
        int a;
        cin >> a;
        if (a >= B + 1){
            P3++;
        }
        else if(a >= A + 1){
            P2++;
        }
        else {
            P1++;
        }
    }
    cout << min({P1, P2, P3}) << endl;

}



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

int main() {
    long long int a,b,m,n,k,ans,ans_2;
    scanf("%lld %lld",&n,&k);
    ans=n%k;
    ans_2=k-ans;
    if (ans > ans_2) {
        printf("%lld\n",ans_2);
    }else{
        printf("%lld\n",ans);
    }
    return 0;
}


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

using namespace std;

typedef pair<int, int> P;
typedef long long int LL;

int main() {
    int n;
    cin >> n;
    vector<bool> p(n, false);
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        tmp--;
        if (tmp == i) {
            p[i] = true;
        }
    }

    int cnt = 0;
    if (p[0]) {
        cnt++;
    }
    for (int i = 1; i < n; i++) {
        if (p[i - 1] && p[i]) {
            p[i] = false;
        } else if (p[i]) {
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
void main() {
    string s = readln.chomp;
    string t = readln.chomp;
    bool ok;
    foreach (i; 0 .. s.length) {
        if (s == t) ok = true;
        s = s[$-1] ~ s[0..$-1];
    }
    writeln(ok ? "Yes" : "No");
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.container;
import std.typecons;

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();

        long ans = 0;

        if (H == 1 || W == 1) {
            ans = 1;
        } else {
            long oddH = (W + 1) / 2;
            long evenH = W / 2;
            ans += oddH * ((H + 1) / 2);
            ans += evenH * (H / 2);
        }

        System.out.println(ans);

    }

}


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

using lint = long long;

struct UnionFind {
    vector<int> par, lb, ub;
    UnionFind(int N): par(N), lb(N), ub(N) {
        for (int i = 0; i < N; i++) {
            par[i] = i;
            lb[i] = i;
            ub[i] = i;
        }
    }

    int root(int i) {
        if (par[i] == i) {
            return i;
        } else {
            par[i] = root(par[i]);
            return par[i];
        }
    }
    void unite(int i, int j) {
        if (root(i) != root(j)) {
            lb[root(i)] = min(lb[root(i)], lb[root(j)]);
            ub[root(i)] = max(ub[root(i)], ub[root(j)]);
            par[j] = root(par[i]);
        }
        return;
    }
    bool same(int i, int j) {
        return root(i) == root(j);
    }
    int lower(int i) {
        return lb[root(i)];
    }
    int upper(int i) {
        return ub[root(i)];
    }
};

int main() {
    int N;
    cin >> N;
    vector<lint> a(N + 1), place(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        place[a[i]] = i;
    }

    UnionFind uf(N + 1);
    lint ans = 0;
    for (int i = N; i >= 1; i--) {
        int pos = place[i];
        if (pos > 1 and a[pos - 1] > a[pos]) {
            uf.unite(pos - 1, pos);
        }
        if (pos < N and a[pos] < a[pos + 1]) {
            uf.unite(pos, pos + 1);
        }

        ans += i*lint(pos - uf.lower(pos) + 1)*lint(uf.upper(pos) - pos + 1);
    }

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

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

using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> T(N);
    for(int i = 0; i < N; ++i) {
        cin >> T[i];
    }

    vector<int> v;
    for(int i = 0; i + 1 < N; ++i) {
        v.push_back(T[i + 1] - T[i] - 1);
    }

    int ans = 0;
    sort(rbegin(v), rend(v));
    for(int i = 0; i < K - 1; ++i) {
        ans += v[i];
    }
    ans = T.back() - T[0] + 1 - ans;
    cout << ans << endl;
}



Measured memory_bytes: 3924
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
struct MONSTER {
	int X;
	long long H;
};
 
bool sortX (const MONSTER& a, const MONSTER& b) {
	return a.X < b.X;
}
 
 
int main(void) {
	int N, D, A;
	cin >> N >> D >> A;
	vector <MONSTER> M(N);
	for (int i = 0; i < N; i++) {
		cin >> M[i].X >> M[i].H;
	}
	sort(M.begin(), M.end(), sortX);
 
	long long ans = 0;
	long long pre_damage = 0;
	queue <MONSTER> damage;
	for (unsigned int i = 0; i < M.size(); i++) {
		while ((damage.size() > 0) && (damage.front().X < M[i].X)) {
			pre_damage -= damage.front().H;
			damage.pop();
		}
		M[i].H -= pre_damage;

		if (M[i].H > 0) {
			int att_cnt = (M[i].H + A - 1) / A;
			ans += att_cnt;
			MONSTER temp;
			temp.H = (long long)att_cnt * A;
			temp.X = M[i].X+D+D;
			damage.push(temp);
			pre_damage += (long long)att_cnt * A;
		}
	}
	cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4992
A = gets.chomp.chars.map(&:to_i)
OP = %w(+ -).repeated_permutation(3).to_a

OP.each do |op|
  exp = A.zip(op).flatten.compact.join
  ans = eval(exp)
  if ans == 7
    puts exp + "=7"
    exit
  end
end

Measured memory_bytes: 1788
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int []A = new int[n];
        for(int i=0;i<n;++i){
            A[i] = sc.nextInt();
        }
        for(int i=0;i<n;++i){
            int tmp = A[i];
            int j = i - 1;
            while(j>=0&&A[j]>tmp){
                A[j+1] = A[j];
                --j;
            }
            A[j+1] = tmp;
            for(j=0;j<n;++j){
                if(j!=0)System.out.print(" ");
                System.out.print(A[j]);
            }
            System.out.println("");
        }
    }
}



Measured memory_bytes: 33488
import java.util.Scanner;
 
class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    //赤
    int red = sc.nextInt();
    //緑
    int green = sc.nextInt();
    //青
    int blue = sc.nextInt();
    //操作回数
    int k = sc.nextInt();
    for(int i = 0; i < k;i++){
      if(blue <= red){
        blue = blue * 2;
      }else{
        if(green <= red){
          green = green * 2;
        }else{
          if(blue <= green){
            blue = blue * 2;
          }
        }
      }
      if(blue > green && green > red){
        break;
      }
    }
    
    if(blue > green && green > red){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
    
  }
}


Measured memory_bytes: 35596
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (true) {
            int height = input.nextInt();
            int width = input.nextInt();
            if(width == 0 || height == 0) break;
            for(int i = 0; i < height;i++){
                for(int j = 0; j < width; j++){
                    if(i % 2 == 0){
                        if(j % 2 == 0){
                            System.out.print("#");
                        } else {
                            System.out.print(".");
                        }
                    } else {
                        if(j % 2 == 1){
                            System.out.print("#");
                        } else {
                            System.out.print(".");
                        }
                    }
                }
                System.out.println("");
            }
System.out.println("");
        }
    }
}


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

int main() {
int a,b,c;
a=0;
b=0;
c=0;
string s;
cin>>s;
string ans="YES";
int lo=s.size();
for(int i=0;i<lo;i++){
if(s[i]=='a')a++;
else if(s[i]=='b')b++;
else c++;
}
if(max({a,b,c})-min({a,b,c})>1)ans="NO";
cout<<ans<<endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  
  string a, str;
  
  for(int i = 0; i < H; i++) {
    cin >> str;
    a += str;
  }
  
  for(int i = 0; i < W+2; i++) {
    cout << "#";
  }
  cout << endl;
  for(int i = 0; i < H; i++) {
    cout << "#";
    for(int j = 0; j < W; j++) {
      cout << a.at(j + i*W);
    }
    cout << "#" << endl;
  }
  for(int i = 0; i < W+2; i++) {
    cout << "#";
  }
  cout << endl;
}


Measured memory_bytes: 3560
# a + b = b + c = c + a = 0 mod k
# a + b * 2 + c = 0 mod k
# a * 2 + b + c = 0 mod k
# a + b + c * 2 = 0 mod k
# ➡　a, b, c全部 0 (mod k) or kが偶数なら全部k / 2 (mod k)でもよい

n, k = map(int, input().split())
cnt0 = 0
cnt1 = 0
for i in range(1, n + 1):
    if i % k == 0:
        cnt0 += 1
    if i % k == k // 2:
        cnt1 += 1
if k % 2 == 1:
    print(cnt0 ** 3)
else:
    print(cnt0 ** 3 + cnt1 ** 3)


Measured memory_bytes: 9072
#include <limits.h>
#include <stdio.h>
#include <string.h>

int n, l, i, j;
char s[15][15];

int main(void){
	scanf("%d", &n);
	for(i=0; i<n; i++){
		int a, x, y;
		scanf("%d", &a);
		for(j=0; j<a; j++){
			scanf("%d%d", &x, &y);
			if(y==1){
				s[i][x-1]=1;
			}else{
				s[i][x-1]=2;
			}
		}
	}
	int max=0, now, f;
	for(l=0; l<(1<<n); l++){
		now=0; f=1;
		for(i=0; i<n; i++){
			if((l&(1<<i))!=0){
				now++;
				for(j=0; j<n; j++){
					if(s[i][j]==1 && (l&(1<<j))==0){f=0; break;}
					if(s[i][j]==2 && (l&(1<<j))!=0){f=0; break;}
				}
			}
		}
		if(f && now>max) max=now;
	}
	printf("%d\n", max);
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
typedef pair<int, bool> sP;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef vector<vector<ll>> mat;
typedef vector<ll> vec;

ll mod_pow(ll x, ll n) {
	ll ret = 1;
	while (n > 0) {
		if (n % 2)ret = ret * x%mod;
		x = x * x%mod; n >>= 1;
	}
	return ret;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	while (b) {
		ll r = a % b; a = b; b = r;
	}
	return a;
}

void solve() {
	ll h, w, t; cin >> h >> w >> t;
	ll gh = gcd(t, h);
	ll gw = gcd(t, w);

	ll nh = h / gh;
	ll nw = w / gw;
	ll ans = 0;
	ans += mod_pow(2, nw) + mod_pow(2, nh) -1;
	//cout << nh << " " << nw << endl;
	ll gg = gcd(nh, nw);
	ans += mod_pow(2, gg) - 2;
	ans %= mod;
	ans = mod_pow(ans, gh*gw);
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(9);
	//init();
	solve();
	//stop
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)
#define all(c) c.begin(),c.end()
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define MAX_V 1001
#define MAX_E 401
#define INF INT_MAX
#define MOD 1000000007
#define EPS 1e-7
typedef long long ll;
inline int toInt(std::string s) { int v; std::istringstream sin(s); sin >> v; return v; }
template<class T> inline std::string toString(T x) { std::ostringstream sout; sout << x; return sout.str(); }
using namespace std;

typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
#define X real()
#define Y imag()
typedef pair<int, int> pii;

int main()
{
	ll h, w, d;
	cin >> h >> w >> d;
	map<ll, pair<ll,ll>> mp;
	ll a;
	vector<ll> dp(h*w);
	rep(i, h*w)
	{
		dp[i] = 0;
	}
	rep(i, h)
	{
		rep(j, w)
		{
			cin >> a;
			mp[a - 1].first = i;
			mp[a - 1].second = j;
		}
	}

	rep(i, h*w)
	{
		if (i - d < 0)
		{
			dp[i] = 0;
		}
		else
		{
			dp[i] = dp[i - d] + abs(mp[i].first - mp[i - d].first) + abs(mp[i].second - mp[i - d].second);
		}
	}

	ll q;
	cin >> q;
	rep(i, q)
	{
		ll L, R;
		cin >> L >> R;
		cout << dp[R - 1] - dp[L - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 7424
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include<iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

int S[30009];
int dp1[30009][10]; // dp[i][j] : 0～i番目までにjという数字が何個あったか
int dp2[30009][10][10]; // dp[i][j][k] : 0～i番目までにjkという並びが何個あったか
bool dp3[10][10][10]; // dp[i][j][k] : ijkという並びがあるか


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

	int N; cin >> N;
	string T; cin >> T;
	for (int i = 0; i < N; i++) S[i] = T[i] - '0';
	dp1[0][S[0]] = 1;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= 9; j++) {
			dp1[i][j] = dp1[i - 1][j];
			if (S[i] == j) dp1[i][j]++;
		}
	}
	//for (int i = 0; i < N; i++) cout << dp[i][2] << " ";

	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k <= 9; k++) {
				dp2[i][j][k] = dp2[i - 1][j][k];
				if (S[i] == k) dp2[i][j][k] += dp1[i - 1][j];
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k <= 9; k++) {
				for (int t = 2; t < N && !dp3[i][j][k]; t++) {
					if (S[t] == k && dp2[t - 1][i][j] > 0) {
						dp3[i][j][k] = true;
						ans++;
					}
				}
			}
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 13312