akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<double, double> P;
int bit[40001], n;
 
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=(i&(-i));
	}
	return s;
}
 
void add(int i){
	while(i<=n){
		bit[i]+=1;
		i+=(i&(-i));
	}
}
int main()
{
  cin>>n;
  double a[40000], b[40000], c[40000];
  for(int i=0; i<n; i++) cin>>a[i]>>b[i]>>c[i];
  P p[40000];
  double x1=-2e8, x2=2e8;
  for(int t=0; t<100; t++){
    double x=(x1+x2)/2;
    map<double, int> mp;
    for(int i=0; i<n; i++){
      p[i]=P(a[i]/b[i], c[i]/b[i]-x*a[i]/b[i]);
      mp[c[i]/b[i]-x*a[i]/b[i]]=0;
    }
    sort(p, p+n);
    int i0=1;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++){
      itr->second=i0;
      i0++;
    }
    fill(bit, bit+n+1, 0);
    int ct=0;
    for(int i=0; i<n; i++){
      int s=mp[p[i].second];
      ct+=(i-sum(s-1));
      add(s);
    }
    if(ct<(1+(ll)n*((ll)n-1)/2)/2) x1=x;
    else x2=x;
  }
  printf("%.10lf ", x1);
  x1=-2e8, x2=2e8;
  for(int t=0; t<100; t++){
    double x=(x1+x2)/2;
    map<double, int> mp;
    for(int i=0; i<n; i++){
      p[i]=P(b[i]/a[i], c[i]/a[i]-x*b[i]/a[i]);
      mp[c[i]/a[i]-x*b[i]/a[i]]=0;
    }
    sort(p, p+n);
    int i0=1;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++){
      itr->second=i0;
      i0++;
    }
    fill(bit, bit+n+1, 0);
    int ct=0;
    for(int i=0; i<n; i++){
      int s=mp[p[i].second];
      ct+=(i-sum(s-1));
      add(s);
    }
    if(ct<(1+(ll)n*((ll)n-1)/2)/2) x1=x;
    else x2=x;
  }
	printf("%.10lf\n", x1);
	return 0;
}

Measured memory_bytes: 6528
#include<iostream>
using namespace std;
int main()
{
	double n;
	while((cin>>n)!=0){
		if(n<=48.00)cout<<"light fly";
		else if(n<=51)cout<<"fly";
		else if(n<=54)cout<<"bantam";
		else if(n<=57)cout<<"feather";
		else if(n<=60)cout<<"light";
		else if(n<=64)cout<<"light welter";
		else if(n<=69)cout<<"welter";
		else if(n<=75)cout<<"light middle";
		else if(n<=81)cout<<"middle";
		else if(n<=91)cout<<"light heavy";
		else cout<<"heavy";
		cout<<endl;
	}
	return 0;
}

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

int main(){
  int a,b;
  cin >> a >> b;
  if(a>12) cout << b;
  else if(a>5) cout << b/2;
  else cout << 0;
  
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
H = list(map(int, input().split()))
G = [[] for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)

ans = 0

for v in range(N):
    flag = True
    for nv in G[v]:
        if H[nv]>=H[v]:
            flag = False
    if flag:
        ans += 1

print(ans)

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

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

    if(a > b) swap(a,b);
    if(a > c) swap(a,c);
    if(b > c) swap(b,c);

    cout << a << " " << b << " " << c << endl;

    return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int H,W;
    cin >> H >> W;
    string tmp;
    char c = 'A';
    int ans;
    for(int i = 0;i < H;i++)
    {
        for(int j = 0;j < W;j++)
        {
            cin >> tmp;
            if(tmp == "snuke")
            {
                c += j;
                ans = i + 1;
            }
        }
    }
    cout << c << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
N, L = map(int, input().split())
a = list(map(int, input().split()))

sum = [0]*(N - 1)
for i in range(N-1):
    sum[i] = a[i] + a[i+1]

if max(sum) < L:
    print("Impossible")
else:
    print("Possible")
    id = sum.index(max(sum))
    for i in range(id):
        print(i+1)
    for i in reversed(range(id+1, N-1)):
        print(i+1)
    print(id+1)


Measured memory_bytes: 14304
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;

#define rep(i,x,y) for(int i=(x); i<(y); ++i)
const int INF = (1<<30);
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;

template <typename T>
void vec_print(vector<T> VEC){
  rep(i, 0, VEC.size()){
    cout << VEC[i] << " ";
  }
  cout << "\n";
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  rep(i, 0, MAT.size()){
    rep(j, 0, MAT[i].size()){
      cout << MAT[i][j] << " ";
    }
    cout << "\n";
  }
};

class HOGE{
  public:
    ll index;
    ll value;
    HOGE(ll index, ll value){
      this->index = index;
      this->value = value;
    };
    ~HOGE(void){
      return;
    };

    void print(void){
      cout << "index : " << index << ", value : " << value << "\n";
      return;
    };
    
    bool operator==(const HOGE &obj){
      return (this->value == obj.value);
    };
    bool operator<(const HOGE &obj){
      return (this->value < obj.value);
    };
    bool operator>(const HOGE &obj){
      return (this->value > obj.value);
    };
};

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  int N;
  long int A, B;

  cin >> N;
  cin >> A;
  cin >> B;

  vector<long int> P;
  P.resize(N);
  for(int i=0; i<N; ++i){
    cin >> P[i];
  }
  
  sort(P.begin(), P.end());

  int A_index=N;
  int B_index=N;

  for(int i=0; i<N; ++i){
    if(P[i]>A){
      A_index=i;
      break;
    }
  }
  for(int i=0; i<N; ++i){
    if(P[i]>B){
      B_index=i;
      break;
    }
  }

  cout << max(min(min(A_index, B_index-A_index), N-B_index), 0) << "\n";

  return 0;
}


