akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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;
}

const ll INF = LONG_LONG_MAX / 2;

vector<int> xs;
vector<int> ys;
vector<int> ps;

ll calc(vector<int> &lxs, vector<int> &lys, const int num_line, const int num_city) {
    ll ans = 0;
    // sort(lxs.begin(), lxs.end());
    // sort(lys.begin(), lys.end());

#ifdef DEBUG
    printf("lxs: ");
    for (auto x : lxs) {
        cout << x << " ";
    }
    cout << endl;
    printf("lys: ");
    for (auto y : lys) {
        cout << y << " ";
    }
    cout << endl;
#endif

    for (int i = 0; i < num_city; i++) {
        ll dist = INF;
        for (auto lx : lxs) {
            chmin(dist, ll(abs(xs[i] - lx)) * ps[i]);
        }
        for (auto ly : lys) {
            chmin(dist, ll(abs(ys[i] - ly)) * ps[i]);
        }
        ans += dist;
    }

#ifdef DEBUG
    cout << "ans: " << ans << endl;
#endif
    return ans;
}

ll h(int pos, vector<int> &lxs, vector<int> &lys, const int num_line, const int num_city, const vector<int> &acc_city) {
    if (pos >= num_line) {
        return calc(lxs, lys, num_line, num_city);
    }

    ll cand = INF;
    const int cur_city = acc_city[pos];
    lxs.push_back(xs[cur_city]);
    chmin(cand, h(pos + 1, lxs, lys, num_line, num_city, acc_city));
    lxs.pop_back();
    lys.push_back(ys[cur_city]);
    chmin(cand, h(pos + 1, lxs, lys, num_line, num_city, acc_city));
    lys.pop_back();

    return cand;
}

ll g(const int num_line, const int num_city, const vector<int> &acc_city) {
#ifdef DEBUG
    for (auto city : acc_city) {
        cout << city << " ";
    }
    cout << endl;
#endif

    vector<int> lxs;
    lxs.push_back(0);
    vector<int> lys;
    lys.push_back(0);

    return h(0, lxs, lys, num_line, num_city, acc_city);
}

ll f(int cur, const int num_line, const int num_city, vector<int> &acc_city) {
    if ((int) acc_city.size() == num_line) {
        return g(num_line, num_city, acc_city);
    }
    if (cur >= num_city) {
        return INF;
    }

    ll cand = INF;

    acc_city.push_back(cur);
    chmin(cand, f(cur + 1, num_line, num_city, acc_city));
    acc_city.pop_back();
    chmin(cand, f(cur + 1, num_line, num_city, acc_city));

    return cand;
}

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

    xs.resize(N);
    ys.resize(N);
    ps.resize(N);
    for (int i = 0; i < N; i++) {
        int X, Y, P;
        cin >> X >> Y >> P;
        xs[i] = X;
        ys[i] = Y;
        ps[i] = P;
    }

    for (int k = 0; k <= N; k++) {
        // printf("k: %d\n", k);
        vector<int> acc_city;
        cout << f(0, k, N, acc_city) << endl;
    }

    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
const ll mod =1000000007;
int main(){
    int n;
    cin>>n;
    vector<int> col(n+1,-1);
    vector<queue< pair<int,int> >> wi(n+1);
    for(int i=0; i<n-1; i++){
        int u,v,w;
        cin>>u>>v>>w;
        wi.at(u).push(make_pair(v,w));
        wi.at(v).push(make_pair(u,w));
    }
    queue<int> sa;
    sa.push(1);
    col[1]=0;
    while(!sa.empty()){
        int tmp =sa.front(); sa.pop();
        int ctmp = col[tmp];
        queue<pair<int,int>> qt = wi.at(tmp);
        while(!qt.empty()){
            int u=qt.front().first;
            int d = qt.front().second; qt.pop();
            if(col[u]==-1){
                col[u]= (d+ctmp)%2;
                sa.push(u);
            }
        }
    }
    for(int i=1; i<n+1; i++){
        cout<<col[i]<<endl;
    }
}

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

int main(){
  int n,k;
  cin >>n >> k;
  vector<int>l(n);
  for(int i=0;i<n;i++){
    cin>>l.at(i);
  }
  
  sort(l.begin(),l.end());
  reverse(l.begin(),l.end());
  
  int ans=0;
  
  for(int i=0;i<k;i++){
    ans += l.at(i);
  }
  cout<< ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back

typedef long long LL; 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

struct UnionFind{
    vector<int> par,rank,sum;
    UnionFind(int N){
        par.assign(N,0);
        rank.assign(N,0);
        sum.assign(N,0);
        REP(i,N) par[i]=i;
        REP(i,N) sum[i]=1;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    void unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]) swap(x,y);
 
        //x becomes root
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
        sum[x] += sum[y];
    }
};

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	

    LL N,M; cin >> N >> M;

    VI A(M), B(M);
    REP(i,M)
    {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    UnionFind UF(N);
    vector<LL> ans(M);
    ans[0] = N * (N-1) / 2;


    for(int i = M - 1; i >= 1; i--)
    {
        if(UF.same(A[i],B[i]))
        {
            ans[M-i] = ans[M-i-1];
            UF.unite(A[i],B[i]);
        }
        else
        {
            ans[M-i] = ans[M-i-1] - UF.sum[UF.find(A[i])] * 1LL * UF.sum[UF.find(B[i])];
            UF.unite(A[i], B[i]);
        }
    }


    reverse(ans.begin(), ans.end());

    REP(i,M)
    {
        cout << ans[i] << endl;
    }



}


Measured memory_bytes: 4096
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using static System.Console;

namespace ConsoleApp2
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine())%10;
            if (N == 3)
            {
                WriteLine("bon");
                return;
            }
            if (new int[] { 0,1,6,8}.Any(x=>x==N))
            {
                WriteLine("pon");
                return;
            }
            Console.WriteLine("hon");
        }

    }
}

