akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = input()
N = len(S)
A = [0]*(N+1)

i = 0
ind = 0
flag = 0
if S[0] == '>':
    while S[ind] == '>':
        ind += 1
        if ind >= N:
            flag = 1
            break
    num = ind
    for i in range(ind+1):
        A[i] = num
        num -= 1
i = ind

if flag:
    print(sum(A))
    exit()
if S.count('<') == N:
    print(N*(N+1)//2)
    exit()
if S == '><' or (len(S) == ind+1 and S[i-1:i+1] == '><'):
    print(2)
    exit()
while True:
    if S[i] == '<' and S[i+1] == '>':
        cnt = 0
        while True:
            cnt += 1
            if i+1+cnt > N-1 or S[i+1+cnt] == '<':
                break
        #print(i, cnt)
        if i+1-ind >= cnt+1:
            num = 1
            for j in range(ind+1, i+2):
                A[j] = num
                num += 1
            num = 0
            for j in reversed(range(i+2, i+cnt+2)):
                A[j] = num
                num += 1
        else:
            num = 1
            for j in range(ind+1, i+1):
                A[j] = num
                num += 1
            num = 0
            for j in reversed(range(i+1, i+cnt+2)):
                A[j] = num
                num += 1
        ind = i+cnt+1
        i += cnt
        #print(A)
    else:
        A[i+1] = A[i] + 1
    i += 1
    if i >= N-1:
        if i == N-1:
            A[i+1] = A[i] + 1
        break

#print(A)
print(sum(A))

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

int n,a[50];

bool solve(int i,int m) {
    if(m==0) return true;
    if(i>=n) return false;
    bool res=solve(i+1,m) || solve(i+1,m-a[i]);
    return res;
}

int main() {
    int q,m,i;
    cin>>n;
    for(i=0;i<n;i++) cin>>a[i];
    cin>>q;
    for(i=0;i<q;i++) {
        cin>>m;
        if(solve(0,m)) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define qi queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define prq priority_queue
#define foreach(it,c) for(__typeof((c).begin()) it=c.begin();it!=c.end();it++)
//#define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? 1:0)
using namespace std;
inline ll read(){
	ll 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');
	return x*f;
}
inline void out(int x){
	if(x>=10)out(x/10);
	putchar(x%10+'0');
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int a;
	cin>>a;
	if(a<30) cout<<"No\n";
	else cout<<"Yes\n";
	return 0;
}

Measured memory_bytes: 3612
n,q=map(int,input().split())
s=input()
t=[0]*len(s)
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        t[i+1]=t[i]+1
    else:
        t[i+1]=t[i]+0
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])

Measured memory_bytes: 7748
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def solve():
    s = input()
    if s == "ABC":
        print("ARC")
    else:
        print("ABC")

    return 0

if __name__ == "__main__":# {{{
    solve()

# vim: set foldmethod=marker: }}}


Measured memory_bytes: 79420
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
    int n;
    int ans = 0;
    cin >> n;

    for(int i=1;i<=n;i++){
        if(i%2==1){
            int jed = 0;
            for(int j=1;j<=i;j++){
                if(i%j==0){
                    jed++;
                }
            }
            if(jed == 8){
                ans++;
            }
        }
    }

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

    return 0;
}

Measured memory_bytes: 380
n = gets.to_i
a = gets.split.map(&:to_i).sort.reverse
e = []
i = 0
tmp = 0
while true
  break if i == a.size || e.size == 2
  if tmp == a[i]
      e << tmp if tmp == a[i]
      tmp = 0
  else
    tmp = a[i]
  end
  i += 1
end

res = 0
res = e[0] * e[1] if e.size == 2
p res


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