Measured memory_bytes: 256
program B085
    implicit none
    integer(8) :: N
    integer(8), allocatable, dimension(:) :: d
    integer(8) :: i, max, sum

    read(5,*) N
    allocate(d(N))
    do i = 1, N
        read(5,*) d(i)
    end do

    sum = 0
    max = maxval(d)
    do while (max /= 0)
        sum = sum + 1
        do i = 1, N
            if (max == d(i)) then
                d(i) = 0
            end if
        end do
        
        max = maxval(d)
    end  do


    write(6,*) sum




end program B085

Measured memory_bytes: 2820
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
#include <list>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;

vvi mul(vvi A, vvi B, ll M) {
	vvi C(A.size(), vi(B[0].size()));
	REP(i, A.size()) {
		REP(k, B.size()) {
			REP(j, B[0].size()) {
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
			}
		}
	}
	return C;
}

vvi pow(vvi A, ll n, ll M) {
	vvi B(A.size(), vi(A.size()));
	REP(i, A.size()) {
		B[i][i] = 1;
	}
	while (n > 0) {
		if (n & 1) {
			B = mul(B, A, M);
		}
		A = mul(A, A, M);
		n >>= 1;
	}
	return B;
}

int main() {
	int N, M, A, B, C, T;
	while (cin >> N >> M >> A >> B >> C >> T, N) {
		vvi mat(N, vi(N));
		REP(i, N) {
			if (i != N - 1) {
				mat[i + 1][i] = A;
			}
			mat[i][i] = B;
			if (i != 0) {
				mat[i - 1][i] = C;
			}
		}

		vvi S(N, vi(1));
		REP(i, N) {
			cin >> S[i][0];
		}

		vvi ans = mul(pow(mat, T, M), S, M);
		REP(i, N) {
			cout << ans[i][0];
			if (i != N - 1) {
				cout << " ";
			}
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1320
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>

using namespace std;
typedef complex<double> P;

int N;
P dots[300];
#define EPS (1e-6)


int main(){

	while(cin >> N && N != 0){
        for(int i = 0; i < N; i++){
            P p;
            double x,y;
            cin>>x>>y;
            dots[i]=P(x,y);
            //cin >> dots[i].second >> dots[i].first;
		}
		int maxCnt = 1;
		// ~ðìé½ßÌQ_ðßé
		for(int i = 0; i < N; i++){
			for(int j = i+1; j < N; j++){
                //pair<double,double> dot1,dot2;
                P dot1,dot2;
				dot1 = dots[i];
				dot2 = dots[j];
                //double v = sqrt((dot1.first - dot2.first)*(dot1.first - dot2.first)
                //+(dot1.second - dot2.second)*(dot1.second - dot2.second));
                double v=abs(dot1-dot2);
				// ñ_Ô£ª2æè¨¨«¯êÎÂ­êÈ¢
				if(v > 2.0 + EPS){
					continue;
				}
                double x = sqrt(1 - (v/2)*(v/2));
				// ñgÌPÊ@üxNg
				P hose[2];
                double y1 = -1.0/(dots[i].imag() - dots[j].imag());
                double x1 = 1.0/(dots[i].real() - dots[j].real());
                hose[0]=P(x1,y1);
                double y2 = 1.0/(dots[i].imag() - dots[j].imag());
                double x2 = -1.0/(dots[i].real() - dots[j].real());
                hose[1]=P(x2,y2);

				//double dd1 = sqrt((hose[0].second)*(hose[0].second)+(hose[0].first)*(hose[0].first));
                //double dd2 = sqrt((hose[1].second)*(hose[1].second)+(hose[1].first)*(hose[1].first));
                double dd1=abs(hose[0]);
                double dd2=abs(hose[1]);
                hose[0]/=dd1;hose[0]*=x;
                hose[1]/=dd2;hose[1]*=x;
                P tmp=(dot1+dot2);
                tmp/=2;
                hose[0]+=tmp;
                hose[1]+=tmp;

    //            hose[0].first /= dd1; hose[0].second /= dd1;
				//hose[1].first /= dd2; hose[1].second /= dd2;
				// x{·é
				//hose[0].first *= x;hose[1].first *= x;
				//hose[0].second *= x;hose[1].second *= x;

				// mð«·
				//hose[0].first += (dot1.first + dot2.first)/2;
				//hose[0].second += (dot1.second + dot2.second)/2;
				//hose[1].first += (dot1.first + dot2.first)/2;
				//hose[1].second += (dot1.second + dot2.second)/2;

				// hose[0]Æhose[1]Í~ÌSÀW
				// e_ÉÖµÄ~ÌÉ¶Ý·é©Ç¤©ðßé
				for(int k = 0; k < 2; k++){
                    int cnt = 0;
					for(int l = 0; l < N; l++){
						//double dist = sqrt((dots[l].first -hose[k].first)*(dots[l].first -hose[k].first)
						//	+ (dots[l].second -hose[k].second)*(dots[l].second -hose[k].second));
                        double dist=abs(dots[l]-hose[k]);
						if(dist <= 1.0 + EPS){
							cnt++;
						}
					}
					maxCnt = max(maxCnt,cnt);
				}
			}
		}
		cout << maxCnt << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL << 50;
struct Edge
{
    ll to;
    ll cost;
};

int main()
{
    ll n;
    cin >> n;
    vector<vector<Edge>> ab(n);
    for (int i = 0; i < n - 1; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        ab[a].push_back({b, c});
        ab[b].push_back({a, c});
    }
    ll q, k;
    cin >> q >> k;
    k--;
    vector<P> xy;
    for (int i = 0; i < q; i++)
    {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        xy.emplace_back(x, y);
    }
    priority_queue<P, vector<P>, greater<P>> Q;
    Q.push(make_pair(0, k));
    vector<ll> dist(n + 5, INF);
    dist[k] = 0;
    while (!Q.empty())
    {
        auto item = Q.top();
        Q.pop();
        for (int i = 0; i < (int)ab[item.second].size(); i++)
        {
            ll temp_to = ab[item.second][i].to;
            ll temp_cost = ab[item.second][i].cost;
            if (dist[temp_to] <= dist[item.second] + temp_cost)
            {
                continue;
            }
            dist[temp_to] = dist[item.second] + temp_cost;
            Q.emplace(dist[temp_to], temp_to);
        }
    }
    for (int i = 0; i < q; i++)
    {
        cout << dist[xy[i].first] + dist[xy[i].second] << endl;
    }
    return 0;
}


Measured memory_bytes: 15756
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  string S;
  cin >>S;
  int x=S.size();
  
  int y=0;
  rep(i,x) {
    if(S.at(i)=='A') {
      y=i;
      break;
    }
  }
  
  
  int count=0;
  vector<int> vec(x);
  repl(j,y,x) {
    if(S.at(j)=='Z') {
      vec.at(j)=j;
    }
  }
  sort(all(vec));
  cout<<vec.at(x-1)-y+1<< endl;
}
    


Measured memory_bytes: 1412
#include <stdio.h>

int main(void){
	int a = 0, b = 0;
	
	scanf("%d", &a);
	scanf("%d", &b);
	
	if((a * b) % 2 == 0)
		printf("Even\n");
	else
		printf("Odd\n");
	
	return 0;
}

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

#define DEBUG(x) // cerr << #x << " = " << x << endl

const double EPS = 1e-8;

double deg_long(int hh, int mm) {
    hh %= 12;
    long double deg = (1.0 * 360) * hh / 12;
    deg += (1.0 * 360 / 12) * mm / 60;
    return deg;
}

double deg_short(int mm) {
    double deg = 1.0 * 360 * mm / 60;
    return deg;
}

int main() {
    int N; scanf("%d", &N);
    while(N--) {
        int hh, mm; scanf("%d:%d", &hh, &mm);
        double degA = deg_long(hh, mm);
        double degB = deg_short(mm);
        DEBUG(degA);
        DEBUG(degB);
        double diff = abs(degA - degB);
        diff = min(diff, abs((degA + 360) - degB));
        diff = min(diff, abs(degA - (degB + 360)));
        DEBUG(diff);
        if (diff < 30 - EPS) puts("alert");
        else if(90 - EPS < diff) puts("safe");
        else puts("warning");
    }
}

Measured memory_bytes: 1160
N = int(input())
S = input()

ans = 99999999

cnt_w = 0
cnt_e = 0
i = 0
for j in range(i):
    if S[j] == 'W':
        cnt_w += 1
for j in range(i,N):
    if S[j] == 'E':
        cnt_e += 1
ans = cnt_w + cnt_e

for i in range(N):
    if S[i] == 'W':
        cnt_w += 1
    else:
        cnt_e -= 1
    ans = min(cnt_w + cnt_e, ans)
print(ans)

Measured memory_bytes: 3828
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
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;}

bool check_row[100],check_col[100];
int H,W,i,j;
string a[100];
inline void solve(){
  while(IN2(H,W)){
    REP(i,H){
      IN(a[i]);
      REP(j,W)if(a[i][j]=='#')break;
      if(j==W)check_row[i]=true;
    }
    REP(j,W){
      REP(i,H)if(a[i][j]=='#')break;
      if(i==H)check_col[j]=true;
    }
    REP(i,H){
      if(check_row[i])continue;
      REP(j,W){
        if(check_col[j])continue;
        cout<<a[i][j];
      }
      cout<<endl;
    }
  }

}

int main(int argc,char**argv){
  BEGIN
  solve();
  END
}


Measured memory_bytes: 256
#include <stdio.h>
#define N 44
#define INI -1
  
int fibo(int);
void ini(int);

int F[N];

int main(){

  int n = 0;

  scanf("%d",&n);

  ini(n);
  
  printf("%d\n",fibo(n));
  
  return 0;
}

int fibo(int n){
  
  if(n == 1 || n == 0)return F[n] = 1;
  if(F[n] != INI)return F[n];
  return F[n] = fibo(n-2) + fibo(n-1);
  
}

void ini(int n){
  
  int i = 0;
  
  for(i = 0; i <= n; i++){
    F[i] = INI;
  }
  
}



Measured memory_bytes: 2108
N,M = map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
for i in range(M):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.group_count())

Measured memory_bytes: 69592
#pragma region header
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr int inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() {
    int n;cin >> n;
    string s;cin >> s;
    int count = 0;
    rep(i, 1000) {
        bool a=false,b=false;
        rep(j, n) {
            if(!a){if(s[j]-'0'==i/100){a=true;/*cout << "a:" << i << ' '<< j << endl; */}}
            else if(a&&!b){if(s[j]-'0'==i/10%10){b=true;/*cout << "b:" << i << ' ' << j << endl;*/}}
            else if(b){if(s[j]-'0'==i%10){count++;/*cout << "c:" << i << endl;*/break;}}
        }
    }
    cout << count << endl;
    // cout << 10/100 << endl;
    return 0;
}

Measured memory_bytes: 3692
#include <cstdio>
bool a[405][405],u[405];
int x[100005],y[100005],n,m;
bool check(int i,int j){
	if (!u[i] || !u[j]) return 0;
	for (int k=1;k<=n;k++)
		if (a[i][k] && a[j][k]) return 0;
	return 1;
}
int main(){
	scanf("%d%d\n",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d%d\n",&x[i],&y[i]);
	for (int i=1;i<=n;i++){
		a[i][i]=u[i]=1;
		for (int j=m;j && u[i];j--)
		if (a[i][x[j]] && a[i][y[j]]) u[i]=0;
		else if (a[i][x[j]] || a[i][y[j]]) a[i][y[j]]=a[i][x[j]]=1;
	}
	int ans=0;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++) ans+=check(i,j);
	printf("%d\n",ans);
}

Measured memory_bytes: 1152
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

# N = int(input())
S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

Q = int(input())
query = [list(input().split()) for _ in range(Q)]
direction = 1
S_front = ""
S_back = ""
for l in query:
    if l[0] == "1":
        direction *= -1
    else:
        if (l[1] == "1" and direction == 1) or (l[1] == "2" and direction == -1):
            S_front += l[2]
        else:
            S_back += l[2]

if direction == 1:
    print(S_front[::-1] + S + S_back)
else:
    print(S_back[::-1] + S[::-1] + S_front)

Measured memory_bytes: 30500
/**
 *      AGC 23 A
 *      author  : kyomukyomupurin
 *      created : 2018-09-11 01:40:56
**/
     
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
     
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
        
    int N; scanf("%d", &N);
    int A[N] = {};
    for (int i = 0; i < N; ++i) {
        scanf("%d", &A[i]);
    }
     
    ll s[N] = {};
    s[0] = A[0];
    for (int i = 1; i < N; ++i) {
        s[i] = A[i] + s[i - 1];
    }
     
    sort(s, s + N);
     
    ll answer = 0;
    int begin = 0;
     
    for (int i = 0; i < N; ++i) {
        if (s[i] == 0){
            ++answer;
        }
    }
     
    while (begin < N){
        int end = begin;
        while (end + 1 < N && s[end + 1] == s[begin]){
            ++end;
        }
        ll len = end - begin + 1;
        answer += len * (len - 1) / 2;
        begin = end + 1;
    }
    cout << answer << '\n';          
    return 0;
}

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

int main() {
    int N; cin >> N;
    vector<int> A(N);
    rep(i, N){
        int a; cin >> a;
        A[i] = a;
    }

    sort(A.begin(),A.end());

    int ans = 0;
    rep(i, N){
        int counter = 1;
        while(A[i] == A[i+1]){
            counter++;
            i++;
        }
        ans += counter % 2;
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val h1 = sc.nextInt()
    val m1 = sc.nextInt()
    val h2 = sc.nextInt()
    val m2 = sc.nextInt()
    val k = sc.nextInt()
    val t1 = h1 * 60 + m1
    val t2 = h2 * 60 + m2
    println(maxOf(t2 - t1 - k, 0))
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 34260
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int x,n;
    cin>>x>>n;
    int num[x];

    for(int i=0;i<x;i++){
        num[i]=i+1;
    }

    for(int i=0;i<n;i++){
        int a,b;
        char c;
        cin>>a>>c>>b;
        swap(num[a-1],num[b-1]);
    }

    for(int i=0;i<x;i++){
        cout<<num[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3064
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        int[][] wav = new int[n][2];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                wav[i][j] = scanner.nextInt();
            }
        }
        System.out.println(new Main().f(wav, n, w));
    }

    public long f(int[][] wav, int n, int w) {
        long[][] dp = new long[n][100001];
        for(int i = 0; i < n; i++){
            Arrays.fill(dp[i], 100000000001l);
        }
        for(int i = 0; i < n; i++){
            dp[i][0] = 0;
        }
        dp[0][wav[0][1]] = wav[0][0];
        long ans = wav[0][0] > w ? 0 : wav[0][1];
        for(int i = 1; i < n; i++){
            for(int j = 0; j < 100001; j++){
                if(j >= wav[i][1]){
                    dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-wav[i][1]] + wav[i][0]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
                if(dp[i][j] <= w){
                    ans = Math.max(ans, j);
                }
            }
        }
        return ans;
    }
}


Measured memory_bytes: 126804
N=int(input())
A=list(map(int,input().split(" ")))
print(" ".join(list(map(str,A))))
for i in range(1,N):
    tmp=A[i]
    j=i-1
    while(j>=0 and A[j]>tmp):
        A[j+1]=A[j]
        j-=1
    A[j+1]=tmp
    print(" ".join(list(map(str,A))))


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

int n,q,u,v,rt,num,cnt=0;
int head[500005],cf[200005],pre[200005];

struct edge
{
	int next;
	int to;
}e[500005];

inline void add_edge(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
		if (ch=='-')  w=-w;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch-'0');
		ch=getchar();
	}
	return s*w;
}