Measured memory_bytes: 18460
#include <stdio.h>
#define H 500000
 
int A[H],n; 

void maxHeapify(int *A,int i){

  int largest,l,r,temp;

  l = 2*i;
  r = (2*i)+1;

  if(l<=n && A[l]>A[i])
    largest = l;
  else
    largest = i;

  if(r<=n && A[r]>A[largest])
    largest = r;
  
  if(largest != i){
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    maxHeapify(A,largest);
  }
}

void buildMaxHeap(int *A){

  int i;

  for(i=n/2;i>0;i--){
    maxHeapify(A,i);
  }
}


int main(void){
 
  int k,p,l,r,i;

  scanf("%d",&n);
 
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
  }
    buildMaxHeap(A);

  for(i=1;i<=n;i++){
    printf(" %d",A[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

int main() {
	int L;
	cin >> L;
	double a = (double) L / 3.0;
	double answer = a * a * a;
	//double answer = pow ((double) L, 1.0 / 3.0);
	printf ("%.7lf\n", answer);
	return 0;
}


Measured memory_bytes: 256
S = input()
T = input()
l = []
for i in range(len(S)-len(T) + 1): 
        c = 0 
        s = S[i:i + len(T)]
        for j in range(len(T)):
                if s[j] != T[j]:
                        c += 1
        l.append(c)
print(min(l))

Measured memory_bytes: 67636
#include <iostream>
using namespace std;
int main() {
	int a, b, c, N;
	cin >> N;
	for(int i=0; i<N; i++) {
		cin >> a >> b >> c;
		cout << (((a*a==b*b+c*c) || (b*b==c*c+a*a) || (c*c==a*a+b*b)) ? "YES" : "NO") << endl;
	}
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#include <fstream>
#include <cstdio>
using namespace std;
// vector<pair<int,int> > v;
// cin.ignore();//twice getline(cin,s);
// g++ iterator.cpp -std=c++17
// cout<<(A + B == C ? "YES" : "NO")<<endl;
// __gcd(a,b)
// string s=to_string(n);
// string p=s.substr(0,len);
// string q=s.insert(0,str);
// sort(arr, arr+n, greater<int>());
// cout<<fixed<<setprecision(9)<<pi<<endl
// const  double pi = acos(-1.0);
// sort(v.rbegin(),v.rend());
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define vll vector<ll>
#define mll map<ll,ll >
#define mlli map<ll,ll>::iterator
#define size size()
#define endl "\n"
#define ll long long int
#define ld long double
void fast(){ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);}


int main(void)
{
	fast();
	ll d,t,s;
	cin>>d>>t>>s;
	if(t*s>=d)
	{
		cout<<"Yes"<<endl;
	}	
	else
	{
		cout<<"No"<<endl;
	}
}

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

int main(){
  int A,B,T;
  cin >> A >> B >> T;
  int ans = 0;
  int mul = (T + 0.5) / A;
  for(int i = 0 ;i < mul;i++){
    ans += B;
  }
  cout << ans << endl ;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,x[N];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)cin>>x[i];
	sort(x,x+n);
	if(n%2==1)
	{
		cout<<0<<endl;
		return 0;
	}
	cout<<x[n/2]-x[n/2-1]<<endl;
	return 0;
}

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

int conv[256];
int grid[1024][1024];
int emblem[2][2];

bool check(int x, int y)
{
	for (int i = 0; i < 2; i++){
		for (int j = 0; j < 2; j++){
			if (grid[x + i][y + j] != emblem[i][j]) return false;
		}
	}
	return true;
}

int main()
{
	conv['J'] = 1;
	conv['O'] = 2;
	conv['I'] = 3;
	
	int m, n;
	char c;
	
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= m; i++){
		for (int j = 1; j <= n; j++){
			scanf(" %c", &c);
			grid[i][j] = conv[c];
		}
	}
	for (int i = 0; i < 2; i++){
		for (int j = 0; j < 2; j++){
			scanf(" %c", &c);
			emblem[i][j] = conv[c];
		}
	}
	
	int def = 0;
	for (int i = 1; i < m; i++){
		for (int j = 1; j < n; j++){
			def += check(i, j);
		}
	}
	
	int maxi = def;
	for (int i = 1; i <= m; i++){
		for (int j = 1; j <= n; j++){
			int tmp = grid[i][j];
			
			int num = def;
			for (int x = i - 1; x <= i; x++){
				for (int y = j - 1; y <= j; y++){
					num -= check(x, y);
				}
			}
			
			for (int to = 1; to <= 3; to++){
				grid[i][j] = to;
				int add = 0;
				for (int x = i - 1; x <= i; x++){
					for (int y = j - 1; y <= j; y++){
						add += check(x, y);
					}
				}
				maxi = max(maxi, num + add);
			}
			grid[i][j] = tmp;
		}
	}
	printf("%d\n", maxi);
}

Measured memory_bytes: 5280
t = input()
skip = -1
t = list(t)
ans = []
for i,j in enumerate(t):
    if j == "?":
        if i == 0 or i == len(t)-1:
            ans.append("D")
        else:
            if ans[i-1] == "P":
                ans.append("D")
            else:
                if t[i+1] == "?":
                    ans.append("P")
                else:
                    ans.append("D")
    else:
        ans.append(j)
print("".join(ans))


Measured memory_bytes: 12412
import itertools
n,a,b,c=map(int,input().split())
abc=[a,b,c]
l=[int(input()) for i in range(n)]
m=[i for i in range(3)]
mi=100000000000000
for i in list(itertools.product(*[m for _ in range(n)])):
    #print(i)
    #print(0)
    sub=[[] for j in range(3)]
    for j in range(n):
        sub[i[j]].append(j)
    #print(sub)
    mi_sub=0
    for j in range(3):
        subsub=sub[j]
        l_sub=len(subsub)
        if l_sub==0:
            mi_sub=100000000000000
            break
        mi_subsub=100000000000000
        for k in range(2**l_sub):
            mi_subsubsub=[0,0]
            for l_subsub in range(l_sub):
                if ((k>>l_subsub) &1):
                    mi_subsubsub[0]+=1
                    #print(subsub[l_subsub])
                    mi_subsubsub[1]+=l[subsub[l_subsub]]
            if mi_subsubsub[0]!=0:
                mi_subsub=min(mi_subsub,abs(mi_subsubsub[1]-abc[j])+mi_subsubsub[0]*10-10)
        mi_sub+=mi_subsub
    mi=min(mi,mi_sub)
    #print(0)
print(mi)


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

int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 

	    
      long long n,i,j,k,sum=0,count=0,ans=0,x=0,y=0,l,r,m;
      cin>>n>>m>>k;
      long long a[n],b[m],c[n],d[m];
      for(i=0;i<n;i++)
      {
          cin>>a[i];
          sum+=a[i];
          c[i]=sum;
      }
      for(i=0;i<m;i++)
      {
          cin>>b[i];
          sum+=b[i];
          count+=b[i];
          d[i]=count;
      }
      if(sum<=k)
      {
          cout<<n+m; return 0;
      }
      j=lower_bound(d,d+m,k)-d;
      if(j==m)
      ans=m;
      else
      {
          if(k==d[j])
          ans=j+1;
          else
          ans=j;
      }
 
      for(i=0;i<n;i++)
      {
          x=k-c[i];
          if(x<0)
          break;
          j=lower_bound(d,d+m,x)-d;
      if(j==m)
      ans=max(ans,i+1+m);
      else
      {
          if(x==d[j])
          ans=max(ans,i+1+j+1);
          else
          ans=max(ans,i+1+j);
      }
      }
      cout<<ans;
	return 0;
}

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

