akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
class disjoint_set {
  public:
    vector<int> rank, p, cnt;
    vector<long long> wt;
    disjoint_set (int size) {
      rank.resize(size, 0);
      p.resize(size, 0);
      for (int i = 0; i < size; i++) {
        p[i] = i;
        rank[i] = 0;
      }
      wt.resize(size, 0);
      cnt.resize(size, 0);
    }
    void initWt (int x, int w) {
      wt[x] = w;
    }
    long long getWt (int x) {
      return wt[find(x)];
    }
    void addCnt (int x) {
      cnt[find(x)]++;
    }
    void clrCnt (int x) {
      cnt[find(x)] = 0;
    }
    int getCnt (int x) {
      return cnt[find(x)];
    }
    bool is_equiv (int x, int y) {
      return find(x) == find(y);
    }
    void unite (int x, int y) {
      x = find(x);
      y = find(y);
      if (x == y) {
        return;
      }
      if (rank[x] > rank[y]) {
        p[y] = x;
        wt[x] += wt[y];
        cnt[x] += cnt[y];
      } else {
        p[x] = y;
        wt[y] += wt[x];
        cnt[y] += cnt[x];
        if (rank[x] == rank[y]) {
          rank[y]++;
        }
      }
    }
    int find (int x) {
      if (x != p[x]) {
        p[x] = find(p[x]);
      }
      return p[x];
    }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  disjoint_set djs(n);
  for (int i = 0; i < n; i++) {
    int w;
    cin >> w;
    djs.initWt(i, w);
  }
  vector<pair<int, pair<int, int>>> edg(m);
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    edg[i] = {w, {a, b}};
  }
  sort(edg.begin(), edg.end());
  int usd = 0;
  for (auto e : edg) {
    int w = e.first;
    int a = e.second.first;
    int b = e.second.second;
    int r = djs.find(a);
    djs.unite(r, b);
    djs.addCnt(r);
    if (w <= djs.getWt(r)) {
      usd += djs.getCnt(r);
      djs.clrCnt(r);
    }
  }
  int ans = m - usd;
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3456
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int modu = 1e9 + 7;

int main() {
	int N;
	cin >> N;
	long long ten=1, nine=1, eight=1;
	for (int i = 0; i < N; ++i) {
		ten = ten*10 % modu;
		nine = nine*9 % modu;
		eight = eight*8 % modu;
	}
	cout << ((ten - 2*nine + eight) % modu + modu) % modu << endl;
	return 0;
}

Measured memory_bytes: 3128
#!/usr/bin/env python
import os
import re
import sys
from io import BytesIO, IOBase
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


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


def main():
    x = inp()
    if x >= 400 and x <= 599:
        print(8)
    if x >= 600 and x <= 799:
        print(7)
    if x >= 800 and x <= 999:
        print(6)
    if x >= 1000 and x <= 1199:
        print(5)
    if x >= 1200 and x <= 1399:
        print(4)
    if x >= 1400 and x <= 1599:
        print(3)
    if x >= 1600 and x <= 1799:
        print(2)
    if x >= 1800 and x <= 1999:
        print(1)


# region fastio
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")

# endregion


if __name__ == "__main__":
    main()


Measured memory_bytes: 10056
n,m=map(int,input().split())
jouken=[]
for x in range(m):
  jouken.append(list(map(int,input().split())))

for x in range(10**n):
  ans=0
  xx=str(x)
  if not len(xx)==n:
    continue
  for y in range(m):
    a=jouken[y][0]-1
    b=jouken[y][1]
    
    
    if not int(xx[a])==b:
      ans+=1
    
  if ans==0:
    print(x)
    break

if ans>=1:
  print(-1)




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

typedef long long int ll;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll prefix[n+1];
    prefix[0]=0;
    ll ans=0,pre=0,a;
    map<ll,ll> m;
    m[0]++;
    for(ll i=0;i<n;i++)
    {
     cin>>a;
     a--;
     pre+=a;
     pre=pre%k;
     prefix[i+1]=pre;
     if(i>=(k-1))
      m[prefix[i-(k-1)]]--;
      ans+=m[pre];
      m[pre]++;
    }
    cout<<ans<<"\n";
    return 0;
}

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

int readInt(){
  int ret = 0;
  char c;
  while((c=getchar()) && '0' <= c && c <= '9'){
    ret = ret * 10 + (c-'0');
  }
  return ret;
}

main(){
  int n,s;
  while(true){
    n = readInt();
    if (n==0)break;
    s = readInt();

    int r[101]={0};
    for(int i=0;i<n;i++){
      int tmp;tmp=readInt();r[tmp]++;
    }
    int ans = 0;
    for(int i=1;i != 101;i++){
      if (r[i] && i+i > s)ans += r[i]*(r[i]-1)/2;
      if (!r[i])continue;
      for(int j=i+1;j != 101;j++){
	if (i+j > s)ans += r[i]*r[j];
      }
    }
    printf("%d\n",ans);
  }
}

Measured memory_bytes: 0
N, M = map(int, raw_input().split())
S = [True]*(N+1)
for _ in range(M):
  a = input()
  S[a] = False
T = [0]*(N+1)
T[0] = 1
T[1] = 1 if S[1] else 0
for i in range(2, N+1):
  if S[i]:
    T[i] = (T[i-1]+T[i-2])%1000000007
print T[N]


Measured memory_bytes: 9732
#include<iostream>
#include<vector>
#include<map>
#include<list>
#include<string>
#include<algorithm>
 
using namespace std;
 