inline void dfs(int now,int fath)
{
	pre[now]=pre[fath]+cf[now];
	
	int flag=0;
	for (int i=head[now];i;i=e[i].next)
	{
		if (e[i].to!=fath)
		{
			flag=1;
			dfs(e[i].to,now);
		}
	}
	if (flag==0)  return; 
}

signed main()
{
	cin>>n>>q;
	for (int i=1;i<n;i++)
	{
		u=read(),v=read();
		add_edge(u,v);
		add_edge(v,u);
	}
	for (int i=1;i<=q;i++)
	{
		rt=read(),num=read();
		cf[rt]+=num;
	}
	dfs(1,0);
	
	for (int i=1;i<=n;i++)  cout<<pre[i]<<' ';
	cout<<endl;
	
	return 0;
}

Measured memory_bytes: 20480
# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)

# Tarjan's strongly connected components algorithm(repetition)
import collections

S = collections.deque()
path = collections.deque()
index = 0
indices = [None] * V
lowlink = [None] * V
onStack = [False] * V
scc_id = [None] * V
parent = [0] * V

for v in range(V):
    if not indices[v]:
        index += 1
        indices[v] = index
        lowlink[v] = index
        S.append(v)
        path.append(v)
        onStack[v] = True

        while path:
            s = path[-1]
            adj_v = adj[s]
            for t in adj_v:
                if not indices[t]:
                    parent[t] = s
                    path.append(t)
                    S.append(t)
                    index += 1
                    indices[t] = index
                    lowlink[t] = index
                    onStack[t] = True
                    adj_v.remove(t)
                    break
            if s == path[-1]:
                for t in adj_v:
                    if onStack[t]:
                        lowlink[s] = min(lowlink[s], lowlink[t])
                p = parent[s]
                lowlink[p] = min(lowlink[p], lowlink[s])
                if indices[s] == lowlink[s]:
                    while S:
                        w = S.pop()
                        onStack[w] =False
                        scc_id[w] = s
                        if w == s:
                            break
                path.pop()