vector<int> primes;

void sieve() {
    vector<bool> is_prime(55556, true);
    is_prime[0] = false; is_prime[1] = false;
    for (int i = 2; i <= 55555; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 2 * i; j <= 55555; j += i) {
            is_prime[j] = false;
        }
    }
}

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

    vector<int> res;
    for (int i = 0; i < primes.size(); i++) {
        if (res.size() == N) break;
        if (primes[i] % 5 == 1) {
            res.push_back(primes[i]);
        }
    }

    for (int i = 0; i < N; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

std::vector<int> vec;
int n;
int c = 0;

int main() {
    std::cin >> n;
    vec.assign(n+2, 0);
    for (int i = 1; i <=n; i++) {
        std::cin >> vec[i];
    }
    for (int i = 1; i <= n+1; i++) {
        c += std::abs(vec[i] - vec[i-1]);
    }
    for (int i = 1; i <= n; i++) {
        int p = c;
        p = p - std::abs(vec[i]-vec[i-1]) - std::abs(vec[i]-vec[i+1]) + std::abs(vec[i-1]-vec[i+1]);
        std::cout << p << std::endl;
    }
}


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

// using namespace __gnu_pbds;
using namespace std;

#define fbo find_by_order
#define ook order_of_key
#define fi first
#define se second
#define long long long
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

// /mnt/c/Users/vince/Desktop/POST-IOI/  

int n;
int A[1000003];

int main()
{
	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// freopen("input.in", "r", stdin);

	scanf("%d", &n);
	bool bol = 0;
	int hit = 0;
	for(int i = 0; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		if(x == y) hit++;
		else hit = 0;
		if(hit >= 3) bol = 1;
	}
	if(bol) printf("Yes\n");
	else printf("No\n");

}

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

int MAX_DP = 18000;
int CENTER = 9000;
bool dp[3002][18000];
bool dp2[3002][18000];

int main()
{
	string S;
	int x, y;
	cin >> S >> x >> y;
	vector<int> xList;
	vector<int> yList;
	bool horizontal = true;
	int count = 0;
	rep(i, S.length()) {
		if (S[i] == 'F') {
			count++;
		} else {
			if (count > 0) {
				if (horizontal) {
					xList.push_back(count);
				} else {
					yList.push_back(count);
				}
			}
			count = 0;
			horizontal = !horizontal;
		}
	}
	if (count > 0) {
		if (horizontal) {
			xList.push_back(count);
		} else {
			yList.push_back(count);
		}
	}
	//最初が「進め」のときはX方向に固定される。
	//その分目的地をずらす
	if (S[0] == 'F') {
		x -= xList[0];
		xList.erase(xList.begin());
	} 
	//X方向のDP
	int left = CENTER;
	int right = CENTER;
	int xlen = xList.size();
	dp[0][CENTER] = true;
	for (int i = 1; i <= xlen; i++) {
		for (int j = left; j <= right; j++) {
			if (dp[i - 1][j]) {
				int j1 = j - xList[i - 1];
				int j2 = j + xList[i - 1];
				if (j1 >= 0) {
					dp[i][j1] = true;
					left = min(left, j1);
				}
				if (j2 < MAX_DP) {
					dp[i][j2] = true;
					right = max(right, j2);
				}
			}
		}
	}

	bool xReachable = dp[xlen][CENTER + x];
	bool yReachable = false;
	if (xReachable) {
		int ylen = yList.size();
		dp2[0][CENTER] = true;
		left = CENTER;
		right = CENTER;
		for (int i = 1; i <= ylen; i++) {
			for (int j = left; j <= right; j++) {
				if (dp2[i - 1][j]) {
					int j1 = j - yList[i - 1];
					int j2 = j + yList[i - 1];
					if (j1 >= 0) {
						dp2[i][j1] = true;
						left = min(left, j1);
					}
					if (j2 < MAX_DP) {
						dp2[i][j2] = true;
						right = max(right, j2);
					}
				}
			}
		}
		yReachable = dp2[ylen][CENTER + y];
	}

	if (xReachable && yReachable) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 72448
num = input()
flag1 = False
flag2 = False
if int(num) % 9 == 0:
    flag1 = True

sum = 0
for i in num:
    sum += int(i)
  
if sum % 9 == 0:
    flag2 = True
    
if flag1 and flag2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9248
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  string s;
  cin>>s;
  int n=s.size();

  string t;
  for(int i=0;i<n;i++){
    if(s[i]!='x') t+=s[i];
  }
  string rt=t;
  reverse(rt.begin(),rt.end());
  if(t!=rt){
    cout<<-1<<endl;
    return 0;
  }

  int lastl=0,lastr=0;
  if(t.size()%2){
    lastl=lastr=t.size()/2;
  }else{
    lastl=t.size()/2-1;
    lastr=t.size()/2;
  }
  int cls[n+1]={},crs[n+1]={};
  int tmpc=0,it=0;
  for(int i=0;it<=lastl;i++){
    if(s[i]=='x') tmpc++;
    else{
      cls[it]=tmpc;
      it++;
      tmpc=0;
    }
  }
  tmpc=0;
  it=0;
  for(int i=n-1;it<=lastl;i--){
    if(s[i]=='x') tmpc++;
    else{
      crs[it]=tmpc;
      it++;
      tmpc=0;
    }
  }

  ll ans=0;
  for(int i=0;i<=it;i++){
    ans+=abs(cls[i]-crs[i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1408
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

type edge struct {
	to, dist int
}

type node struct {
	no        int
	edgeList  []edge
	weight    int
	isVisited bool
}

type graph []node

func main() {
	sc.Split(bufio.ScanWords)

	N, M := scanInt(), scanInt()
	G := make(graph, N)
	for i := 0; i < N; i++ {
		G[i].no = i
	}
	for i := 0; i < M; i++ {
		l, r, d := scanInt(), scanInt(), scanInt()
		G[l-1].edgeList = append(G[l-1].edgeList, edge{to: r - 1, dist: d})
		G[r-1].edgeList = append(G[r-1].edgeList, edge{to: l - 1, dist: -d})
	}

	queue := make([]*node, 0)
	for i := 0; i < N; i++ {
		if G[i].isVisited {
			continue
		}

		queue = append(queue, &G[i])
		G[i].isVisited = true

		for len(queue) > 0 {
			grayNode := queue[0]
			// ここを queue := とtypoすると、for文中でのみ使えるqueueの定義となり無限ループになる
			queue = queue[1:]
			for _, ed := range grayNode.edgeList {
				if G[ed.to].isVisited {
					if G[ed.to].weight != G[grayNode.no].weight+ed.dist {
						fmt.Println("No")
						return
					}
				} else {
					queue = append(queue, &G[ed.to])
					G[ed.to].weight = G[grayNode.no].weight + ed.dist
					G[ed.to].isVisited = true
				}
			}
		}
	}

	fmt.Println("Yes")
}


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

using namespace std;

#define ll  long long
#define ld  double

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

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 405;
const int   S   = N * N;

typedef pair<int,int>   ii;

const int   mod = 998244353;

void add(int &a,int b)  {
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub(int &a,int b)  {
    a -= b;
    if (a <  0)
        a += mod;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}
int Pow(int a,int b)    {
    int ans = 1;
    while (b)   {
        if(b & 1)   ans = mul(ans,a);
        a = mul(a,a);   b >>= 1;
    }
    return  ans;
}
int inv(int a,int p)    {
    return  a == 1 ? 1 : p - 1ll * p * inv(p % a,a) / a;
}

int Fac[N];
int Inv[N];

int Ckn(int n,int k)    {
    if (n < k)  return  0;
    if (k < 0)  return  0;

    return  mul(Fac[n],mul(Inv[k],Inv[n - k]));
}

int a[N];
ii  R[S];

int F[S][N];
int G[S][N];

int tot = 0;

int cal(int l,int r,int h)  {
    vector<int> vec;

    int p = l;

    for(int i = l ; i <= r ; ++i)    if (a[i] == h)  {
        if (i > p)  vec.pb(cal(p,i - 1,h + 1));
        p = i + 1;
    }
    if (r >= p) vec.pb(cal(p,r,h + 1));

    vector<int> f(1,1);
    vector<int> g(1,1);

    int len = 0;

    for(int x : vec)    {
        int L = R[x].Y - R[x].X + 1;

        vector<int> nf(len + L + 1,0);
        vector<int> ng(len + L + 1,0);

        for(int i = 0 ; i <= L ; ++i)
        for(int j = 0 ; j <= len ; ++j)
            add(nf[i + j],mul(f[j],F[x][i])),
            add(ng[i + j],mul(g[j],G[x][i]));

        f.swap(nf);
        g.swap(ng); len += L;
    }
    int x = tot;
    int L = r - l + 1;

    vector<int> ng(L + 1);

    for(int i = 0 ; i <= len ; ++i)
        ng[i + L - len] = g[i];

    g.swap(ng);
    f.resize(L + 1);

    for(int i = 0 ; i <= L ; ++i)   {
        add(F[x][i],g[i]);
        add(G[x][i],mul(g[i],Pow(2,L - i)));
        add(F[x][i],mul(f[i],Pow(2,L - i) - 1));

        for(int j = 1 ; j <= i ; ++j)   {
            int M = mul(Pow(2,L - i),Ckn(i,j));

            add(G[x][i - j],mul(M,g[i]));
            add(F[x][i - j],mul(M,f[i]));
        }
    }
    R[x] = ii(l,r);
    return  tot++;
}

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

    Fac[0] = Inv[0] = 1;

    for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i);     Inv[N - 1] = inv(Fac[N - 1],mod);
    for(int i = N - 2 ; i ; --i)    Inv[i] = mul(Inv[i + 1],i + 1);

    int n;  cin >> n;

    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i];

    cout << F[cal(1,n,1)][0] << endl;
}

Measured memory_bytes: 258432
#include <stdio.h>

int main(void)
{
	int a,b,c;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(a < b && b < c){
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	
	return(0);
}

Measured memory_bytes: 2688
#include <algorithm>
#include <cmath>
#include <queue>
#include <iostream>
#include <cstring>
#include <map>
#include <cstdio>
#include <vector>
#include <functional>
#define lson (i << 1)
#define rson ((i << 1) | 1)
using namespace std;
typedef long long ll;
const int maxn= 101000;

int t1[maxn], t2[maxn], c[maxn];
bool cmp(int *r, int a, int b, int l) {
	return r[a] == r[b] && r[l + a] == r[l + b];
}

void get_sa(int str[], int sa[], int Rank[], int height[], int n, int m) {
	n++;
	int p, *x= t1, *y= t2;
	for(int i= 0; i < m; i++) c[i]= 0;
	for(int i= 0; i < n; i++) c[x[i]= str[i]]++;
	for(int i= 1; i < m; i++) c[i]+= c[i - 1];
	for(int i= n - 1; i >= 0; i--) sa[--c[x[i]]]= i;
	for(int j= 1; j <= n; j<<= 1) {
		p= 0;
		for(int i= n - j; i < n; i++) y[p++]= i;
		for(int i= 0; i < n; i++)
			if(sa[i] >= j) y[p++]= sa[i] - j;
		for(int i= 0; i < m; i++) c[i]= 0;
		for(int i= 0; i < n; i++) c[x[y[i]]]++;
		for(int i= 1; i < m; i++) c[i]+= c[i - 1];
		for(int i= n - 1; i >= 0; i--) sa[--c[x[y[i]]]]= y[i];

		swap(x, y);
		p= 1;
		x[sa[0]]= 0;
		for(int i= 1; i < n; i++) x[sa[i]]= cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
		if(p >= n) break;
		m= p;
	}
	int k= 0;
	n--;
	for(int i= 0; i <= n; i++) Rank[sa[i]]= i;
	for(int i= 0; i < n; i++) {
		if(k) k--;
		int j= sa[Rank[i] - 1];
		while(str[i + k] == str[j + k]) k++;
		height[Rank[i]]= k;
	}
}

int Rank[maxn];
int sa[maxn];
int str[maxn], height[maxn];
char s[maxn];
int id[maxn];
struct node {
	int Min;
	int Max;
	int flag;
} anspos[15];

void ini() {
	for(int i= 0; i <= 12; i++) anspos[i].Min= 0x3f3f3f3f, anspos[i].Max= -1;
}

bool can(int len, int n, int num) {
	int l= 2, r= 2;
	ini();
	for(int i= 2; i <= n; i++) {
		if(height[i] >= len) {
			int id1= id[sa[i - 1]];
			int id2= id[sa[i]];

			anspos[id1].Max= max(anspos[id1].Max, sa[i - 1]);
			anspos[id1].Min= min(anspos[id1].Min, sa[i - 1]);

			anspos[id2].Max= max(anspos[id2].Max, sa[i]);
			anspos[id2].Min= min(anspos[id2].Min, sa[i]);
			int t;
			for(t= 0; t < num; t++)
				if(anspos[t].Max - anspos[t].Min < len) break;
			if(t == num) return 1;
		}
		else {
			for(int j= 0; j <= 10; j++) anspos[j].Min= 0x3f3f3f3f, anspos[j].Max= -1;
		}
	}
	for(int i= 0; i < num; i++)
		if(!anspos[i].flag) return 0;
	return 1;
}

int main() {
	int k, n= 1, t;
    scanf("%d", &t);
	ini();
	int tot= 0, len= 0x3f3f3f3f;
	for(int i= 0; i < n; i++) {
		scanf("%s", s);
		for(int j= 0; s[j] != '\0'; j++) {
			id[tot]= i;
			str[tot++]= s[j] - 'a' + 10;
		}
		id[tot]= i;
		str[tot++]= i;
		len= min(len, (int)strlen(s));
	}
	str[tot]= 0;
	get_sa(str, sa, Rank, height, tot, 100);
	int l= 0, r= len;
	int ans= 0;
	while(l <= r) {
		int mid= (l + r) >> 1;
		if(can(mid, tot, n)) {
			ans= mid;
			l= mid + 1;
		}
		else
			r= mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
int main(void){
int N=0,A=0,B=0;
scanf("%d %d %d", &N,&A,&B);
if(N * A > B){
printf("%d", B);
}else if(N * A < B){
printf("%d", N * A);
}else{
printf("%d", B);
}

 return 0;
}


Measured memory_bytes: 128
import math

def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

n = NextInt()
a = NextIntList()
ans = [0]*n
for i in range(n-1):
    ans[a[i]-1] += 1

for i in ans:
    print(i)

Measured memory_bytes: 33632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS=1e-10;
const ll INF=1000000000;
int main(){
    int prime[300000];
    for(int i=0;i<300000;i++){
        prime[i]=1;
    }
    prime[1]=0;prime[0]=0;
    for(int i=2;i<=150000;i++){
        if(prime[i]==1){
            for(int j=i+i;j<=300000;j+=i){
                prime[j]=0;
            }
        }
    }
    int c[300000]={};
    for(int i=1;i<300000;i++){
        c[i]=c[i-1]+prime[i];
    }
    int n;
    while(cin>>n,n){
        cout<<c[2*n]-c[n]<<endl;
    }
    return 0;
}


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

using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl;
//#define DEBUG(x) ;

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

int main(int argc, char **argv)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll N, K; cin >> N >> K;
	vector<ll> A(N); REP(i, N) cin >> A[i];
	vector<ll> cnt(200000+10, 0);
	REP(i, N)
	{
		++cnt[A[i]];
	}

	sort(ALL(cnt), greater<ll>());
	ll sum{0};
	for (ll i = K; i < cnt.size(); ++i)
		sum += cnt[i];
	
	std::cout << sum << std::endl;
	return 0;
}


Measured memory_bytes: 6340
# reference -> https://atcoder.jp/contests/abc131/submissions/10358162
import sys
sys.setrecursionlimit(100000)

# 再帰的に連結部分の辺の数を求める
# 同じ辺を2回ずつ数えるので、最終的には2で割る
def solve(x, x_set, y_set, x2y, y2x):
  num_e = 0
  if x in x2y:
    x_set.add(x)
    yl = x2y.pop(x)
    num_e += len(yl)
    for y in yl:
      num_e += solve(y, y_set, x_set, y2x, x2y)
  return num_e


N = int(input())
X2Y = {}
Y2X = {}
for i in range(N):
  x, y = map(int, input().split())
  if x in X2Y:
    X2Y[x].append(y)
  else:
    X2Y[x] = [y]
  if y in Y2X:
    Y2X[y].append(x)
  else:
    Y2X[y] = [x]


ans = 0
while X2Y:
    x = next(iter(X2Y)) # まだスタートに選んでいないxを取り出す
    x_set = set() # 上のxと連結であるxの集合
    y_set = set() # 上のxと連結であるyの集合
    num_e = solve(x, x_set, y_set, X2Y, Y2X)
    ans += len(x_set)*len(y_set) - num_e//2

print(ans)

Measured memory_bytes: 88344
#include<bits/stdc++.h>
using namespace std;
int digit(int,long long);
int main(){
	long long n;
	cin>>n;
	int m=n;
	int sum=0;
	while(n){
		sum+=n%10;
		n/=10;
	}
	if(m%sum==0){
		cout<<"Yes"<<endl;
	}
	else cout<<"No"<<endl;
}
int digit(int n,long long dig){
	return n%(dig*10)/dig;
}


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

#define all_of(x) std::begin(x), std::end(x)
#ifdef _GLIBCXX_DEBUG
    #define debug(x) cerr << #x << ": " << x << endl
#else
    #define debug(x) 
#endif

using namespace std;

using LL = long long;

template<typename T>
ostream& operator << (ostream& out, const vector<T>& v) {
    out << "[";
    for(const auto& x : v) {
        out << x << ", ";
    }
    return out << "]";
}
template<typename T>
istream& operator >> (istream& in, vector<T>& v) {
    for(auto& x : v) {
        in >> x;
    }
    return in;
}

template<typename S, typename T>
ostream& operator << (ostream& out, const pair<S, T>& p) {
    return out << "{" << p.first << ", " << p.second << "}";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    LL N, X, M;
    cin >> N >> X >> M;
    vector<bool> V(M), C(M);
    vector<LL> A;
    LL x = X;
    while(true) {
        V[x] = true;
        x = (x * x) % M;
        if(V[x]) {
            break;
        }
    }
    while(true) {
        C[x] = true;
        A.push_back(x);
        x = (x * x) % M;
        if(C[x]) {
            break;
        }
    }
    LL ans = 0;
    while(N) {
        if(C[X]) {
            break;
        }
        ans += X % M;
        X = (X * X) % M;
        --N;
    }
    for(int i = 0; i < int(A.size()); ++i) {
        ans += (N / LL(A.size()) + LL((N % A.size()) > i)) * A[i]; 
    }
    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 3884
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
ans=0
for i in a:
    if i>n:
        ans+=1
    else:
        b[i-1]+=1
for i in range(n):
    if b[i]>i:
        ans+=b[i]-i-1
    else:
        ans+=b[i]
print(ans)

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll R, G, B, N;
    cin >> R >> G >> B >> N;

    ll ans = 0;
    for (int i = 0; i <= 3000; i++) {
        for (int j = 0; j <= 3000; j++) {
            ll tmp = N - i*R - j*G;
            if (tmp >= 0 && tmp % B == 0) {
                ans++;
            }
        }
    }

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

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    R = int(input())
    if R < 1200:
        print('ABC')
    elif R < 2800:
        print('ARC')
    else:
        print('AGC')
if __name__ == '__main__':
    main()
    

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = pair<ii, int>;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define __lcm(a, b) a * b / __gcd(a, b)
const int MOD = 1e9 + 7;
const int INF = 2e9;
const int N = 1e5 + 5;

int n;
int a[N];

int SlidingWindow(int x) {
    int l = 1, r = 1, maxim = 0;
    while(r <= x) {
        while(a[r + 1] <= a[r]) {
            r++;
        }
        maxim = max(maxim, r - l);
        r++; l = r;
    }
    return maxim;
}

/* 
5
10 4 8 7 3
     ^
         ^
*/

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n + 1] = INF;
    cout << SlidingWindow(n) << "\n";
}

int main() {
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    solve();
    
}

Measured memory_bytes: 4004
n,m=map(int,input().split())
g = [[ ] for _ in range(n)]
for _ in range(m):
    l,r,d = map(int,input().split())
    g[l-1].append((d,r-1))
    g[r-1].append((-d,l-1))
inf = 12345678901234
dist = [inf]*n

import queue
q=queue.Queue()
for i in range(n):
    if dist[i] != inf: continue
    dist[i] = 0
    q.put((0,i))
    while not q.empty():
        cost, nown = q.get()
        for nextc, nextn in g[nown]:
            if dist[nextn] != inf:
                if dist[nextn] != cost + nextc:
                    print('No')
                    exit()
            else:
                dist[nextn] = cost+nextc
                q.put((dist[nextn], nextn))
print('Yes')


Measured memory_bytes: 86684
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A) # A をソート
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)] # BからX-Yの最小パターンを出す
sL = sorted(L,key=lambda x:x[1]) # Lをソート

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()

if Q == N - K + 1:
    # 全部の要素が選ばれる = 必ず最小値が選ばれる
    print(L[0][1])
    exit()

if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()


for key,value in sL:
    max_value = B[key + Q - 1]
    min_value = B[key]
    C = [(i if i >= min_value else None) for i in A]
    i = 0
    j = 0
    count = 0
    min_OK = max_OK = False
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp < 1:
            # 要素を取得できないパターン
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and (sC[0] == min_value):
            min_OK = True
        if not max_OK and max_value in sC[0:tmp]:
            max_OK = True
        count += tmp - len([i for i in sC[:tmp] if i > max_value])
        i = j +1
    if min_OK and max_OK and (count >= Q):
        print(value)
        exit()

print(L[0][1])



Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
long double EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////////////////



int main(){fastio;
    
    ll n;cin>>n;
    double ans=0.0;
    while(n--){
        double a;cin>>a;string s;cin>>s;
        if(s[0]=='J'){
            ans+=a;
        }else{
            ans+=380000.0*a;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <utility>
#include <set>
#include <bitset>
#define ls x<<1
#define rs x<<1|1
#define mst(a,b) memset(a,b,sizeof(a))
#define scd(x) scanf("%d", &x)
#define scdd(x,y) scanf("%d%d", &x, &y)
#define scddd(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define eb emplace_back
#define rep(i,n) for(int i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define IOS std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = 2*acos(0.0);
const double eps = 1e-13;
const ll mod = 998244353;
const int maxn = 2e5 + 10;
const int maxm = 50000 + 10;

int a[maxn], stmin[maxn][50], stmax[maxn][50], tmp[maxn];

void init(int n) {
    for (int i = 0; i < n; i++)
        stmin[i][0] = a[i], stmax[i][0] = a[i];

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++){
            stmin[i][j] = min(stmin[i][j - 1],stmin[i + (1 << (j - 1))][j - 1]);
            stmax[i][j] = max(stmax[i][j - 1],stmax[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int qmin(int l, int r) {
    int k = (int)(log((double)(r - l + 1)) / log(2.0));
    return min(stmin[l][k],stmin[r - (1 << k) + 1][k]);
}

int qmax(int l, int r) {
    int k = (int)(log((double)(r - l + 1)) / log(2.0));
    return max(stmax[l][k],stmax[r - (1 << k) + 1][k]);
}

int d[maxn];
int lowbit(int x) {
    return x&(-x);
}

void add(int x, int k) {
    while(x<maxn) {
        d[x]+=k;
        x += lowbit(x);
    }
}

int query(int x) {
    int sum=0;
    while(x>0) {
        sum += d[x];
        x -= lowbit(x);
    }
    return sum;
}

void solve() {
    int n, k;
    scdd(n, k);
    for(int i=0; i<n; i++) scd(a[i]), a[i]++;
    init(n);
    int now=0;
    for(int i=0; i<k-1; i++) {
        add(a[i], 1);
        now += i+1-query(a[i]);
    }
    int ans=0, flag=0;
    bool first=1;
    for(int i=k-1; i<n; i++) {
        add(a[i], 1);
        now += k-query(a[i]);
        if(!flag){
            if(now==0){
                if(first) ans++;
                first=0;
            }
            else ans++;
        }
        now -= query(a[i-k+1])-1;
        add(a[i-k+1], -1);
        if(i<n-1) {
            if(qmin(i-k+1, i+1)==a[i-k+1] and qmax(i-k+1, i+1)==a[i+1]){
                flag=(flag+1)%k;
            }
            else flag=0;
        }
    }
    printf("%d\n", ans);
}

int main() {
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    //freopen("ans.txt","w",stdout);
#endif
    //IOS;
    solve();

    return 0;
}


Measured memory_bytes: 80000
#include<iostream>
using namespace std;
int main(){
  int mon,c;
  while(1){
    cin>>mon;
    if(mon==0){
      break;
    }
    mon=1000-mon;
    c=0;
    for(int i=0;i<15;i++){
      if(mon==0){
	break;
      }
      if(mon>=500){
	mon-=500;
	c++;
      }if(mon<500&&mon>=100){
	mon-=100;
	c++;
      }if(mon<100&&mon>=50){
	mon-=50;
	c++;
      }if(mon<50&&mon>=10){
	mon-=10;
	c++;
      }if(mon<10&&mon>=5){
	mon-=5;
	c++;
      }if(mon<5){
	c+=mon;
	mon=0;
      }
    }
  cout<<c<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long h=sc.nextInt();
		long w=sc.nextInt();
		int n=sc.nextInt();
		HashSet<Long> hs1=new HashSet<>();
		HashSet<Long> hs2=new HashSet<>();
		for(int i=0;i<n;i++){
			long a=sc.nextInt()-1;
			long b=sc.nextInt()-1;
			hs1.add(a*w+b);
		}
		long[] count=new long[10];
		count[0]=(h-2)*(w-2);
		
		for(long l:hs1){
			long a=l/w;
			long b=l%w;
			for(long i=a-1;i<=a+1;i++){
				for(long j=b-1;j<=b+1;j++){
					if(i>0 && i<h-1 && j>0 && j<w-1 && !hs2.contains(i*w+j)){
						int temp=0;
						
						for(long ii=i-1;ii<=i+1;ii++){
							for(long jj=j-1;jj<=j+1;jj++){
								if(hs1.contains(ii*w+jj))temp++;
							}
						}
						count[temp]++;
						count[0]--;
						hs2.add(i*w+j);
						
					}
				}
			}
		}
		for(int i=0;i<10;i++)System.out.println(count[i]);
	}
}

Measured memory_bytes: 213208
N = int(input())
A = [0 for k in range(int(N**0.5)+1)]

#N=1の処理
if N == 1:
  print(0)
  exit()
ans = 0


prime = [2]
for k in range(3, len(A), 2):
  if A[k] == 0:
    prime.append(k)
    for j in range(k, len(A), k):
      A[j] = 1
for p in prime:
  if N%p == 0:
    break
else: 
  print(1)
  exit()

used = []
use = []
#print(prime)
for p in prime:
  if p > N:
    break
  if N%p == 0:
    #print(p)
    ans += 1
    used.append(p)
    use.append(p)
    N = N // p
  np = p * p
  while N % np == 0:
    #print(np)
    ans += 1
    used.append(np)
    N = N // np
    np = np * p
    
#print(use)
#print(N)

for u in used:
  if N % u == 0:
    N = N // u
for u in used:
  if N % u == 0:
    N = N // u
for u in used:
  if N % u == 0:
    N = N // u
if N > 1:
  ans += 1
print(ans)    

Measured memory_bytes: 151012
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String ans = "Three";
        for(int i = 0; i < n; i++)
            if(sc.next().charAt(0) == 'Y')
                ans = "Four";
        System.out.println(ans);
    }
}

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

using namespace std;
using ll=int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi=vector<int>;
using vii=vector<vi>;
using vl=vector<ll>;
using vll=vector<vl>;
using tpi=tuple<int, int, int>;

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

    ll ans = 0;
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                bool f1 = false, f2 = false;
                for (int p = 0; p < N; p++) {
                    if (f1 && f2 && (S[p] - '0' == k)) {
                        ans++;
                        break;
                    }
                    if (f1 && (S[p] - '0' == j)) {
                        f2 = true;
                        continue;
                    }
                    if (S[p] - '0' == i) {
                        f1 = true;
                        continue;
                    }

                }
            }
        }
    }


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


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

typedef long long ll;
ll a, b, c;
int main()
{
	cin >> a >> b >> c;
	if (a > b) swap(a, b);
	if (b > c) swap(b, c);
	if (a & b & c & 1) cout << a * b;
    else cout << '0';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

int main() {
	ll n, x;
	cin >> n >> x;
	vector<ll> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	ll count = 0;
	if (a[0] > x) {
		count = a[0] - x;
		a[0] = x;
	}
	for (int i = 0; i < n - 1; i++) {
		if (a[i] + a[i + 1] > x) {
			int eat = a[i] + a[i + 1] - x;
			count += eat;
			a[i + 1] -= eat;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 1024
n = gets.to_i
ans = (1..n).map do
    a = (1..9).map { gets.chomp.split }
    b = (0..8).map do |i|
        (0..8).map do |j|
            t = a[i][j]
            ng = a[i].count(t) > 1 ||
                 a.transpose[j].count(t) > 1 ||
                 (i/3*3..i/3*3+2).to_a.product((j/3*3..j/3*3+2).to_a).count{|k, l| a[k][l] == t} > 1
            (ng ? "*" : " ") + t
        end
    end
    b.map(&:join).join "\n"
end
puts ans.join "\n\n"

Measured memory_bytes: 9180
#include <iostream>
#include <vector>
#include <algorithm>

#include <numeric>
using namespace std;

int main(void) {
     int k,n;
     cin >> k >> n;
     vector<int> a(n);
     vector<int> dis(n);

     for (int i = 0;i < n;i++){

          cin >> a[i];
     }
     
     dis[0] = k - a[n - 1] + a[0];
     for (int i = 0;i < n -1;i++){
          dis[i + 1] = a[i + 1] - a[i];
     }

     cout << accumulate(dis.begin(), dis.end(), 0) - *max_element(dis.begin(), dis.end()) << endl;
     
     
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define e edg
#define vis vissssssssssss
using namespace std;
struct edge{int go,next;} e[1000000];
int n,m,gg,vis[1000],f[1000][1000],ljb[1000],cnt,nn,c[1000],ma[1000][1000],num[1000][3];
void dfs(int x){
	vis[x]=1;
	num[nn][c[x]]++;
	for (int i=ljb[x];i;i=e[i].next){
		if (!vis[e[i].go]){
			c[e[i].go]=c[x]^1;
			dfs(e[i].go);
		}
		else{
			if (c[x]==c[e[i].go]) gg=1;
		}
	}
}
int ff(int x){
	return x*(x-1)/2;
}
int main(){
	scanf("%d%d",&n,&m);
	gg=0;
	for (int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		ma[x][y]=ma[y][x]=1;
	}
	for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (ma[i][j]==0){
		e[++cnt].go=j;e[cnt].next=ljb[i];ljb[i]=cnt;
		e[++cnt].go=i;e[cnt].next=ljb[j];ljb[j]=cnt;
	}
	int td=0;
	for (int i=1;i<=n;i++) if (!vis[i]){
		nn++;
		dfs(i);
	}
	if (gg){puts("-1");return 0;}
	f[0][0]=1;
	for (int i=0;i<nn;i++){
		for (int j=0;j<=n;j++){
			f[i+1][j+num[i+1][0]]|=f[i][j];
			f[i+1][j+num[i+1][1]]|=f[i][j];
		}
	}
	for (int i=n/2;i;i--) if (f[nn][i]){
		printf("%d",ff(i)+ff(n-i));
		return 0;
	}
}

Measured memory_bytes: 8576
#include <cstdio>
#include <cmath>
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
	double r;

	cin >> r;

	double S = M_PI * r * r;
	double L = 2 * M_PI * r;

	printf("%f %f\n", S, L);

	return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename A,typename B>istream&operator>>(istream&is,pair<A,B> &p){is>>p.fi>>p.se;return is;}
template<typename A,typename B>ostream&operator<<(ostream&os,const pair<A,B> &p){os<<"("<<p.fi<<","<<p.se<<")";return os;}
template<typename T>istream&operator>>(istream&is,vector<T> &t){REP(i,t.size())is>>t[i];return is;}
template<typename T>ostream&operator<<(ostream&os,const vector<T>&t){os<<"{";REP(i,t.size()){if(i)os<<",";os<<t[i];}cout<<"}";return os;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n=5;
    vi vec(n);
    cin>>vec;
    int k;
    cin>>k;
    REP(i,n){
        REP(j,n){
            if(abs(vec[i]-vec[j])>k){
                cout<<":("<<endl;
                return 0;
            }
        }
    }
    cout<<"Yay!"<<endl;
    return 0;
}

Measured memory_bytes: 256