int main() {
  string s;
  cin >> s;

  string f,e;
  f = s.substr(0,s.length()/2);
  e = s.substr((s.length()/2)+1);
  if(f==e){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
using namespace std;
 
string dir[6] = {"North", "East", "West", "South", "Right", "Left"};
 
int r[6][6] = { {1,5,2,3,0,4},
        {3,1,0,5,4,2},
        {2,1,5,0,4,3},
        {4,0,2,3,5,1},
        {0,2,4,1,3,5},
        {0,3,1,4,2,5} };
 
int main(){
  int n,d[6];
  string s;
 
  while(cin >> n,n){
    int ans = 1;
    for(int i=0;i<6;i++)d[i] = i+1;
    for(int i=0;i<n;i++){
      cin >> s;
 
      for(int j=0;j<6;j++){
    if(s == dir[j]){
      int tmp[6];
      for(int k=0;k<6;k++)tmp[k] = d[r[j][k]];
      for(int k=0;k<6;k++)d[k] = tmp[k];
      ans += d[0];
    }
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3176
#include <stdio.h>

int toSec(int h,int m,int s){
  return 3600*h+60*m+s;
}

void printTime(int s){
  printf("%d ",s/3600);
  s %= 3600;
  printf("%d ",s/60);
  s %= 60;
  printf("%d\n",s);
}

int main(void){
  int i,j;
  int t[2][3];

  while(1){
    for(i=0;i<2;i++){
      for(j=0;j<3;j++){
	if(scanf("%d",&t[i][j]) == EOF) return 0;
      }
    }
    printTime(toSec(t[1][0],t[1][1],t[1][2])-toSec(t[0][0],t[0][1],t[0][2]));
  }
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	char a, b;
	cin >> a >> b;
	
	if(a=='H')
	{
		cout << b;
		exit(0);
	}
	else
	{
		if(b=='H')
			cout << 'D';
		else
			cout << 'H';
	}
	
	return 0;
}



Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define print(A,n) for(ll i=0;i<n;++i)cout<<A[i]<<' ';cout<<endl;
#define take(A,n) for(ll i=0;i<n;++i)cin>>A[i];
ll mulmod(ll a,ll b,ll c) 
{ 
    if (b==0) 
        return 0; 
    ll s = mulmod(a, b/2, c); 
    if (b%2==1) 
        return (a%c+2*(s%c)) % c; 
 
    else
        return (2*(s%c)) % c; 
} 

  
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{ll int tc,x;
//t=1;
tc=1;

while(tc--)
{set< ll int> s;
ll int n,i;
cin>>n;
for(i=0;i<n;i++)
{
    cin>>x;
    s.insert(x);
}
if(s.size()==n)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
   
}
 
    return 0;
}

Measured memory_bytes: 9600
//██████╗ ██╗   ██╗██╗      ██████╗ ███████╗
//██╔══██╗██║   ██║██║      ██╔══██╗██╔════╝
//██████╔╝██║   ██║██║█████╗██║  ██║█████╗
//██╔══██╗██║   ██║██║╚════╝██║  ██║██╔══╝
//██║  ██║╚██████╔╝██║      ██████╔╝███████╗
//╚═╝  ╚═╝ ╚═════╝ ╚═╝      ╚═════╝ ╚══════╝
#include <iostream>
#include <random>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#include <chrono>
#include <cstdio>


// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define fst first
#define snd second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define sqr(x) ((x) * (x))

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

#define next ajksdslk
#define prev aklsfjk

mt19937_64 mt_rand(chrono::system_clock::now().time_since_epoch().count());

template<typename T1, typename T2> inline bool upmax(T1& a, T2 b) { return (a < b ? (a = b, true) : false); }
template<typename T1, typename T2> inline bool upmin(T1& a, T2 b) { return (b < a ? (a = b, true) : false); }

const int maxn = (int) 5e6 + 100;
const int maxlog = 21;
const int base = 1e9 + 7;
const ld eps = (ld) 1e-9;
const ld PI = acos(-1.);
//const int pp = 41;
const int inf = 2e9;
const ll llinf = 1e18;

int fact[maxn];


int bp(int a, int n) {
  int res = 1;
  while (n) {
    if (n & 1) res = 1ll * res * a % base;
    n >>= 1;
    a = 1ll * a * a % base;
  }
  return res;
}

int inv(int a) {
  return bp(a, base - 2);
}

int getc(int n, int k) {
  return 1ll * fact[n] * inv(fact[n - k]) % base * inv(fact[k]) % base;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  freopen ("input.txt", "r", stdin);
#endif
  fact[0] = 1;
  for (int i = 1; i < maxn; i ++) {
    fact[i] = 1ll * fact[i - 1] * i % base;
  }

  int x, y; cin >> x >> y;
  int cnta = 2 * x - y;
  int cntb = 2 * y - x;

  if (cnta % 3 || cntb % 3 || cnta < 0 || cntb < 0) {
    cout << 0;
    return 0;
  }
  cnta /= 3;
  cntb /= 3;

  cout << getc(cnta + cntb, cnta) << "\n";

  return 0;
}

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

using namespace std;

int main(void) {
	string s;
	cin >> s;
	for(int i = 0; i < s.length(); ++i) {
		cout << s[i];
		if(i == 3) cout << ' ';
	}
	cout << '\n';
	return 0;
}



Measured memory_bytes: 256
//\\//\\ * * * //\\// ||
#include <bits/stdc++.h> 

#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;

const int N = 110;

int a[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        if (a[i] != a[j] && a[i] != a[k] && a[j] != a[k]) {
          if (a[i] + a[j] > a[k]) {
            ++ans;
//            debug(i);
//            debug(j);
//            debug(k);
//            debug(a[i]);
//            debug(a[j]);
//            debug(a[k]);
          }
        } 
      }
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3628
#include<stdio.h>

int main(void){

	int a,b;
	int k;

	scanf("%d %d",&a,&b);

	k = a+b;

	if(k%2==1){
		printf("IMPOSSIBLE\n");

	}else{
		printf("%d\n",k/2);

	}

	


	return 0;
}

Measured memory_bytes: 128
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

B1 = [i-a for i, a in enumerate(A)]
B2 = [a+i for i, a in enumerate(A)]

c1 = dict(Counter(B1))
c2 = dict(Counter(B2))

SUM = 0
for k in c2.keys():
    if k in c1:
        SUM += c2[k] * c1[k]

print(SUM)

Measured memory_bytes: 73768
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;


int main () {
	int N, M;
	cin >> N;
	vector<string> s(N);
	for (int i = 0; i < N; i++) {
		cin >> s.at(i);
	}
	cin >> M;
	vector<string> t(M);
	for (int i = 0; i < M; i++) {
		cin >> t.at(i);
	}

	map<string, int> nouns;
	for (int i = 0; i < N; i++) {
		if (nouns.count(s.at(i))) {
			nouns.at(s.at(i)) = nouns.at(s.at(i)) + 1;
		}
		else {
			nouns.insert(make_pair(s.at(i), 1));
		}
	}
	for (int i = 0; i < M; i++) {
		if (nouns.count(t.at(i))) {
			nouns.at(t.at(i)) = nouns.at(t.at(i)) - 1;
		}
	}

	int max_noun = 0;
	for (auto i = nouns.begin(); i != nouns.end(); i++) {
		if (max_noun < i->second) max_noun = i->second;
	}
	cout << max_noun << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=(int) 2*1e5+5;
int b[N];
int c[N];
int main()
{
	long long i,n,ans=0,x,x1,x2;
	cin>>n;
	int a[n+4];
	for(i=1;i<=n;i++)
	{
    cin>>a[i];
    b[a[i]]++;
    c[a[i]]++;
	}
	for(i=1;i<=n;i++)
	{
		 x=b[a[i]];
		 b[a[i]]=0;
		ans=ans+(x*(x-1))/2;
	}
	//cout<<ans<<endl;
	for(i=1;i<=n;i++)
	{
   x1=c[a[i]]-1;
   x1=(x1*(x1-1))/2;
   x2=c[a[i]];
   x2=(x2*(x2-1))/2;
   x=ans-x2+x1;
   cout<<x<<endl;
	}
	return 0;

}

Measured memory_bytes: 3968
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <climits>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair

// ?????????0-origin??¨??????
template <typename T>
class Dijkstra {
    struct edge { int to; T cost; };
    typedef pair<T, int> P; // <???????????¢, ????????????>

public:
    T INF;

    Dijkstra(int V) 
        : INF(std::numeric_limits<T>::max())
        , m_V(V)
        {
        m_G.resize(m_V);
    }

    // a -> b?????????????????¨???????????????
    void add_dir_edge(int a, int b, T cost) {
        m_G[a].push_back( edge{ b, cost } );
    }

    // a <-> b?????????????????¨???????????????
    void add_undir_edge(int a, int b, int cost) {
        add_dir_edge(a, b, cost);
        add_dir_edge(b, a, cost);
    }

    // ??????s????????????????????§????????¢????¨????????????????
    vector<T> shortest_path(int s) {
        vector<T> d(m_V, INF);
        priority_queue<P, vector<P>, greater<P> > que;
        d[s] = 0;
        que.push(P(0, s));
    
        while(!que.empty()) {
            P p = que.top();
            que.pop();

            T dist = p.first;
            int v = p.second;
            if (d[v] < dist) continue;
            REP(i, m_G[v].size()) {
                edge e = m_G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }

        return d;
    }

private:
    int m_V;
    vector<vector<edge> > m_G;
};


int main(){
    int V, E, r;
    cin >> V >> E >> r;
    Dijkstra<int> dij(V);

    REP(e,E) {
        int v1, v2, cost;
        cin >> v1 >> v2 >> cost;
        dij.add_dir_edge(v1, v2, cost);
    }

    auto distances = dij.shortest_path(r);
    for(auto d : distances) {
        if (d == dij.INF) cout << "INF" << endl;
        else cout << d << endl;
    }

    return 0;
}

Measured memory_bytes: 11228
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
    long long N;
    cin>>N;
    string S;
    cin>>S;
    long long ans =1;

    for (int i = 0; i < N-1; ++i) {
        if (S[i] != S[i+1]){
            ans +=1;

        }
    }

    cout<<ans<<endl;

}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define nn 105
int ai[nn];
int n,k;
vector<int> ans;
void add(int x)
{
	ans.push_back(x);
	if(ai[x]==0)
	{
		puts("-1");
		exit(0);
	}
	ai[x]--;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>ai[i];
	
	int lst=0;ai[0]=12345243;
	for(int id=0;id<=k;id++)
	{
		int x=0;
		for(int i=1;i<=n;i++) if(i!=lst and ai[i]<ai[x]) x=i;
		
		for(int i=1;i<=n;i++) if(i!=x and i!=lst) add(i);
		add(x);lst=x; 
	}
	
	cout<<ans.size()<<"\n";
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
	
	return 0;
}

Measured memory_bytes: 256
import numpy as np

N, K = list(map(int, input().split()))

x = list(map(int, input().split()))


def calc(m, n, default=100000000):
    tmp = 0
    if m > n:
        tmp = m + 2*n
    else:
        tmp = 2*m + n

    min = tmp if default > tmp else default

    return min


def my_index(l, i, default=False):
    if i in l:
        return True
    else:
        return default


def main():
    global x, K
    if 0 in x:
        K -= 1
        if K == 0:
            return 0

    x = np.array(x)
    positives = x[np.where(x > 0)]
    negatives = x[np.where(x < 0)]

    nega_size = np.size(negatives)
    posi_size = np.size(positives)
    if nega_size == 0:
        return positives[K-1]

    if posi_size == 0:
        return abs(negatives[-K])

    if K <= nega_size and K <= posi_size:
        min = 1e9
        for i in range(K+1):
            if i == 0:
                min = abs(negatives[-K])
            elif i > 0 and i < K:
                ne = abs(negatives[-K+i])
                po = positives[i-1]
                min = calc(ne, po, min)
            elif i == K:
                tmp = positives[K-1]
                min = tmp if min > tmp else min

        return min

    if K > nega_size and K > posi_size:
        min = 1e9
        for i in range(N-K+1):
            ne = abs(x[i])
            po = x[K+i-1]
            min = calc(ne, po, min)

        return min

    if nega_size < K and K <= posi_size:
        min = 1e9
        for i in range(nega_size):
            po = x[K+i-1]
            ne = abs(x[i])
            min = calc(ne, po, min)

        min = abs(positives[K-1]) if abs(positives[K-1]) < min else min
        return min

    if posi_size < K and K <= nega_size:
        min = 1e9
        for i in range(posi_size):
            po = x[-i-1]
            ne = abs(x[-K-i])
            min = calc(po, ne, min)

        min = abs(negatives[-K]) if abs(negatives[-K]) < min else min
        return min


print(main())


Measured memory_bytes: 23140
A = []
B = [0]*9

# Aには [1, 2, 3, 4, 5, 6, 7, 8, 9] の形で格納.
for _ in range(3):
    A += [int(i) for i in input().split()]

# 印をつけた数字をBに残しておく.
n=int(input())
for _ in range(n):
    b = int(input())
    for i, a in enumerate(A):
        if b == a:
            B[i] = 1

#ビンゴの可能性がある組を作っておく.
C = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]
flag = 0

# Bで1と記録が残っていれば真
for a,b,c in C:
    if B[a-1] and B[b-1] and B[c-1]:
        flag = 1
print('Yes' if flag else 'No')

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

ans=[0]*N

for i in range(1,int(N**0.5)):
    if i**2 >=N:
        break
    for j in range(1,int(N**0.5)):
            if i**2+j**2+i*j>=N:
                break
            for k in range(1,int(N**0.5)):
                    if i**2+j**2+k**2+i*j+j*k+k*i <=N:
                        ans[i**2+j**2+k**2+i*j+j*k+k*i-1] +=1

for i in range(N):
    print(ans[i])

Measured memory_bytes: 9652
#include <stdio.h>
int main(void){
    int a;
    scanf("%d", &a);
    if(a < 105){
        printf("0");
    }else if(a < 135){
        printf("1");
    }else if(a < 165){
        printf("2");
    }else if(a < 189){
        printf("3");
    }else if(a < 195){
        printf("4");
    }else{
        printf("5");
    }

}


Measured memory_bytes: 1624
# 情報を取得
input = gets.chomp.split
a = input[0].to_i
b = input[1].to_i
x = input[2].to_i

puts (b / x) - ((a - 1) / x)

# # x で割り切れるものの個数を格納する変数を宣言
# count = 0

# # a 以上 b 以下の整数において、x で割り切れるか判定
# (a..b).each do |num|
#   if num % x == 0
#     count += 1
#   end
#   num += num
# end

# # 結果を出力
# puts count

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()

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

	long long l, r;
	scanf("%lld%lld", &l, &r);
	if (r - l >= 2019) {
		puts("0");
		return 0;
	}

	int ans = 2019;
	for (long long i = l; i < r; i++) for (int j = i+1; j <= r; j++)
		ans = min(ans, (int)((i * j) % 2019));
	printf("%d\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define vi vector<long long>
#define pi pair<long long, long long>
#define mp make_pair
#define endl '\n'
#define _ << ' '
#define min3(a, b, c) min(a, min(b, c))
#define min4(a, b, c, d) min(min(a, d), min(b, c))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)1e18+1;
const ll N = 2e5;
ll seg[2*N];
int n, q;

void build(){
    for(int i=n-1; i>0; i--) seg[i]=max(seg[i*2], seg[i*2+1]);
}

void change(int p, ll to){
    for(seg[p+=n]=to; p>1; p/=2) seg[p/2]=max(seg[p], seg[p^1]);
}

ll query(int l, int r)
{
    ll res=0;
    for(l+=n, r+=n; l<r; l/=2, r/=2)
    {
        if(l&1) res=max(res, seg[l++]);
        if(r&1) res=max(res, seg[--r]);
    }
    return res;
}

struct Flower
{
    ll h, b;
};
Flower v[200001];
ll ans=0;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    //freopen("C.txt", "r", stdin);
    #endif
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> v[i].h;
    }
    for(int i=0; i<n; i++)
    {
        cin >> v[i].b;
    }
    for(int i=0; i<n; i++)
    {
        ll before = query(0, v[i].h-1);
        change(v[i].h-1, before+v[i].b);
        ans = max(ans, before+v[i].b);
    }
    cout << ans;
}


Measured memory_bytes: 6528
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using vi = vector<int>;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define show(x) cout << #x << " = " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define YesNo {cout<<"Yes";}else{cout<<"No";}
#define YESNO {cout<<"YES";}else{cout<<"NO";}
#define v(T) vector<T>

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> bool lcmp(const pair<T, T>& l, const pair<T, T>& r) {
  return l.first < r.first;
}
template<class T> istream& operator>>(istream& i, v(T)& v) {
  F0R(j, sz(v)) i >> v[j];
  return i;
}
template<class A, class B> istream& operator>>(istream& i, pair<A, B>& p) {
  return i >> p.first >> p.second;
}
template<class A, class B, class C> istream& operator>>(istream& i, tuple<A, B, C>& t) {
  return i >> get<0>(t) >> get<1>(t) >> get<2>(t);
}
template<class T> ostream& operator<<(ostream& o, const vector<T>& v) {
  F0R(i, v.size()) {
    o << v[i] << ' ';
  }
  o << newl;
  return o;
}
template<class T1, class T2> ostream& operator<<(ostream& o, const map<T1, T2>& m) {
  for (auto& p : m) {
    o << p.first << ": " << p.second << newl;
  }
  o << newl;
  return o;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  set<string> s;
  string p;
  bool yes = true;
  F0R(i, N) {
    string w;
    cin >> w;
    if (s.find(w) != s.end() || (i && p.back() != w[0])) {
      yes = false;
      break;
    }
    s.insert(w);
    p = w;
  }
  if (yes) YesNo;
}
#endif


Measured memory_bytes: 3660
import sys
input = sys.stdin.readline
H,W,A,B= map(int,input().split())

MOD = 10**9 + 7
num = 200010
fact = [1] * (num+1)
ifact = [1] * (num+1)

for i in range(1,num+1):
    fact[i] = (fact[i-1] * i) % MOD
ifact[-1] = pow(fact[-1],MOD-2,MOD)
for i in range(1,num+1)[::-1]:
    ifact[i-1] = (ifact[i] * i)% MOD

def nCr(n,r):
    if r > n:
        return 0
    return (fact[n] * ifact[r] * ifact[n-r]) % MOD

ans = 0
for i in range(B+1,W+1):
    ans += nCr((i-1)+(H-A-1),i-1) * nCr((A-1)+(W-i),A-1)
    ans %= MOD
print(ans)


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



int main() {
    string s;
    cin >> s;
    
    bool a, b;
    a = b = false;
    
    rep(i,3) {
        if(s[i] == 'A')
            a = true;
        if(s[i] == 'B')
            b = true;
    }
    
    if(a && b)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}




Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0;
    cin>>n;
    vector<int>a(n);
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    double b=sum*1.0/n;
    int sum2=0,sum3=0;
    for(int i=0; i<n; i++)
    {

        sum2+=pow(a[i]-floor(b),2);
        sum3+=pow(a[i]-ceil(b),2);
    }
    cout<<min(sum2,sum3)<<endl;
}


Measured memory_bytes: 3648
import sys
import bisect

N, Q = map(int, input().split())
s = sys.stdin.readline().rstrip()
ac_list = []
start = 0
while True:
  index = s.find('AC', start)
  if index == -1:
    break
  ac_list.append(index + 1)
  start = index + 1


for _ in range(Q):
  l, r = map(int, input().split())
  res = 0
  start = bisect.bisect_left(ac_list, l)
  end = bisect.bisect_right(ac_list, r-1) - 1
  print(end-start+1)

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

int main(){
  int x, y, d, r;
  double f;

  cin >> x >> y;

  d = x/y;
  r = x%y;
  f = 1.0 * x/y;

  printf("%d %d %.5lf", d, r, f);

  return 0;
}

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

int gdc(int a,int b){
  if(b==0){
    return a;
  }
  gdc(b,a%b);
}

int main() { 
  int n,x;
  cin >>n;
  n=n+1;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin>> a.at(i);
  }
  sort(a.begin(),a.end());
  vector<int>b(n-1);
  for(int i=0;i+1<n;i++){
    b.at(i) = a.at(i+1)-a.at(i);
  }
  if(b.size()==1){
    cout << b.at(0);
    return 0;
  }
  int ans=b.at(0);
  for(int i=0;i<b.size();i++){
    ans = gdc(b.at(i),ans);
  }
  cout <<ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
//BIAR MANTAB LAH YA
#define Willy using
#define Indrayana namespace
#define Komara std
 
Willy Indrayana Komara;

bool besarDulu(const int &a, const int &b)
{
    return a > b;
}

bool tupleSort(tuple<int, int, int> &a, tuple<int, int, int> &b)
{
    return get<2>(a) > get<2>(b);
}

using ll = long long int;
const int MAX = 1000000000;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    ll a, b;
    cin >> a >> b;
    ll ans = ((n / (a + b)) * a) + (n % (a + b) > a ? a : n % (a + b));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main(){
	var N int
	var S string 
	var x, max int

	fmt.Scan(&N, &S)

	for i := 0 ; i < len(S) ; i++ {
		if S[i] == 'I' {
			x++
		}else {
			x--
		}
		if max < x{
			max = x
		}
		// fmt.Println(x)
	}
	fmt.Println(max)
}

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

int main() {
    int64_t n, x;
    cin >> n >> x;
    vector<int64_t> a(n);
    for (auto& e : a) cin >> e;

    int64_t ans = 0;
    for (int i = 0; i+1 < n; i++) {
        if (a[i] + a[i+1] <= x) continue;
        ans += a[i] + a[i+1] - x;
        a[i+1] = a[i] > x ? 0 : x - a[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#定石の商と剰余でやってみた

N, A, B = map(int, input().split())
ans = 0

for i in range(1,N+1):
  n = i
  sum = 0
  while n > 0:
    sum += n % 10
    n = n // 10
  if sum >= A and sum <= B:
    ans += i
    
print(ans)

Measured memory_bytes: 3060
n,m = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
mod = 10**9 + 7

dp = [[0 for j in range(m+1)] for i in range(n+1)]

sum_dp = [[0 for j in range(m+1)] for i in range(n+1)]

dp[0][0] = 1
for i,x in enumerate(S):
    for j,y in enumerate(T):
        if x == y:
            dp[i+1][j+1] = sum_dp[i][j]+1
            dp[i+1][j+1] %= mod
        else:
            dp[i+1][j+1] = 0
        sum_dp[i+1][j+1] = sum_dp[i][j+1]+sum_dp[i+1][j]-sum_dp[i][j]+dp[i+1][j+1]
        sum_dp[i+1][j+1] %= mod

ans = 0
for x in dp:
    ans += sum(x)
    ans %= mod

print(ans)

Measured memory_bytes: 109148
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.next().toCharArray();
		int length = arr.length;
		int[][] dp = new int[length + 1][13];
		dp[0][0] = 1;
		for (int i = 1; i <= length; i++) {
		    for (int j = 0; j < 13; j++) {
		        if (arr[i - 1] == '?') {
		            for (int k = 0; k < 10; k++) {
		                dp[i][(j * 10 + k) % 13] += dp[i - 1][j];
		                dp[i][(j * 10 + k) % 13] %= MOD;
		            }
		        } else {
		            dp[i][(j * 10 + arr[i - 1] - '0') % 13] += dp[i - 1][j];
		            dp[i][(j * 10 + arr[i - 1] - '0') % 13] %= MOD;
		        }
		    }
		}
		System.out.println(dp[length][5]);
   }
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

int imax=2147483647;
long long int llimax=9223372036854775807;

//int型vectorを出力
void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

//LLi型vectorを出力
void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

int main(){

	int a, b;
	cin>> a >> b;

	cout<< a*b << endl;
 
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
typedef long long ll;
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
char s[MAXN][MAXN];
short l[MAXN][MAXN], r[MAXN][MAXN];
int n, a[MAXN][MAXN], res[MAXN][MAXN];
inline void chkmax(short &x, short y) {if (y > x) x = y; }
inline void chkmin(short &x, short y) {if (y < x) x = y; } 
int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s[i] + 1);
		for (int j = 1; j <= n; j++)
			if (s[i][j] == '#') a[i][j] = 0;
			else a[i][j] = s[i][j] - '0';
	}
	ll finalans = 0;
	for (int i = n; i >= 1; i--)
	for (int j = n; j >= 1; j--) {
		if (a[i][j] != 0) {
			if (a[i + 1][j] == 0 && a[i][j + 1] == 0) l[j][i] = r[j][i] = j;
			else if (a[i + 1][j] == 0) {
				memcpy(l[j] + i, l[j + 1] + i, sizeof(short) * (n - i + 1));
				memcpy(r[j] + i, r[j + 1] + i, sizeof(short) * (n - i + 1));
				l[j][i] = j, res[i][j] = res[i][j + 1];
			} else if (a[i][j + 1] == 0) {
				l[j][i] = r[j][i] = j;
				res[i][j] = res[i + 1][j];
			} else {
				short Max = 0; int ans = res[i + 1][j] + res[i][j + 1];
				l[j][i] = j, r[j][i] = r[j + 1][i];
				for (int k = i + 1; k <= n; k++) {
					if (r[j][k] >= l[j + 1][k] && l[j + 1][k] > Max) ans -= res[k][l[j + 1][k]];
					chkmax(Max, r[j][k]);
					chkmax(r[j][k], r[j + 1][k]);
					chkmin(l[j][k], l[j + 1][k]);
				}
				res[i][j] = ans;
			}
			finalans += a[i][j] * res[i][j];
			res[i][j] += a[i][j];
		} else {
			memset(l[j] + i, 0x3f, sizeof(short) * (n - i + 1));
			memset(r[j] + i, 0, sizeof(short) * (n - i + 1));
		}
	}
	cout << finalans << endl;
	return 0;
}

Measured memory_bytes: 29056
// 2012/11/19 Tazoe

#include <iostream>
#include <algorithm>
using namespace std;

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

	int A, B;
	cin >> A >> B;

	int C;
	cin >> C;

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

	sort(D, D+N);

	int c_sum = C;
	int p_sum = A;

	for(int i=N-1; i>=0; i--){
		if(c_sum/p_sum>(c_sum+D[i])/(p_sum+B)){
			break;
		}
		else{
			c_sum += D[i];
			p_sum += B;
		}
	}

	cout << c_sum/p_sum << '\n';

	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define LINF 1e18
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const double PI = acos(-1.0);
const double EPS = 1e-10;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    vector<int> A(N+1),B(N);
    REP(i,N+1) cin>>A[i];
    REP(i,N) cin>>B[i];
    ll ans = 0;
    REP(i,N){
        if(A[i]<=B[i]){
            ans+=A[i];
            B[i] -= A[i];
        }
        else{
            ans += B[i];
            B[i] = 0;
        }
        if(A[i+1]<=B[i]){
            ans += A[i+1];
            B[i] -= A[i+1];
            A[i+1] = 0;
        }
        else{
            ans += B[i];
            A[i+1] -= B[i];
            B[i] = 0;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
import Data.Array
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

main = do
    [n,k] <- map read.words <$> getLine :: IO [Int]
    hs <- map (fst.fromJust.BS.readInt).BS.words <$> BS.getLine :: IO [Int]
    print $ answer n k $ listArray (1,n) hs

answer n k hs = dp ! 1 where
    -- table = listArray ((1,1), (n,n)) [ x#y | x <- [1..n], y <- [1..n] ]
    dp = array (1,n) $ (n,0): (n-1, n#(n-1)):[ (now, move now) | now <- [1..n-2] ]
    move now = minimum $ map (\i -> (dp!(now+i) + now#(now+i))) [1..min k (n-now)]
    a # b = abs $ (hs!a) - (hs!b)

Measured memory_bytes: 88444
import java.util.Scanner;

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

		// 入力値の取得
		String S = sc.next();
		String T = sc.next();
		
		// 結果の出力
		System.out.println(T + S);
		
		sc.close();
	}
}


Measured memory_bytes: 39520
#include <stdio.h>
#include <limits.h>
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
#define MAX(X, Y) (((X) < (Y)) ? (Y) : (X))

int main()
{
	int N, i;
	int min_v = INT_MAX, max_v = INT_MIN;

	scanf("%d", &N);
	int R[N];
	for (i = 0; i < N; i++)
		scanf("%d", &R[i]);
	for (i = 0; i < N; i++) {
		max_v = MAX(max_v, R[i]-min_v);
		min_v = MIN(min_v, R[i]);
	}
	printf("%d\n", max_v);
	return 0;
}



Measured memory_bytes: 2536
#include<iostream>

using namespace std;

int a[1000001];

int main()
{
    int K;

    cin >> K;

    a[1] = 7 % K;

    for (int i = 2; i <= K; i++)
        a[i] = (a[i - 1] * 10 + 7)%K;

    for (int i = 1; i <= K; i++)
        if (a[i] ==0) {
            cout << i;
            return 0;
        }

    cout << -1;
}

Measured memory_bytes: 7504
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using vv = vector<V<T>>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int a[5];
  REP(i,5) cin >> a[i];
  int b = -1,c = 10;
  REP(i,5){
    if((a[i]+9)%10<c){
      c = a[i]%10;
      b = i;
    }
  }
  int ans = 0;
  REP(i,5){
    if(i!=b) ans += (a[i]+9)/10*10;
    else ans += a[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream> 
#include<algorithm>
#include<climits>

using namespace std;

#define N 5
#define REP(i, n) for ( int i = 0; i < (int)n; i++ )
#define LIMIT 20

// S[ÌÇ±É éÌ©
static const int T[12][2] = {
	{-1, -1},
	{1, 1},
	{1, 2},
	{1, 3},
	{2, 0},
	{2, 1},
	{2, 2},
	{2, 3},
	{2, 4},
	{3, 1},
	{3, 2},
	{3, 3}
};

// S[Ìzu
static const int g[N][N] = {
	{-1, -1,  0, -1, -1},
	{-1,  1,  2,  3, -1},
	{ 4,  5,  6,  7,  8},
	{-1,  9, 10, 11, -1},
	{-1, -1,  0, -1, -1}
};

class Puzzle
{
public:
	int C[N][N], mdist; //manhatta distance
	Puzzle(){}
	
	bool swapAdj( int si, int sj, int ti, int tj )
	{
		if ( ti < 0 || tj < 0 || ti >= N || tj >= N )
			return false;
		if ( C[ti][tj] <= 0 )
			return false;

		swap( C[ti][tj], C[si][sj] );

		int tti = T[C[si][sj]][0];
		int ttj = T[C[si][sj]][1];
		mdist -= max(tti, ti)-min(tti, ti) + max(ttj, tj)-min(ttj, tj);
		mdist += max(tti, si)-min(tti, si) + max(ttj, sj)-min(ttj, sj);
		return true;
	}
	
	bool isGoal()
	{
		REP(i, N) REP(j, N)
			if ( g[i][j] != C[i][j] )
				return false;
		return true;
	}
	
	// get initial manhattan distance
	int getMD()
	{
		int sum = 0;
		int ti, tj;
		REP(i, 5) REP(j, 5)
		{
			if ( C[i][j] <= 0 )
				continue;
			ti = T[C[i][j]][0];
			tj = T[C[i][j]][1];
			sum += (max(ti, i)-min(ti, i) + max(tj, j) - min(tj, j));
		}
		return sum;
	}
};
 
int limit;
 
bool dfs( int depth, Puzzle P )
{
	if ( P.isGoal() )
		return true;
	if ( depth + P.getMD() > limit )
		return false;
	
	static const int di[4] = {0, -1, 0, 1};
	static const int dj[4] = {1, 0, -1, 0};
	
	REP(i, N) REP(j, N)
	{
		if ( P.C[i][j] != 0 )
			continue;

		REP(r, 4)
		{
			Puzzle v = P;
			if ( !v.swapAdj(i, j, i+di[r], j+dj[r]) )
				continue;
			if ( dfs( depth + 1, v ) )
				return true;
		}
	}
	
	return false;
}

int idp(Puzzle source)
{
	for ( limit = 0; limit <= LIMIT; limit++ )
	{
		source.mdist = source.getMD();
		if ( dfs(0, source) )
			return limit;
	}
	return INT_MAX;
}

int main()
{
	Puzzle P;
	int top;
	
	while(1)
	{
		cin >> top;
		if ( top == -1 ) break;
		REP(j, N) P.C[0][j] = -1;
		P.C[0][2] = top;
		for(int i = 1; i < N; i++) REP(j, N)
		{
			if ( (i == 1 || i == 3) && (j == 0 || j == 4 ) )
				P.C[i][j] = -1;
			else if ( i == 4 && j != 2 )
				P.C[i][j] = -1;
			else
				cin >> P.C[i][j];
		}
	
		int cost = idp(P);
		
		if ( cost == INT_MAX )
			cout << "NA" << endl;
		else
			cout << cost << endl;	
	}
	
	return 0;
}

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

using namespace std;

int main() {
  int n; long long k;
  cin >> n >> k;
  vector <long long> p(n + 1, 0);
  long long cur = 0;
  map <long long, long long> cnt;
  cnt[0] = 1;
  long long ans = 0;
  for(int i = 0; i < n; i++) {
    long long x; cin >> x;
    x--;
    cur = (cur + x) % k;
    p[i + 1] = cur;
    if(i >= k - 1) cnt[p[i - k + 1]]--;
    if(cnt.count(cur)) {
      ans += cnt[cur];
      cnt[cur] += 1;
    }
    else {
      cnt[cur] = 1;
    }
  }
  cout << ans << '\n';
}

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

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,x,gray=0,brown=0,red=0,orange=0,light=0,blue=0,green=0,yellow=0,any=0,min=0,max=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        if(x>=1&&x<=399)
            gray++;
        if(x>=400&&x<=799)
            brown++;
        if(x>=800&&x<=1199)
            green++;
        if(x>=1200&&x<=1599)
            light++;
        if(x>=1600&&x<=1999)
            blue++;
        if(x>=2000&&x<=2399)
            yellow++;
        if(x>=2400&&x<=2799)
            orange++;
        if(x>=2800&&x<=3199)
            red++;
        if(x>3199)
            any++;
    }
    if(gray!=0)min+=1;
    if(brown!=0)min+=1;
    if(green!=0)min+=1;
    if(light!=0)min+=1;
    if(blue!=0)min+=1;
    if(yellow!=0)min+=1;
    if(red!=0)min+=1;
    if(orange!=0)min+=1;
    max=min+any;
    if(min==0)min=1;
    cout<<min<<" "<<max<<endl;
	return 0;
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int>   vi;
typedef vector<long long> vll;
typedef vector<pair<int,int> > vii;
#define ll long long
#define pb push_back
#define mp  make_pair
#define ff first
#define ss second
#define pq priority_queue
#define sf1(x) scanf("%d",&x)
#define sf2(x,y) scanf("%d %d",&x,&y)
#define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z)
int inf = (1e9) + 7;


int main(){

	ll total = 0;
	int n;
	int a,b;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		sf2(a,b);
		total += b - a + 1;
	}
	printf("%lld\n",total );
}	

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <deque>

using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef deque<pair<ll,ll>> dep;

int inf=1e9+1000;
const int mod=1e9+7;
ll infi=1e18+100;

//x=10111;
//x<<2 = 1011100 (右シフト),x>>2 = 101 (左シフト)
//(x>>2)&1 = 101 & 001 = 1
//iビット目は、(x>>i) & 1 でわかる(x>>i)%2 でもよい

string alpha="abcdefghijklmnopqrstuvwxyz";

int n,m;



int main(){
	cin>>n>>m;
	cout<<(n-1)*(m-1)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e8;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
vector<vector<char> >tmp;
vector<vector<int> >scr;
int main(){
	ll dp[30]={1,2,4};
	loop(i,3,30)dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
	int n;
	while(cin>>n,n){
		ll d=dp[n-1];
		d=(d+9)/10;
		cout<<(d+364)/365<<endl;
	}
}

Measured memory_bytes: 1156
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)
#define INF 10000000

typedef long long ll;
typedef pair<ll, ll> P;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z


int dx4[4]={1,0,-1,0};
int dy4[4]={0,1,0,-1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

void solve(void){
    ll n;
    scanf("%lld\n", &n);
    ll small=1, large=n;
    for (;small * small <= n; small++){
        if(n % small == 0) large = n / small;
    }
    ll digit = 0;
    while(large > 0) {
        large /= 10;
        digit++;
    }
    printf("%lld\n", digit);
}

int main(void){
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
   int a,b,c;
   cin >> a;
   cin >> b;
   cin >> c;

   if(a <= b && b <= c){
       cout << a<< " "  << b<< " "  << c;
   }
   else if(a <= c && c <= b){
       cout << a << " " << c<< " "  << b;
   }
   else if(b < a && a < c){
       cout << b << " " << a << " " << c;
   }
   else if(b <= c && c <= a){
       cout << b << " " << c << " " << a;
   }
   else if(c <= a && a<= b){
       cout << c << " " << a << " " << b;
   }
   else{
       cout << c<< " "  << b<< " "  << a;
   }

   cout << endl;
}


Measured memory_bytes: 3092
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

ll t[200000];

int main(){
  int N;  ll T;
  cin >> N >> T;
  for(int i=0; i<N; i++)
    cin >> t[i];
  ll sum = T; // last
  for(int i=0; i<N-1; i++) {
    if(t[i+1] - t[i] < T)
      sum += t[i+1] - t[i];
    else
      sum += T;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1792