# Output
Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    if scc_id[u] == scc_id[v]:
        print(1)
    else:
        print(0)

Measured memory_bytes: 11228
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	int t=0;
	double num;
	int n,m,i,sum=0;
	int arr[10005];
	scanf("%d%d",&n,&m); 
	for(i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
		sum+=arr[i];
	}
	num=(double)sum/4/m;
	for(i=0;i<n;i++)
	{
		if(arr[i]>=num)
		{
			t++;
		}
	}
	if(t>=m)
	printf("Yes\n");
	else
	printf("No\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)
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; }
const int INF = 1000100100;

int main() {
    ll N, D;
    cin >> N >> D;

    vector<vector<ll>> X(N, vector<ll>(D));
    REP(i, N) REP(j, D) cin >> X[i][j];

    vector<ll> sq(42);
    REP(i, sq.size()) {
        sq[i] = i*i;
    }

    ll ans = 0;
    vector<vector<ll>> dt2(N, vector<ll>(N, 0));
    REP(y, N) {
        FOR(z, y + 1, N) {
            REP(i, D) {
                dt2[y][z] += pow(X[y][i] - X[z][i], 2);
            }

            for(ll i = 0; i*i <= dt2[y][z]; ++i) {
                if(dt2[y][z] == i*i) {
                    ++ans;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3608
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s,t;
    cin >> s >> t;
    string a = "", b = "";
    for(int i = 0; i < s.size(); i++){
        if(i%2) a += s[i];
        else b += s[i];
    }
    int j, k;
    j = k = 0;
    for(int i = 0; i < t.size(); i++){
        if(j < a.size() && t[i] == a[j]) j++;
        if(k < b.size() && t[i] == b[k]) k++;
    }
    if(j == a.size() || k == b.size()){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef long double ld;
typedef vector<ll>VI;
typedef pair<ll,ll>P;
#define VV(T) vector<vector<T>>
#define sz(x) int(x.size())
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define reprev(i,n) for (ll i=(ll)n-1;i>=0;i--)
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX6 1001001//6
#define MAX7 10010010//7
#define SENTINEL 2000000000//9
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define CLR(mat) memset(mat, 0, sizeof(mat))
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}
template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}
using Edge=pair<int,ll>;
using Graph=vector<vector<ll> >;//ll or Edge
const int MOD = 1000000007;
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// vector型から重複を削除 list.erase(unique(ALL(list)),list.end());
// g++ -o a a.cpp -Wall -lm -std=c++17
//push_back -> emplace_back

int main(){
   int n;cin>>n;
   VI A(n);rep(i,n)cin>>A[i];
   VI P,M;
   rep(i,n){
      if(A[i]>0)P.emplace_back(A[i]);
      else M.emplace_back(A[i]);
   }
   ll sum=0;
   sort(ALL(P));
   sort(rALL(M));
   if(sz(P)==0){
            sum+=M[0];
            P.emplace_back(M[0]);
            M.erase(M.begin());
         
      for(int i=0;i<sz(M);i++){
         sum-=M[i];
      }
   }
   else if(sz(M)==0){
            sum-=P[0];
            M.emplace_back(P[0]);
            P.erase(P.begin());
      for(int i=0;i<sz(P);i++)sum+=P[i];
   }
   else{
      rep(i,n){
         sum+=llabs(A[i]);
      }
   }
   cout<<sum<<endl;
   int now=M[sz(M)-1];
   M.pop_back();
   rep(i,sz(P)){
      if(i==sz(P)-1){
         cout<<P[i]<<' '<<now<<endl;
         now=P[i]-now;
         break;
      }
      cout<<now<<' '<<P[i]<<endl;
      now=now-P[i];
   }
   rep(i,sz(M)){
      cout<<now<<' '<<M[i]<<endl;
      now-=M[i];
   }
   assert(now==sum);
}

Measured memory_bytes: 5268
def divisorcount(N):#1~Nまでの数の約数の個数
    ans = 0
    divisor = [0]*N
    for i in range(1,N+1):
        ans += (n-1)//i
    return ans

import math
n = int(input())
bf = [0]*int(10**6+1)

N = n - 1

print(divisorcount(N))

Measured memory_bytes: 24460
Scanf.scanf "%d %s" (fun n s ->
    let rec loop i r g b rg rb gb rgb =
        if i = n then rgb else
            match s.[i] with
            | 'R' -> loop (i + 1) (r + 1) g b (rg + g) (rb + b) gb (rgb + gb)
            | 'G' -> loop (i + 1) r (g + 1) b (rg + r) rb (gb + b) (rgb + rb)
            | _   -> loop (i + 1) r g (b + 1) rg (rb + r) (gb + g) (rgb + rg)
    in
    let acc = loop 0 0 0 0 0 0 0 0 in

    let rec loop_i i acc =
        let rec loop_j j acc =
            if j >= n then acc else
                let acc = if s.[i] = s.[j] then acc else
                    let k = j - i + j in
                    if k >= n then acc else
                        if s.[i] <> s.[k] && s.[j] <> s.[k] then acc - 1 else acc
                in
                loop_j (j + 1) acc
        in
        if i = n then acc else loop_i (i + 1) (loop_j (i + 1) acc)
    in
    loop_i 0 acc |> Printf.printf "%d\n"
)

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

using ll = long long;
const ll MOD = 998244353;

int main() {
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    ll asum = 0, bsum = 0;
    rep(i, N) {
        cin >> a[i];
        asum += a[i];
    }
    rep(i, N) {
        cin >> b[i];
        bsum += b[i];
    }
    ll ac = 0, bc = 0;
    rep(i, N) {
        if (a[i] < b[i]) {
            if ((b[i] - a[i]) % 2) {
                ac += (b[i] - a[i] + 1) / 2;
                bc++;
            } else {
                ac += (b[i] - a[i]) / 2;
            }
        }
        if (a[i] > b[i]) bc++;
    }
    //cout << ac << " " << bc << " " << asum << " " << bsum << endl;
    if (bsum - asum < max(ac, bc)) cout << "No\n";
    else cout << "Yes\n";
}

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

using namespace std;

const int MOD = 1e9 + 7;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int data[n];
    for (int i = 0; i < n; ++i) cin >> data[i];
    int suma = 0;
    for (int i = 0; i < n; ++i) suma = (suma + data[i]) % MOD;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        suma -= data[i];
        if (suma < 0) suma += MOD;
        suma %= MOD;
        ans += (suma * data[i]) % MOD;
        ans %= MOD;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 5208
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W = map(int,input().split(' '))
A = -(-W//2)
if W==1 or H==1:
    print(1)
    exit()
if H%2==0:
    print(W*H//2)
else:
    print(W*(H-1)//2+A)

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(), (v).end()
#define sort(v) sort(all(v))
#define rev(x) reverse(all(x))
 
using ld = long double;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
 
const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

int main() {
  int n,m;cin>>n>>m;
  ll xn[n], yn[m];
  rep(i,n) cin>>xn[i];
  rep(j,m) cin>>yn[j];
  ll sx=0,sy=0;
  rep(i,n) {
    sx = (sx + (2*i+1-n) * xn[i]) % MOD;
  }
  rep(j,m) {
    sy = (sy + (2*j+1-m) * yn[j]) % MOD;
  }
  ll s = (sx * sy) % MOD;
  cout << s;
}


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

int main()
{
    string S;
    cin >> S;

    string keyence = "keyence";
    string value;

    rep(i, S.size())
    {
        for (int j = i; j < S.size(); j++)
        {
            if (S.substr(0, i) + S.substr(j, S.size()) == keyence)
            {
                cout << "YES" << endl;
                return 0;
            }
        }
    }

    cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <bits/stdc++.h>
#include <set>
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define vii vector<pair<int, int> >
#define si stack<int>
#define pb push_back
#define mp make_pair
#define ALL(T) (T).begin(), (T).end()
#define MODU 1000000007
typedef long long ll;
using namespace std;

ll intmax = (1LL<<32)-1;
ll llmax = (1LL<<60)-1;

const int INF = 1e9 + 5;

class fastio{
public:
	fastio(){
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
	}
} __fastio;

template <typename T>
T abs(T x){
	if(x<0)	return -x;
	else return x;
}

void DFSVisit(int u, vector<int> g[], vector<bool> &visited){ 
    visited[u] = true;
    for(int i=0; i<g[u].size(); i++){
        if(!visited[g[u][i]]){
            DFSVisit(g[u][i], g, visited); 
        }
    }
} 
  
void DFS(vector<int> adj[], int V){
    vector<bool> visited(V, false); 
    for(int u=0; u<V; u++) 
        if(!visited[u]) 
            DFSVisit(u, adj, visited);
}


void solve(){
	
}

int main(){
	string s;
	vector<int> a(26, 0);
	cin >> s;
	for(char c:s){
		a[c-'A']++;
	}
	bool f1 = false, f2 = false;
	for(int i=0; i<26; i++){
		if(a[i] == 2)
			if(f1 == false)
				f1 = true;
			else
				f2 = true;
	}
	if(f1 && f2)
		cout << "Yes";
	else
		cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    ll h,w,d;
    cin >> h>> w>> d;
    vector<pair<ll, ll> > grid(h*w+1, pair<ll, ll>(0,0));
    ll sum[d][h*w/d+2]={};
    rep(i,h)rep(j,w){
        ll tmp;
        cin >> tmp;
        grid[tmp].first=i;
        grid[tmp].second=j;
    }
    ll q;
    cin >> q;
    ll lr[q][2];
    rep(i,q)cin >> lr[i][0] >> lr[i][1];
    rep(i,d){
        for(ll j=0;i+(j+1)*d<=h*w;j++){
            sum[i][j+1]=sum[i][j]+abs(grid[i+j*d].first-grid[i+(j+1)*d].first)+abs(grid[i+j*d].second-grid[i+(j+1)*d].second);
        }
    }
    rep(i,q){
        DEBUG{
            printf("from : %lld, to : %lld\n",lr[i][0],lr[i][1]);
        }
        cout << sum[lr[i][1]%d][lr[i][1]/d] - sum[lr[i][0]%d][lr[i][0]/d] << endl;
    } 
    return 0;
}


Measured memory_bytes: 5504
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

from collections import deque

def bfs() -> None:
    q = [(0, 0)]
    while q:
        x, y = q.pop(0)
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy  # next x, y
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and dist[nx][ny] == 0:
                q += [(nx, ny)]
                dist[nx][ny] = dist[x][y] + 1


def main():
    global H, W, S, dist, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    dist = [[0] * W for _ in range(H)]  # distance from (0, 0) to (x, y)
    dist[0][0] = 1
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    bfs()
    white, x = sum(s.count(".") for s in S), dist[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
#include <iostream>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

int p[6] = {380,550,850,1520,1870,2244};
int w[6] = {200,300,500,1000,1200,1500};

int dp[5001];

int main(void){
    rep(i,5001) dp[i]=1<<30;
    dp[0]=0;
    rep(i,6){
        loop(j,w[i],5001){
            dp[j]=min(dp[j-w[i]]+p[i],dp[j]);
        }
    }
    int W;
    while(cin>>W,W){
        cout<<dp[W]<<endl;
    }
}

Measured memory_bytes: 1180
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
//const ll mod = 1000000007LL;
const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222


ll a[MAX], memo[3333][3333];

ll dfs(ll le, ll ri) {
  ll cur = n - (ri - le);
  cur %= 2;
  if (le == ri) return cur ? a[le] : 0;
  if (memo[le][ri]) return memo[le][ri];
  if (cur) return memo[le][ri] = max(dfs(le + 1, ri) + a[le], dfs(le, ri - 1) + a[ri]);
  else return memo[le][ri] = min(dfs(le + 1, ri), dfs(le, ri - 1));
}


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


  cin >> n;
  rep(i, n) cin >> a[i];
  ll sum = accumulate(a, a + n, 0LL);
  cout << 2 * dfs(0, n - 1) - sum << endl;



  return 0;
}

Measured memory_bytes: 82304
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    x,k,d = LI()
    if x == 0:
        if k % 2 == 1:
            print(d)
        else:
            print(0)
        return
    else:
        s = abs(x) // x
    c = abs(x) // d

    ans = 0
    if c >= k:
        ans = x - d * k * s
    else:
        ans = x - d * c * s
        if (k-c) % 2 == 1:
            ans = ans - d * s
    print(abs(ans))
if __name__ == '__main__':
    main()

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) 
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (ll i=(ll)(a);i<(ll)(b);++i)
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)
#define YES(cond) cond ? OUT("YES") : OUT("NO")
#define Yes(cond) cond ? OUT("Yes") : OUT("No")

template<class T> T gcd(const T x,const T y){if(!y){return x;}return gcd(y,x%y);}
template<class T> T lcm(const T x,const T y){return x/gcd(x,y)*y;};
template<class T> T modpow(const T x,const T n,const T mod) {
  T res=1;while(n>0){if(n%2)res=res*x%mod;x=x*x%mod;n/=2;};return res;
}
template<class T> bool alltrue(const T &a){return all_of(ALL(a),[](bool x){return x;});}
template<class T> bool anytrue(const T &a){return any_of(ALL(a),[](bool x){return x;});}
template<class T> bool contain(const T &a,const T &b){for(auto x:b){if (a.find(x)==a.end()){return false;}}return true;}
template<class T> bool mmax(T &m,const T q){ if (m < q) {m = q; return true;} else return false; }
template<class T> bool mmin(T &m,const T q){ if (m > q) {m = q; return true;} else return false; }
template<class T> int siz(const T &a) {return (int)a.size();}
template<class T> set<T> devisers(T n) {
  set<T> res;for(T i=1;i<(T)sqrt(n)+1;i++){if(n%i==0){res.insert(i);res.insert(n/i);}}return res;
}
template<class T> void concat(T &a, const T &b){a.insert(a.end(),b.begin(),b.end());}
template<class T> void getand(const T &a,const T &b,T &c) {
  set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}
template<class T> void getor(const T &a,const T &b,T &c) {
  set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}

typedef long long ll;
typedef pair<ll, ll> P;

const int MOD=1e9+7;
const int MAX=1e5+100;

vector<ll> dijkstra(int V, int s, vector<vector<int>> &G) {
  vector<ll> d(V,LLONG_MAX);d[s]=0;
  priority_queue<P,vector<P>,greater<P>> q;q.push({0,s});
  while (!q.empty()) {
    P p = q.top();q.pop();
    int v = p.second;
    if (d[v]<p.first) continue;
    for (int nv:G[v]) {
      if (d[nv]>d[v]+1) {
        d[nv] = d[v]+1;
        q.push({d[nv],nv});
      }
    }
  }
  return d;
}

int main() {
  int N,M;cin>>N>>M;
  vector<vector<int>> G(N*3);
  REP(i,M) {
    int u,v;cin>>u>>v;
    u--;v--;
    REP(j,3) G[u*3+j].push_back(v*3+(j+1)%3);
  }
  int S,T;cin>>S>>T;
  S--;T--;
  vector<ll> ans = dijkstra(3*N,3*S,G);
  (ans[T*3]==LLONG_MAX) ? OUT(-1) : OUT(ans[T*3]/3);

  return 0;
}

Measured memory_bytes: 18944