int main()
{
	int a[34] = {0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k;
	cin >> k;
	cout << a[k] << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) (((long long)mod_x)%modulo)

//aのb乗
int beki(int a,int b){
	int x = 1;
	while(b!=0){
		if(b&1){
			x=mod(x*a);
		}
		a=mod(a*a);
		b>>=1;
	}
	return x;
}

//aの逆元
int gyakugen(int a){
	return beki(a,modulo-2);
}

struct combi{
	deque<int> kaijou;
	deque<int> kaijou_;
	
	void kaijou_set(int n){
		kaijou.push_back(1);
		for(int i=1;i<=n;i++){
			kaijou.push_back(mod(kaijou[i-1]*i));
		}
		
		int b=gyakugen(kaijou[n]);
		
		/*
		int a = kaijou[n];int b = 1;int m = modulo-2;
		while(m!=0){
			if(m%2){
				b=mod(b*a);
			}
			a=mod(a*a);
			m/=2;
		}
		*/
		kaijou_.push_front(b);
		for(int i=1;i<=n;i++){
			int k=n+1-i;
			kaijou_.push_front(mod(kaijou_[0]*k));
		}
	}
	
	int combination(int n,int r){
		if(r>n)return 0;
		int a = mod(kaijou[n]*kaijou_[r]);
		a=mod(a*kaijou_[n-r]);
		return a;
	}
	
	int junretsu(int a,int b){
		int x = mod(kaijou_[a]*kaijou_[b]);
		x=mod(x*kaijou[a+b]);
		return x;
	}
	
};

int main(){
	
	int N,A,B,C;
	cin>>N>>A>>B>>C;
	
	combi c;
	c.kaijou_set(N*2);
	int ans = 0;
	
	int aa = mod(beki(A,N)*beki(gyakugen(A+B),N));
	int bb = mod(beki(B,N)*beki(gyakugen(A+B),N));
	
	int AA = 1;
	int BB = 1;
	
	for(int i=0;i<N;i++){
		int x = 1;
		x=mod(x*(N+i));
		x=mod(x*c.combination((N+i-1),i));
		int y = mod(mod(aa*BB)+mod(bb*AA));
		x=mod(x*y);
		ans=mod(ans+x);
		AA=mod(AA*A);
		AA=mod(AA*gyakugen(A+B));
		BB=mod(BB*B);
		BB=mod(BB*gyakugen(A+B));
	}
	//cout<<ans<<endl;
	ans=mod(ans*100);
	ans=mod(ans*gyakugen(A+B));
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  int sum=0;

   cin>>s;
   int i=0;
  
   for(int i=0;i<s.size();i++)
  {
    int d=s[i]-'0';
    sum+=d;
  }
   if(sum%9==0)
   {
        cout<<"Yes"<<endl;

   }
   else
    cout<<"No"<<endl;



   }


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

vector<int> AA[100000];

int tree(int a){
    int ans,i;
    vector<int> tmp;
    for(i=0;i<AA[a].size();i++){
        tmp.push_back(tree(AA[a][i]-1));
    }
    sort(tmp.begin(),tmp.end());
    ans=0;
    for(i=0;i<tmp.size();i++){
        ans=max(ans,tmp[i])+1;
    }
    return ans;
}

int main(void){
    int i,j,N,a,ans;
    cin >> N;
    for(i=2;i<=N;i++){
        cin >> a;
        AA[a-1].push_back(i);
    }
    cout << tree(0) << endl;;
    return 0;
}

Measured memory_bytes: 13568
import           Control.Monad

main :: IO ()
main = do
  [n, d] <- map read . words <$> getLine
  points <- map (map read . words) <$> replicateM n getLine :: IO [[Integer]]
  print $ length $ filter id $ map
    (\[x, y] -> x ^ 2 + y ^ 2 <= (fromIntegral d) ^ 2)
    points


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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
bool chmin(T &a,T b){if(a>b){a=b;return true;}else return false;}
template<typename T>
bool chmax(T &a,T b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,k;cin>>n>>k;
  vector<ll>h(n);
  rep(i,0,n)cin>>h[i];
  rep(i,0,n)res+=h[i]>=k;
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <string>

std::string w;
std::string t;

int main()
{
	std::getline(std::cin, w);

	std::string line;
	while (std::getline(std::cin, line))
	{
		t += line;
    	t += " ";
	}

	t = " " + t;
	w = " " + w + " ";
	for (int i = 0; i < t.length(); i++)
	{
		t[i] = tolower(t[i]);
	}

	int count = 0;
	int i = 0;
	while (true)
	{
		t = t.substr(i);
		int index = t.find(w);
		if (index >= 0)
		{
			count++;
			i = index + 1;
		}
		else
		{
			break;
		}
	}
	std::cout << count << std::endl;
}


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

int main(){
  int n,y;
  cin>>n>>y;
  for(int i=0;i<=n;i++){
    for(int j=0;i+j<=n;j++){
      if(10000*i+5000*j+1000*(n-i-j)==y){
        cout<<i<<" "<<j<<" "<<n-i-j<<endl;
        return 0;
      }
    }
  }
  cout<<"-1 -1 -1"<<endl;
}
        


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

int main() {
  int N;
  cin >> N;
  if (N < 10){
    cout << N << endl;
  }
  else if (N < 100){
    cout << 9 << endl;
  }
  else if (N < 1000){
    cout << 9 + (N - 99) << endl;
  }
  else if (N < 10000){
    cout << 909 << endl;
  }
  else if (N < 100000){
    cout << 909 + (N - 9999) << endl;
  }
  else{
    cout << 90909 << endl;
  }
}


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

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

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll solve(ll N)
{
    ll ans = N + 1;

    for (ll d = 1; d * d <= N; ++d)
    {
        if (N % d == 0)
        {
            auto k = N / d;
            ans = min(ans, (d - 1) + (k - 1));
        }
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;

    auto ans = solve(N);

    cout << ans << '\n';

    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007

class BIT{
  public:
  vector<vector<ll>> s;
  const int n;
  BIT(int N) : s(N+1,vector<ll>(26,0)),n(N){}
  vector<ll> sum(int i){
    vector<ll> res(26,0);
    while(i){
      rep(j,26)res[j] += s[i][j];
      i -= i & -i;
    }
    return res;
  }
  vector<ll> sum(int l,int r){
    vector<ll> res(26,0);
    vector<ll> sl = sum(l-1),sr = sum(r);
    rep(i,26)res[i] = sr[i]-sl[i];
    return res;
  }
  void add(int pos,char c,bool is){
    if(is){
      while(pos <= n){
        s[pos][c-'a']++;
        pos += pos &  -pos;
      }
    }else{
      while(pos <= n){
        s[pos][c-'a']--;
        pos += pos &  -pos;
      }
    }
  }
};

int main(){

  int n,Q;
  string s;
  cin >> n >> s >> Q;
  BIT bit(n);
  rep(i,n)bit.add(i+1,s[i],true);
  while(Q--){
    int q;cin >> q;
    if(q == 1){
      int pos;char c;cin >> pos >> c;
      bit.add(pos,c,true);
      bit.add(pos,s[pos-1],false);
      s[pos-1] = c;
    }else{
      int l,r;cin >> l >> r;
      vector<ll> k = bit.sum(l,r);
      ll res = 0;
      rep(i,26)res += k[i] > 0;
      cout << res << endl;
    }
  }

  


  return 0;
}

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

int main() {
  int N, M, X, Y;
  cin >> N >> M >> X >> Y;
  int x[N];
  for (int i = 0; i < N; i++) {
    cin >> x[i];
  }

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

  sort(x, x + N);
  sort(y, y + M);

  if (x[N-1] < y[0] && x[N -1] < Y && X < y[0]) {
    cout << "No War" << endl;
  } else {
    cout << "War" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import itertools
bit_base = 2#bit_base^nの全探査になる. 
def Base_10_to_n(X, n):#10進数をbit_base進数に変換
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

def main():
  H, W, K = map(int, input().split())
  C = []
  for i in range(H):
    C.append(str(input()))
  num_b = 0
  for i in range(H):
    for j in range(W):
      if C[i][j] == "#":
        num_b += 1
  ans = 0
  for i in range(bit_base**(H+W)):
    s = Base_10_to_n(i, bit_base)
    s = s.zfill(H+W)
    flag_h = []
    flag_w = []
    for num, j in enumerate(s):
      if j == '1':
        if num < H:
          flag_h.append(num)
        else:
          flag_w.append(num-H)
    temp = num_b
    for i in flag_h:
      for j in range(W):
        if C[i][j] == "#":
          temp -= 1
    for j in flag_w:
      for i in range(H):
        if C[i][j] == "#":
          temp -= 1
    for i, j in itertools.product(flag_h, flag_w):
      if C[i][j] == "#":
        temp += 1
    if temp  == K:
      ans += 1
  print(ans)
    
if __name__ == "__main__":
  main()

Measured memory_bytes: 9284
#include<bits/stdc++.h>
using namespace std;
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define ll long long
#define mod 998244353 
#define pb push_back
#define mb make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main(){
	IOS;
	ll n ; cin >> n;
	pair<ll,ll> dp[n+1][n+1];
	for(ll i=0;i<=n;i++)
		for(ll j=0;j<=n;j++)
			dp[i][j].first= 0, dp[i][j].second = 0;

	ll arr[n+1];
	for(ll i=1;i<=n;i++) 	cin >> arr[i];
	for(ll i=1;i<=n;i++)
		dp[i][i].first = arr[i];


	for(ll l =2 ; l<=n ; l++){
		for(ll left = 1 ; left <= n-l+1 ; left++){
			ll right = left+l-1;
			// cout << left << " " << right << endl;	
			if(arr[left]+dp[left+1][right].second > arr[right]+dp[left][right-1].second){
				dp[left][right].first = arr[left]+dp[left+1][right].second;
				dp[left][right].second = dp[left+1][right].first;
			}
			else{
				dp[left][right].first = arr[right]+dp[left][right-1].second;
				dp[left][right].second = dp[left][right-1].first;
			}


			// dp[left][right].first = max(arr[left]+dp[left+1][right].second,arr[right]+dp[left][right-1].second);
			// dp[left][right].second = min(arr[left]+dp[left+1][right].second,arr[right]+dp[left][right-1].second);
		}
	}
	// for(ll i=1;i<=n;i++){
	// 	for(ll j=1;j<=n;j++)
	// 		cout << dp[i][j].first << "," << dp[i][j].second << " ";
	// 	cout << endl;
	// }
	cout << dp[1][n].first - dp[1][n].second << endl;


	return 0;
}




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

const int N = 8;
int n, m;
bool g[N][N];

int dfs(int v, int n, bool visited[]) {
  bool all_visited = true;
  for (int i = 0; i < n; i ++) {
    if (visited[i] == false) all_visited = false;
  }

  if (all_visited) return 1;

  int res = 0;
  for (int i = 0; i < n; i ++) {
    if (visited[i]) continue;
    if (g[v][i] == false) continue;

    visited[i] = true;
    res += dfs(i, n, visited);
    visited[i] = false;
  }

  return res;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i ++) {
    int x, y;
    cin >> x >> y;
    x --, y --;
    g[x][y] = g[y][x] = true;
  }

  bool visited[N];
  for (int i = 0; i < N; i ++) visited[i] = false;
  visited[0] = true;

  cout << dfs(0, n, visited) << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int num = 0;
    rep(i,s.size()){
        num += (s[i] - '0');
        num %= 9;
    }
    if(num == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3764
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>

#pragma warning( disable: 4996 )

using namespace std;

typedef long long ll;

#define INF 100000000
#define EPS 1e-9

#define MAX_N 50
#define MAX_R 50

#define MAX_W 20
#define MAX_H 20

int W, H;
int ans;
char maze[MAX_W][MAX_H];

void dfs(int sx, int sy){
	
	maze[sy][sx] = '#';

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

	for (int i = 0; i < 4; i++){
		int nx = sx + dx[i];
		int ny = sy + dy[i];
		if (nx >= 0 && nx < W && ny >= 0 && ny < H && maze[ny][nx] != '#'){
			ans++;
			dfs(nx, ny);
		}
	}

}

int main(){

	while (true){
		cin >> W >> H;
		if (W == 0 && H == 0){
			break;
		}
		int sx;
		int sy;
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				cin >> maze[i][j];
				if (maze[i][j] == '@'){
					sx = j;
					sy = i;
				}
			}
		}

		ans = 1;
		dfs(sx,sy);
		cout << ans << endl;

	}


	return 0;

}

Measured memory_bytes: 1180
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include<cmath>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int N,K,Q;
    cin >> N >> K >> Q;
    
    int A[100001];
    rep(i,Q){
        cin >> A[i];
    }
    
    int B[100001];
    rep(i,N){
        B[i] = K;
    }
    
    int M = max(N,Q);
    rep(i,M){
        B[i]-=Q;
        B[A[i] - 1]++;
    }
    
    rep(i,N){
        if(B[i] > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}


Measured memory_bytes: 1408
import numpy as np
import sys

input = sys.stdin.readline

s = int(input())

if s == 1 :
    n = 2
elif s == 2:
    n = 1
else:
    n = 3

ans = 1

while s != 4:
    if s%2 == 0 :
        s = s/2
    else:
        s = 3*s + 1
    
    
    ans+=1


print(ans+n)


Measured memory_bytes: 14420
#include <iostream>
using namespace std;
void ABC60(void);
void ABC61(void);
void ABC62(void);
void ABC63(void);
void ABC64(void);
void ABC65(void);
void ABC66(void);
void ABC67(void);
void ABC68(void);
void ABC69(void);

int main(void){
    ABC64();
}

void ABC64(void){
    int n,a,b,c;
    cin>>a>>b>>c;
    n=a*100+b*10+c;
    if(n%4==0)cout<<"YES";
    else cout<<"NO";
}

Measured memory_bytes: 256
#include <math.h>
#include <stdio.h>
#include <string.h>
void swap_int(int* x, int* y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
void swap_char(char* x, char* y) {
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void asc_sort(int* array, int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (array[i] > array[j]) {
                swap_int(&array[i], &array[j]);
            }
        }
    }
}

void dec_sort(int* array, int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (array[i] < array[j]) {
                swap_int(&array[i], &array[j]);
            }
        }
    }
}

int max(int x, int y) {
    if (x > y) {
        return x;
    } else {
        return y;
    }
}

int min(int x, int y) {
    if (x > y) {
        return y;
    } else {
        return x;
    }
}
int main(void) {
    char str[100];
    int length;
    int t, f;
    int i, j, k;
    t = f = 0;

    scanf("%s", str);
    length = strlen(str);

    for (i = 0; str[i] != '\0'; i++) {
        if (str[i] == 'o') {
            t++;
        } else {
            f++;
        }
    }

    if (f < 8) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return 0;
}

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

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

	int n;
	long long int d,a;
	vector <pair<long long int,long long int>> v;
	long long int x,y;
	long long int res = 0;
	priority_queue <pair<long long int,long long int>,vector<pair<long long int,long long int>>,greater<pair<long long int,long long int>>> pque;
	long long int damage = 0;

	cin >> n >> d >> a;

	for(int i=0;i<n;i++)
	{
		cin >> x >> y;
		v.push_back(make_pair(x,y));
	}

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

	for(int i=0;i<n;i++)
	{
		while(!pque.empty())
		{
			if(pque.top().first >= v[i].first)
			{
				break;
			}
			damage -= pque.top().second;
			pque.pop();
		}

		long long int H = (v[i].second - damage);
		if(H>0)
		{
			long long int num = ceil((H*1.0)/a);
			res += num;
			//cout << num << '\n';
			pque.push(make_pair(v[i].first + 2*d,num*a));
			damage += (num*a);
		}
	}

	cout << res << '\n';

	return 0;
}

Measured memory_bytes: 7020
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    ll n;
    cin >> n;
    vll mem(10010);
    REP(x, 101) {
        REP(y, 101) {
            REP(z, 101) {
                ll v = x * x + y * y + z * z + x * y + y * z + z * x;
                if (x * y * z >= 1 && v <= n) mem[v]++;
            }
        }
    }
    REP(i, n) {
        cout << mem[i + 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 3692
def checkWays(n,x)
  count = 0
  catch(:stop) do
    n.downto(1) do |n1|
      (n1-1).downto(1) do |n2|
        n3 = x - n1 - n2
        count += 1 if (n3 < n2) && (n3 > 0)
        throw :stop if (n3 > n1)
        break if (n3 > n2)
      end
    end
  end
  puts count
end

while ((n,x = gets.split(" ").map(&:to_i)).inject(:+) != 0) do
  checkWays(n,x)
end

Measured memory_bytes: 8592
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e3 + 5;
const int maxm = 2e5 + 5;
const int inf = 1e9;
const int mod = 1e9 + 7;
vector<int> adj[maxn];
int id[maxn][maxn];
bool vis[maxn][maxn];
bool vis1[maxn];
int a[maxm],b[maxm];
bool res[maxm];
int n , m;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        cin >> a[i] >> b[i];
        adj[a[i]].pb(i);
    }
    for(int i = 1 ; i <= n ; ++i){
        queue<int> q;
        q.push(i);vis[i][i] = 1;
        while(q.size()){
            auto u = q.front();q.pop();
            for(auto &c : adj[u]){
                if(vis[i][b[c]] == 0){
                    vis[i][b[c]] = 1;q.push(b[c]);
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        memset(vis1,0,sizeof vis1);
        vis1[i] = 1;
        for(auto &c : adj[i]){
            if(vis1[b[c]]){
                res[c] = 1;
                continue;
            }
            queue<int> q;q.push(b[c]);vis1[b[c]] = 1;
            while(q.size()){
                auto u = q.front();q.pop();
                for(auto &c : adj[u]){
                    if(vis1[b[c]] == 0){
                        vis1[b[c]] = 1;q.push(b[c]);
                    }
                }
            }
        }
        reverse(adj[i].begin(),adj[i].end());
        memset(vis1,0,sizeof vis1);
        vis1[i] = 1;
        for(auto &c : adj[i]){
            if(vis1[b[c]]){
                res[c] = 1;
                continue;
            }
            queue<int> q;q.push(b[c]);vis1[b[c]] = 1;
            while(q.size()){
                auto u = q.front();q.pop();
                for(auto &c : adj[u]){
                    if(vis1[b[c]] == 0){
                        vis1[b[c]] = 1;q.push(b[c]);
                    }
                }
            }
        }
    }
    for(int i = 1 ; i <= m ; ++i){
//        cout << vis[b[i]][a[i]] << " " << res[i] << " ";
        if(vis[b[i]][a[i]] == res[i])cout << "same\n";
        else cout << "diff\n";
    }
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define sz size()
#define mp make_pair
#define p(x) cout<< x << " ";
#define pe(x) cout<< x << endl ;
#define deb(x) cout<<#x<<" : "<<x<<endl;
#define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define el endl
#define MOD 1000000007 
#define int long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROR(i,a,b) for(int i=a;i>=b;i--)
const int N = 4e5 + 5;


int32_t main() 
{ 
    FAST;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int pp=b/c;
    int qq=(a-1)/c;
    int xx=b/d;
    int yy=(a-1)/d;
    int lcm=(c*d)/(__gcd(c,d));
    int hh=b/lcm;
    int mm=(a-1)/lcm;
    pp=pp-qq;
    xx=xx-yy;
    hh=hh-mm;
    int ans=pp+xx-hh;
    ans=(b-a+1)-ans;
    cout<<ans;
}

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




void solve(long long X, long long K, long long D){
    ll ans = 0;
    if( log10(abs(K))+log10(abs(D)) > 16 or K*D > abs(X) ){
        if( ((K-abs(X)/D)&1) == 1 )
            ans = X - (X/D+1)*D;
        else
            ans = X - (X/D)*D;

    }
    else{
        ans =  abs(X) - abs(K) * abs(D) ;
    }
    cout << abs(ans) << endl;
}

void solve2(long long X, long long K, long long D){
    ll ans = 0;
    if( log10(abs(K))+log10(abs(D)) > 16 or K*D > abs(X) ){
        if( ((K-abs(X)/D)&1) == 1 )
            if( X >= 0 ) 
                ans = X - (X/D+1)*D;
            else
                ans = X + (abs(X)/D+1)*D;
        else
            if( X >= 0 ) 
                ans = X - (X/D)*D;
            else
                ans = X + (abs(X)/D)*D;
    }
    else{
        ans =  abs(X) - abs(K) * abs(D) ;
    }
    cout << abs(ans) << endl;
}


signed main(){
    long long X;
    scanf("%lld",&X);
    long long K;
    scanf("%lld",&K);
    long long D;
    scanf("%lld",&D);
    solve2(X, K, D);
    return 0;
}


Measured memory_bytes: 3984
#include <cstdio>

#define N 100000

typedef long long i64;

int n, m, p;
int a[N + 9];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
	}
	for (int i = 1; i < n; ++i)
		if (a[i] + a[i + 1] >= m) {
			p = i;
			break;
		}
	if (p) {
		puts("Possible");
		for (int i = 1; i < p; ++i) printf("%d\n", i);
		for (int i = n - 1; i >= p; --i) printf("%d\n", i);
	} else {
		puts("Impossible");
	}
	return 0;
}


Measured memory_bytes: 1152
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

using ll = long long;

// 処理内容
int main() {

    ll k; scanf("%lld", &k);
    ll dp[100000];
    for (ll i = 0; i < k; i++) dp[i] = 0x7FFFFFFFFFFFFFFFLL;
    dp[1] = 1;

    // deque
    ll qv[100000] = {1};
    ll qc[100000] = {1};
    ll qbeg = 0, qend = 1;

    while (qbeg != qend) {

        ll c = qc[qbeg];
        ll v = qv[qbeg];
        qbeg++; if (qbeg == k) qbeg = 0; // pop_front

        ll n1 = -~v; if (n1 == k) n1 = 0;
        ll n2 = v * 10; while (n2 >= k) n2 -= k;
        ll temp;
        if (dp[n1] > (temp = -~dp[v])) {
            dp[n1] = temp;
            // push_back
            qv[qend] = n1;
            qc[qend] = temp;
            qend++; if (qend == k) qend = 0;
        }
        if (dp[n2] > (temp = dp[v])) {
            dp[n2] = temp;
            // push_front
            qbeg--; if (qbeg == -1) qbeg = ~-k;
            qv[qbeg] = n2;
            qc[qbeg] = temp;
        }
        
    }

    printf("%lld", dp[0]);
    
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(input.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int t = Integer.parseInt(tokenizer.nextToken());
        int minCost = 1000011;
        int c1, t1;
        for (int i = 0; i < n; i++) {
            tokenizer = new StringTokenizer(input.readLine());
            c1 = Integer.parseInt(tokenizer.nextToken());
            t1 = Integer.parseInt(tokenizer.nextToken());
            if (t1 <= t)
                minCost = Math.min(minCost, c1);
        }
        System.out.println(minCost== 1000011? "TLE" : minCost);
    }
}


Measured memory_bytes: 22864
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <map>
#include <set>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

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

    REP(i,26){
        REP(j,14){
            int ans=0;
            ans = 4*i+7*j;
            if(ans==n){
                cout << "Yes" << endl;
                exit(0);
            }
        }
    }

    cout << "No" << endl;

    return 0;
}

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

#define rep(i, n) for(int (i) = 0; i < (n); ++(i))

using ll = long long int;
const ll MOD = 1e9 + 7;

template<long long int P>
struct _mint {
  long long int x;
  _mint(long long int x = 0): x((x % P + P) % P) {}

  _mint operator-() const {
    return _mint(-x);
  }

  _mint& operator+=(const _mint a) {
    if((x += a.x) >= P) {
      x -= P;
    }
    return *this;
  }
  _mint& operator-=(const _mint a) {
    if((x += P - a.x) >= P) {
      x -= P;
    }
    return *this;
  }
  _mint& operator*=(const _mint a) {
    (x *= a.x) %= P;
    return *this;
  }
  _mint& operator/=(const _mint a) {
    return (*this) *= a.inv();
  }

  _mint operator+(const _mint a) const {
    _mint res(*this);
    return res += a;
  }
  _mint operator-(const _mint a) const {
    _mint res(*this);
    return res -= a;
  }
  _mint operator*(const _mint a) const {
    _mint res(*this);
    return res *= a;
  }
  _mint operator/(const _mint a) {
    _mint res(*this);
    return res /= a;
  }

  _mint pow(long long int t) const {
    if(! t) return 1;
    _mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }

  // for prime P
  _mint inv() const {
    return pow(P - 2);
  }
};
using mint = _mint<MOD>;

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

  mint ans = mint(2).pow(n) - 1;

  auto comb = [&](ll N, ll k) {
    mint ret = 1;
    rep(i, k) {
      ret *= (N - i);
    }
    rep(i, k) {
      ret /= (k - i);
    }

    return ret;
  };

  ans -= comb(n, a) + comb(n, b);
  std::cout << ans.x << '\n';
}


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

int main(void){
	int h1, h2, k1, k2, a, b, c, d, resh, resk;
	cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;

	resh = (h1*a)+(h2*b)+(h1/10*c)+(h2/20*d);
	resk = (k1*a)+(k2*b)+(k1/10*c)+(k2/20*d);

	if(resh > resk) cout << "hiroshi";
	else if(resh < resk) cout << "kenjiro";
	else cout << "even";
	cout << endl;
}


Measured memory_bytes: 3132
#include <iostream>
#include <string>

int main() {
    int h,w;
    std::cin >> h >> w;
    std::string s[50];
    
    for(int i = 0; i < h; i++) std::cin >> s[i];

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

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] == '#') continue;
            int num = 0;
            for(int k = 0; k < 8; k++){
                if(i + dy[k] < 0 || i + dy[k] >= h || j + dx[k] < 0 || j + dx[k] >= w)continue;
                else if(s[i + dy[k]][j + dx[k]] == '#') num++;
            }
            s[i][j] = (char)(num + '0');
        }
    }
    for(int i = 0; i < h; i++) std::cout << s[i] << std::endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int pa, pb, pc, ja, jb,p=0,j=0;
	cin >> pa >> pb >> pc >> ja >> jb;
	{if (pa < pb)
	{
		if (pa < pc)
		{
			p=pa;
		}
		else
		{
			p = pc;
		}
	}

	else
	{
		if (pb < pc)
		{
			p = pb;
		}
		else
		{
			p = pc;
		}
	}
	}
	{
		if (ja > jb)
		{
			j = jb;
		}
		else
		{
			j = ja;
		}
	}
	cout << p+j-50 << endl;
	
	return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    int L = -1, R = 1e6;
    REP(i, m) {
        int l, r;
        scanf("%d%d",&l,&r);
        L = max(l, L);
        R = min(r, R);
    }
    int ans = max(0, R - L + 1);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
const int MOD = 1000000007;
int main() {
    ll x;
    cin>>x;
    ll cnt=0,money=100;
    while(money<x){
        money*=1.01;
        cnt++;
    }
    cout<<cnt<<endl;
}


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

int main() {
    int N,K;
    cin >> N >> K;
    vector<ll> vec(N);
    for(int i = 0; i < N; i++){
        cin >> vec.at(i);
    }

    sort(vec.begin(),vec.end());
    ll ans = 1000000000;
    for(int i = 0; i < N - K + 1; i++){
        ll H = vec.at(i+K-1) - vec.at(i);
        ans = min(ans, H);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4028
<?php
    $a = str_split(trim(fgets(STDIN)));
    $b = str_split(trim(fgets(STDIN)));
    $c = str_split(trim(fgets(STDIN)));
    $p = "a";
    while(true){
        if(count($$p)==0){
            echo strtoupper($p),"\n";
            exit;
        }
        $p = array_shift($$p);
    }


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

int main()
{
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    for (auto &a : A) cin >> a;
    for (auto &b : B) cin >> b;
    for (auto &c : C) cin >> c;
    sort(A.begin(), A.end());
    sort(C.begin(), C.end());
    long long ans = 0;
    for (auto b : B)
    {
        ans += distance(A.begin(), lower_bound(A.begin(), A.end(), b)) * distance(upper_bound(C.begin(), C.end(), b), C.end());
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1408
# 約数のリストを表示する(因数分解ではない)
# make_divisors(16)
# [1, 16, 2, 8, 4]
def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    # divisors.sort()
    return divisors

# 約数のリストを表示する(1とその数を除く)
# make_divisors_without_own(16)
# [2, 8, 4]
def make_divisors_without_own(n):
    r = make_divisors(n)
    r.remove(1)
    r.remove(n)
    return r
n = int(input())

r = make_divisors_without_own(n)
r.sort()
if len(r) == 0:
    print(n - 1)
else:
    a = r[len(r) // 2]
    b = n // a
    print(a - 1 + b - 1)


Measured memory_bytes: 3296
#include<bits/stdc++.h>
#define INF (1e15)
#define N 100005
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,m,r,q,a,b,c,x,y,z;
vector<P> G[N];
priority_queue<P,vector<P>,greater<P> > Q;
ll d[10][N];

void dijkstra(int M){
  while(!Q.empty()){
    P t=Q.top(); Q.pop();
    ll cost=t.first,node=t.second;
    if(d[M][node]<cost)continue;
    for(int i=0;i<G[node].size();i++){
      ll nnode=G[node][i].first;
      ll ncost=cost+G[node][i].second;
      if(d[M][nnode]>ncost){
	d[M][nnode]=ncost;
	Q.push(P(ncost,nnode));
      }
    }
  }
}

int main(){
  cin>>n>>m>>r>>q;
  for(int i=0;i<m;i++){
    cin>>a>>b>>c;
    G[b-1].push_back(P(a-1,c));
  }
  for(int i=0;i<r;i++)
    for(int j=0;j<n;j++)d[i][j]=INF;
  for(int i=0;i<r;i++){
    for(int j=0;j<n;j++)
      if((j+1)%r==i){
	Q.push(P(0,j));
	d[i][j]=0;
      }
    dijkstra(i);
  }
  ll ans=0;
  for(int i=0;i<q;i++){
    cin>>x>>y>>z;
    x--,y--;
    ll minc=INF;
    for(int j=0;j<r;j++)
      minc=min(minc,d[j][x]+d[j][y]);
    if(z-minc>0)ans+=z-minc;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 16480
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n,a[2001];
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n)
	cin>>a[i];
	sort(a,a+n);
	ll ans=0;
	rep(i,n-1){
		forn(j,i+1,n){
			int low=j+1,high=n-1;
			while(low<=high){
				int mid=(low+high)/2;
				if(a[i]+a[j]<=a[mid])
				high=mid-1;
				else
				low=mid+1;
			}
			ans+=low-j-1;
		}
	}
	cout<<ans;
	re 0;
}


Measured memory_bytes: 256
//usr/bin/env node $0 $@;exit 
var main=function(){
	for(;;){
		var n=Number(readline())
		if(!n)break;
		var r=0;
		var i=2;
		for(;;i++){
			//bitwise operations cause bug.
			var x=n-i*(i-1)/2;
			if(x<i)break;
			if(x%i==0)r++;
		}
		print(r);
	}
};

/// IO ///
if(typeof process!=='undefined'){
	//node.js
	var print=function(x){
		console.log(x);
	}
	var readline=(function(){
		var T=[],cnt=0;
		var stdin = process.openStdin();
		stdin.setEncoding('utf8');

		var input_fragment="";
		stdin.on('data', function(input) {
			var ref=(input_fragment+input).split("\n");
			input_fragment=ref.pop();
			for(var i=0;i<ref.length;i++){
				if(ref[i]=='')continue;
				T.push(ref[i]);
			}
		});
		stdin.on('end', function(z) {
			if(input_fragment){
				var ref=(input_fragment+"\n").split("\n");
				input_fragment=ref.pop();
				for(var i=0;i<ref.length;i++){
					if(ref[i]=='')continue;
					T.push(ref[i]);
				}
			}
			main();
		});

		return function(){
			if(T.length<=cnt)return null;
			return T[cnt++];
		};
	})();
}else{
	//v8
	main();
}

Measured memory_bytes: 16412
words = lambda t : list(map(t, input().split()))
s = input()

p = []
i = 0
while i < len(s):
    # s[i] == 'R'
    r = 0
    l = 0
    while s[i] == 'R':
        r += 1
        i += 1
    while i < len(s) and s[i] == 'L':
        l += 1
        i += 1
    p.append((r,l))
#print(p)


ans = []
for r,l in p:
    nr = ((r+1) // 2) + l // 2
    nl = r // 2 + ((l+1) // 2)
    st = ([0] * (r-1)) + [nr] + [nl] + ([0] * (l-1))
    ans += st
print(" ".join(map(str,ans)))


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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  string s;
  cin >> s;
  int ans = s.size(), cnt = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'S') cnt++;
    else {
      if (cnt) {
        ans -= 2;
        cnt--;
      }
    }
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3744
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

typedef long long ll;

int n,m,q;
ll ans[10];
map<pair<int,int>,int> vis;

void add(int x,int y){
    if(x<2||y<2|x>n-1||y>m-1) return;
    //printf("#%d %d\n",x,y);
    vis[make_pair(x,y)]++;
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    ans[0]=1ll*(n-2)*(m-2);
    for(int s=1;s<=q;s++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        for(int i=-1;i<=1;i++)
            if(i!=0) add(x+i,y),add(x,y+i);
        for(int i=-1;i<=1;i++)
            for(int j=-1;j<=1;j++)
                if(i!=0&&j!=0) add(x+i,y+j);
    }
    map<pair<int,int>,int>::iterator it;
    for(it=vis.begin();it!=vis.end();it++)
        ans[it->second]++,ans[0]--;
    for(int i=0;i<=9;i++)
        printf("%lld\n",ans[i]);
}


Measured memory_bytes: 56448
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=200005,lim=4000,mod=1000000007,o=2001;
typedef long long LL;
int n,vis[lim+5][lim+5];
LL flv[lim*2+5],inv[lim*2+5],ans,f[lim+5][lim+5];
struct data{int x,y;} dat[N];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

LL getmi(LL a,LL x)
{
	LL rt=1;
	while(x)
	{
		if(x&1) rt=rt*a%mod;
		a=a*a%mod,x>>=1;
	}
	return rt;
}

LL C(int n,int m)
{
	return n<m?0:flv[n]*inv[m]%mod*inv[n-m]%mod;
}

int main()
{
	n=getint();
	rep(i,1,n)
	{
		int x=getint(),y=getint();
		dat[i]=(data){x,y},++vis[x][y];
	}
	flv[0]=inv[0]=1;
	rep(i,1,lim<<1) flv[i]=flv[i-1]*i%mod,inv[i]=getmi(flv[i],mod-2);
	rep(i,-2000,2000) 
		rep(j,-2000,2000)
		{
			f[i+o][j+o]=(f[i-1+o][j+o]+f[i+o][j-1+o])%mod;
			if(i<0 && j<0) f[i+o][j+o]=(f[i+o][j+o]+vis[-i][-j])%mod;
		}
	rep(i,1,n) ans=(ans+f[dat[i].x+o][dat[i].y+o]-C(dat[i].x*2+dat[i].y*2,dat[i].y*2))%mod;
	ans=ans*(mod+1)/2%mod;
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}

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

int main() {
    int x;
    cin >> x;
    vector<ll> f;
    f.push_back(0);
    ll n=1;
    //int j=0;
    while(1){
        //nの五乗を生成
        f.push_back(pow(n,5));
        //cout << "f" << n << "=" << f[n] << endl;
        //正解があるか判定(n^5とそれまでのx^5で判定)
        for(int i=0;i<n;i++){
            //和
            //cout << "wa=" << f[n]+f[i] << endl;
            if(f[n]+f[i]==x){
                cout << n << " " << i*(-1) << endl;
                return 0;
            }
            //差
            if(f[n]-f[i]==x){
                cout << n << " " << i << endl;
                return 0;           
            }
        }
        //なければ次のnで検索
        n++;
        //j++;
    }
    return 0;
}


Measured memory_bytes: 3996
ans = 0
a = int(input())
b = int(input())
c = int(input())
x = int(input())
 
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i + 100*j + 50*k == x:
        ans += 1
 
print(ans)


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

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

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

void solve() {
    i64 n;
    cin >> n;
    vector<i64> a(n);
    for (auto& e : a) cin >> e;
    a.emplace_back(0);
    i64 money = 1000, stock = 0;

    for (i64 i = 0; i + 1 < n; i++) {
        money += stock * a[i];
        stock = 0;
        if (a[i] < a[i + 1]) {
            stock = money / a[i];
            money %= a[i];
        }
    }

    cout << money + stock * a[n - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 3652