akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repdm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)

int main()
{

  ll N, K;
  cin >> N >> K;

  ll ans = 0;

  if (K % 2 == 1)
  {
    ll num = floor(N / K);
    ans += pow(num, 3);
  }
  else if (K % 2 == 0)
  {
    ll num = floor(N / (K / 2));
    ll numK = floor(N / K);
    if (numK * 2 == num)
    {
      ans += pow(numK, 3) * 2;
    }
    else
    {
      ans += pow(numK, 3);
      ans += pow(num - numK, 3);
    }
  }

  cout << ans;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <cstring>
#include <ctype.h>
#include<stdlib.h>

#define flin            freopen("input.txt", "r", stdin); 
#define flout           freopen("output.txt", "w", stdout);
#define ll              long long
#define ull             unsigned long long
#define fastio          ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define nl              '\n'
#define nll             '\0'
#define pb              push_back
#define bdyptb          return 0;
#define sorted(x)       sort(x.begin(), x.end())
#define reversed(x)     reverse(x.begin(), x.end())
#define all(x)          x.begin(), x.end()
#define mset(a, b)      memset(a, b, sizeof(a));
#define testcase        ll t,tt; cin>>tt; for(t=1;t<=tt;t++)

#define pi acos(-1.00)   
#define mx 1000007

using namespace std;


int main()
{
    fastio;
    int n;
    cin>>n;
    string in;
    int ac=0,wa=0,tle=0,re=0;
    for(int i=0; i<n; i++)
    {
        cin>>in;
        if(in=="AC")ac++;
        else if(in=="WA")wa++;
        else if(in=="TLE")tle++;
        else re++;

    }

    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n",ac,wa,tle,re);

}

Measured memory_bytes: 3748
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class A {
    static StreamWriter Out = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    static void Main(string[] args) {
        int[] X = new int[] { 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;
        Input(out K);
        Print(X[K - 1]);
        Out.Flush();
    }
    static T ChangeT<T>(string s) => (T)Convert.ChangeType(s, typeof(T));
    static void Input<A>(out A a) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
    }
    static void Input<A, B>(out A a, out B b) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
    }
    static void Input<A, B, C>(out A a, out B b, out C c) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
    }
    static void Input<A, B, C, D>(out A a, out B b, out C c, out D d) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
    }
    static void Input<A, B, C, D, E>(out A a, out B b, out C c, out D d, out E e) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
    }
    static void Input<A, B, C, D, E, F>(out A a, out B b, out C c, out D d, out E e, out F f) {
        var words = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries);
        a = ChangeT<A>(words[0]);
        b = ChangeT<B>(words[1]);
        c = ChangeT<C>(words[2]);
        d = ChangeT<D>(words[3]);
        e = ChangeT<E>(words[4]);
        f = ChangeT<F>(words[5]);
    }
    static void Inputs<T>(out T[] array) {
        array = Console.ReadLine().Split(new[] { ' ' }, options: StringSplitOptions.RemoveEmptyEntries).Select(s => ChangeT<T>(s)).ToArray();
    }
    static void Print<T>(T s) => Out.WriteLine(s);
    static void Print<T>(params T[] s) => Out.WriteLine(string.Join(" ", s));
    static void Print<T>(IEnumerable<T> e) => Out.WriteLine(string.Join(" ", e));
}

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

int main()
{
    int n, m;
    int i, j;
    long long int x = 1, y = 1, ans;
    
    cin >> n >> m;
    
    if(abs(n-m) >= 2) {
        cout << "0\n";
        
    } else {
        for(i = 1; i <= n; i++) {
            x = (x * i) % (1000000000+7);
        }
        for(j = 1; j <= m; j++) {
            y = (y * j) % (1000000000+7);
        }
        
        ans = (x * y) % (1000000000+7);
        if(abs(n-m) == 0) {
            ans = (ans * 2) % (1000000000+7);
        }
        ans = ans % (1000000000+7);
        
        cout << ans << "\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans1 = max(A)
if A[1] == 0:
    print(ans1, 0)
for i in range(n):
    if i == 0:
        pass
    elif i == 1:
        ans2 = A[i]
        now_div = abs(ans1/2 - ans2)
    else:
        chk = A[i]
        chk_div = abs(ans1/2 - chk)
        if chk_div > now_div:
            print(ans1, ans2)
            exit()
        if abs(ans1/2 - chk) < abs(ans1/2 - ans2):
            ans2 = chk
            now_div = abs(ans1/2 - ans2)

Measured memory_bytes: 14052
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<string, int>> v(n);
  rep(i, n) cin >> v[i].first >> v[i].second;
  string x;
  cin >> x;

  ll res = 0;
  bool flag = false;
  rep(i, n){
    if(flag) res += v[i].second;
    if(x == v[i].first) flag = true;
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int h,n;
  cin >> h >> n;
  vector<int> A(n);
  int sum = 0;
  for (int i = 0; i < n; i++){
    cin >> A[i];
    sum += A[i];
  }
  if (h <= sum){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3768
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int sum = scan.nextInt();
        for (int i = 1; i <= sum; i++) {
        	String x = String.valueOf(i);
            if (i % 3 == 0 || x.indexOf("3") != -1){
            	System.out.print(" " + i);
            }
        }
        System.out.println("");
	}
}

Measured memory_bytes: 30056
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        char[] s = sc.next().toCharArray();
        int ko = 0;
        int ka = 0;
        for (int i = 0 ; i < n ; i++) {
            if (s[i] == 'a') {
                if (ko < a + b) {
                    System.out.println("Yes");
                    ko++;
                } else {
                    System.out.println("No");
                }
            }
            if (s[i] == 'b') {
                if (ko < a + b && ka < b) {
                    System.out.println("Yes");
                    ko++;
                    ka++;
                } else {
                    System.out.println("No");
                }
            }
            if (s[i] == 'c') {
                System.out.println("No");
            }
        }
    }

}

Measured memory_bytes: 34252
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+5;
char str[MAXN];
int sa[MAXN],ra[MAXN],height[MAXN];
int wa[MAXN],wb[MAXN],wc[MAXN],wd[MAXN];
int read()
{
    int s=1,x=0;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
    while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
    return x*s;
}
void GetSaRa(int n,int m)//倍增法 nlogn 
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(int i=0;i<m;++i) wd[i]=0;
    for(int i=0;i<n;++i) wd[x[i]=str[i]]++;
    for(int i=1;i<m;++i) wd[i]+=wd[i-1];
    for(int i=n-1;i>=0;--i) sa[--wd[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p)
    {
        for(p=0,i=n-j;i<n;++i) y[p++]=i;
        for(i=0;i<n;++i) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<n;++i) wc[i]=x[y[i]];
        for(i=0;i<m;++i) wd[i]=0;
        for(i=0;i<n;++i) wd[wc[i]]++;
        for(i=1;i<m;++i) wd[i]+=wd[i-1];
        for(i=n-1;i>=0;--i) sa[--wd[wc[i]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;++i)
        x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
    }
}
void GetHeight(int n)
{
    int i,j,k=0;
    for(i=1;i<=n;++i) ra[sa[i]]=i;
    for(i=0;i<n;height[ra[i++]]=k)
    for(k?k--:0,j=sa[ra[i]-1];str[i+k]==str[j+k];++k);
}
bool C(int n,int k)//差分数组中是否存在两个长度为k的子串是相同的 
{
    int maxi=-1,mini=1<<30;//下标 
    for(int i=1;i<=n;++i)
    {
        if(height[i]<k)//分组
        maxi=sa[i],mini=sa[i];
        else//组内是否有相同长度超过k的子串且距离大于k 
        {
            maxi=max(maxi,max(sa[i],sa[i-1]));
            mini=min(mini,min(sa[i],sa[i-1]));
            if(maxi-mini>=k) return true;
        }
    }
    return false;
}
int main()
{
    int len;
   	scanf("%d",&len);
    scanf("%s",str);
    str[len]=0;
    GetSaRa(len+1,300);
    GetHeight(len);
//    for(int i=0;i<len;++i) cout<<str[i]<<' ';cout<<endl;
//    for(int i=1;i<=len;++i) cout<<height[i]<<' ';cout<<endl;
    int l=-1,r=len+1,mid;
    while(l+1!=r)
    {
        mid=(l+r)>>1;
        if(C(len,mid)) l=mid;
        else r=mid;    
    } 
    cout<<l<<endl;
    return 0;
}

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


/* エイリアス */
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define endl '\n'

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace


/* 関数マクロ */
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n, m) for (ll i = n; i <= m; ++i)
#define rep3(i, n, m) for (ll i = n; i >= m; --i)
#define all(v) v.begin(), v.end()
#define si(v) int(v.size())
#define UNIQUE(v) sort(all(v)), v.erase(unique(all(v)),v.end())


/* 定数 */
const ll mod = 1e9 + 7;
const ll infll = (1LL << 62) - 1;
const ll inf = (1LL << 30) - 1;


/* その他 */
template<class S, class T> inline bool chmax(S &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class S, class T> inline bool chmin(S &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;


signed main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  
  int a, b; cin >> a >> b;
  cout << a * b << endl;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector <ll> A(N);
    loop(i,0,N) cin >> A[i];
    vector <ll> B=A;
  	sort(A.begin(),A.end());
  	loop(i,0,N)
    {
      if (B[i]!=A[N-1]) cout << A[N-1] << "\n";
      else cout << A[N-2] << "\n";
    }
    return 0;
}

Measured memory_bytes: 4736
cards = [[False for i in range(13)] for j in range(4)]
pattern = ['S', 'H', 'C', 'D']

n = int(input())
for i in range(n):
    ch, rank = map(str, input().split())
    rank = int(rank)
    cards[pattern.index(ch)][rank - 1] = True

for i in range(4):
    for j in range(13):
        if cards[i][j] == False:
            print(pattern[i], j + 1)


Measured memory_bytes: 5604
from itertools import product
N = int(input())
ans = 0
for k in range(3,11):
    for i in product([0,3,5,7],repeat=k):
        if set(i) != {3,5,7}:
            continue
        if sum([10**j*v for j,v  in enumerate(i)]) <= N:
            ans += 1
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////




int main() {

	ll N, i;
	cin >> N >> i;
	cout << N - i + 1;
	system("PAUSE");
}

Measured memory_bytes: 504
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod ll(1e9+7)
void solve(){
	ll n;
	cin>>n;
	vector<ll> arr(n);
	vector<ll> freq(n);
	ll prod=1;
	for( ll&x:arr)cin>>x,freq[x]++;
	if(freq[0]>=2){cout<<0<<endl;return;}
	if(n%2==0 and freq[0]>1){cout<<0<<endl;return;}
	for(ll i=0;i<freq.size();i++){
		if(freq[i]>2){
			cout<<0;return;
		}
		if(freq[i])
		prod=(prod%mod*(freq[i]%mod))%ll(1e9+7);
	}
	cout<<prod<<endl;

}


int main(){
	solve();
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>

using namespace std;

const long long INF = 1LL<<30;

long long solve(
    const int n,
    const int m,
    const vector<long long> &a,
    const vector<long long> &b,
    const vector<vector<long long>> &C) {
    vector<int> x(m);
    for (int i = 0; i < C.size(); ++i) {
        int mask = 0;
        for (int j = 0; j < C[i].size(); ++j) {
            mask |= 1 << (C[i][j] - 1);
        }
        x[i] = mask;
    }
    vector<vector<long long>> dp(m+1, vector<long long>(2<<n));
    for (int i = 0; i < dp.size(); ++i) {
        for (int j = 0; j < dp[i].size(); ++j) {
            dp[i][j] = INF;
        }
        dp[i][0] = 0;
    }
    for (int i = 0; i < m; ++i) {
        for (int mask = 0; mask < (1 << n); ++mask) {
            dp[i+1][mask] = min(dp[i+1][mask], dp[i][mask]);
            int s = mask | x[i];
            dp[i+1][s] = min(dp[i+1][s], dp[i][mask] + a[i]);
        }
    }
    long long best = dp[m][(1 << n)-1];
    return (best == INF) ? -1 : best;
}

int main() {
    int n, m; cin >> n >> m;
    vector<long long> a(m), b(m);
    vector<vector<long long>> C;
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        vector<long long> c(b[i]);
        for (int j = 0; j < b[i]; ++j) {
            cin >> c[j];
        }
        C.push_back(c);
    }
    cout << solve(n, m, a, b, C) << endl;
    return 0;
}

Measured memory_bytes: 64512
#include<stdio.h>
int main(void)
{
  int A,B,C,D;
  scanf("%d %d %d %d",&A,&B,&C,&D);
  if(A*B>C*D){
    printf("%d\n",A*B);
  } else {
    printf("%d\n",C*D);
  }

  return 0;
}


Measured memory_bytes: 128
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

# n = int(input())
# 
# s = input()

A, B = list(map(int, input().split()))
ans = -1
for n in range(1, 50000):
    if math.floor(n * 0.08) == A and math.floor(n * 0.1) == B:
        ans = n
        break
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>

#include <atcoder/dsu>

using namespace std;
using namespace atcoder;
#define rep(i,l,r) for(int i = l; i < r; i++)

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

    dsu d(n);

    rep(i, 0, q) {
        int t, u, v;
        cin >> t >> u >> v;

        if (t == 0) {
            d.merge(u, v);
        } else {
            cout << (d.same(u, v)) << endl;
        }
    }
}


Measured memory_bytes: 3540
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N)
res = 1
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
  res = max(res, uf.Count(u))
print(res)

Measured memory_bytes: 82720
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define loop(i,a,b) for(ll i=a; i<b; i++)
#define revloop(i,a,b) for(ll i=a; i>=b; i--)
#define pb push_back
#define vl vector<ll>
#define vvl vector<vl>
#define pl pair<ll,ll>
#define vpl vector<pl>
#define all(c) (c).begin(), (c).end()
#define sz(a) ((a).size())
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i!=(c).end(); i++))
#define mp make_pair
#define ss second
#define ff first
#define ld long double
const ll INF = 1e13;
const ll N = 2e5+5;
ll mod= 1000000007;
/*bool prime(ll x)
{
	if(x<2) return false;
	for(ll i=2; i*i<=x; i++) if(x%i==0) return false;
	return true;
}
vl fac(N);
void fact()
{
	fac[0]=1;
	loop(i,1,N) fac[i]=(fac[i-1]*i)%mod;
}
*/
ll h[N], b[N],n,dp[N],num=2;
struct node{
	ll left =-1, right=-1,data=0;
	node(){
		left=-1;
		right=-1;
		data=0;
	}
}seg[4*N];
ll query(ll idx, ll l, ll r, ll ql, ll qr)
{
	if(idx<=0 || l>qr || r<ql ) return 0;
	if(ql<=l && qr>=r) return seg[idx].data;
	ll mid = (l+r)/2;
	return max(query(seg[idx].left,l,mid,ql,qr),query(seg[idx].right,mid+1,r,ql,qr));
}
void update(ll idx, ll l, ll r, ll qp, ll qd)
{
	if(l==r)
	{
		seg[idx].data=max(qd,seg[idx].data);
		return;
	}
	ll mid = (l+r)/2;
	if(qp<=mid)
	{
		if(seg[idx].left==-1) seg[idx].left=num++;
		update(seg[idx].left,l,mid,qp,qd);
		seg[idx].data=max(seg[idx].data,seg[seg[idx].left].data);
	}
	else
	{
	   if(seg[idx].right == -1) seg[idx].right = num++;
       update(seg[idx].right,mid+1,r,qp,qd);
       seg[idx].data = max(seg[idx].data,seg[seg[idx].right].data);
	}
}
void solve()
{
 cin>>n;
 loop(i,1,n+1) cin>>h[i];
 loop(i,1,n+1) cin>>b[i];
 loop(i,1,n+1) {
 dp[i]=b[i]+query(1,1,n,0,h[i]-1);
 update(1,1,n,h[i],dp[i]);
}
cout<<query(1,1,n,1,n)<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--) solve();
 return 0;
}

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

using namespace std;

struct RMQ {
  int N;
  vector<long long> dat;

  RMQ(int n) {
    N = 1;
    while (N < n) N *= 2;
    dat.resize(N * 2, 1e18);
  }

  void update(int k, long long v) {
    dat[k + N] = v;
    for (int i = k + N >> 1; i > 0; i >>= 1) {
      dat[i] = min(dat[i * 2], dat[i * 2 + 1]);
    }
  }

  long long query(int l, int r) {
    long long ans = 1e18;
    l += N;
    r += N;
    while (l < r) {
      if (l & 1) ans = min(ans, dat[l++]);
      if (r & 1) ans = min(ans, dat[--r]);
      l >>= 1;
      r >>= 1;
    }
    return ans;
  }
};


int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  RMQ rmq(n);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    rmq.update(i, a[i] - i);
    if (i > 0 && a[i] == a[i - 1] + 1) {
      ans++;
    } else {
      ans += a[i];
    }
  }
  for (int i = 0; i < n; i++) {
    if (i - a[i] < 0) {
      cout << -1 << endl;
      return 0;
    }
    if (rmq.query(i - a[i], i) < a[i] - i) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 5120
#include <stdio.h>

void bubble_sort_s(int *data, int n);
void bubble_sort_b(int *data, int n);

int main(void)
{
	int s_seisuu;
	int b_seisuu;
	int a[8];
	int cp_a[8];
	int n;
	int i;
	
	scanf("%d", &n);
	
	while (n-- > 0){
		scanf("%d", &s_seisuu);
		
		for(i = 0; i < 8; i++){
			a[i] = s_seisuu % 10;
			cp_a[i] = a[i];
			s_seisuu /= 10;
		}
		
		bubble_sort_s(a, 8);
		bubble_sort_b(cp_a, 8);
		
		s_seisuu = b_seisuu = 0;
		
		for (i = 0; i < 8; i++){
			s_seisuu = s_seisuu * 10 + a[i];
			b_seisuu = b_seisuu * 10 + cp_a[i];
		}
		
		printf("%d\n", b_seisuu - s_seisuu);
	}
	return (0);
}

void bubble_sort_s(int *data, int n)
{
	int i, j;
	
	for (i = 0; i < n - 1; i++){
		for(j = 0; j < n - i - 1; j++){
			if (data[j] > data[j + 1]){
				data[j] += data[j + 1];
				data[j + 1] = data[j] - data[j + 1];
				data[j] = data[j] - data[j + 1];
			}
		}
	}
}

void bubble_sort_b(int *data, int n)
{
	int i, j;
	
	for (i = 0; i < n - 1; i++){
		for(j = 0; j <n - i - 1; j++){
			if (data[j] < data[j + 1]){
				data[j] += data[j + 1];
				data[j + 1] = data[j] - data[j + 1];
				data[j] = data[j] - data[j + 1];
			}
		}
	}
}

Measured memory_bytes: 0
#include "stdio.h"
#include "string.h"



int main(void){
	int A, B, C, D;

	scanf("%d%d%d%d", &A, &B, &C, &D);

	if(A+B == C+D)
	{
		printf("Balanced\n");
		return 0;
	}else if(A+B < C+D){
		printf("Right\n");
		return 0;
	}else{
		printf("Left\n");
		return 0;
	}

	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
using namespace std;
int main(void)
{
	unsigned int s,a[200000],x,b[200000];
	int n,i;
	scanf("%d",&n);
	s=0;
	for(i=0;i<n;i++)	{
		scanf("%u",&a[i]);
		s^=a[i];
	}
	for(i=0;i<n;i++)	{
		b[i]=s^a[i];
	}
	printf("%u",b[0]);
	for(i=1;i<n;i++)	printf(" %u",b[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 4024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vp;
typedef pair<int,int> pii;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//cout << 'H' << endl;
//next_permutation(ALL(p));
//typedef priority_queue<int> pque;//これは大きい順
//typedef priority_queue<int, vector<int>, greater<int>> pque;//これは小さい順
//factorizeは、素因数分解用の関数

int main(){
	int n,m;
  cin >> n >> m;
  vector<int> h(n);
  rep(i,n) cin >> h[i];

  vector<vector<int>> to(n,vector<int>());
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--;b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  int ans = 0;
  rep(i,n) {
    bool good = true;
    map<int,int> mp;
    rep(j,to[i].size()){
      mp[to[i][j]]++;
    }
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
      if(h[i] <= h[itr->first]){
        good = false;
        break;
      }
    }
    if(good) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 10940
#include<iostream>
#include <algorithm>
#include<string>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;
int main() {
    string n;
    cin>>n;
    string ans="No";
    if(n[0]=='7')ans="Yes";
    if(n[1]=='7')ans="Yes";
    if(n[2]=='7')ans="Yes";
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define In_The_Name_Of_Allah_The_Merciful ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define Alhamdulillah return 0;
#define all(v) v.begin(),v.end()
#define debug(n) cerr << "[" << #n << " = " << n << "]" << endl 

const int N = 1e5;
ll dp[N];
int n , a[N];

ll calc (int idx){

    if (idx == n-1)
        return 0;

    ll &ret = dp[idx];
    if (~ret)
        return ret;

    ret = calc(idx+1) + abs(a[idx] - a[idx+1]);

    if (idx+2 < n)
        ret = min (ret , calc(idx+2) + abs(a[idx] - a[idx+2]));

    return ret;

} 

void Suhaib_Sawalha (){

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

    memset(dp,-1,sizeof dp);
    cout << calc(0);

}

int main(){
                                In_The_Name_Of_Allah_The_Merciful   /* بسم الله الرحمن الرحيم  */
#ifndef ONLINE_JUDGE
    freopen("SuhaibSawalha1.txt","r",stdin);
#endif
//int _;for(cin>>_;_;--_,cout<<'\n')
        Suhaib_Sawalha();
                                         Alhamdulillah                    /* الحمد لله */
}

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

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

  string s;
  cin >> s;

  auto a = std::find(s.begin(), s.end(), 'A');
  auto z = std::find(s.rbegin(), s.rend(), 'Z');
  int beginoffset = &*a - s.data();
  int endoffset = &*z - s.data();
  cout << (endoffset - beginoffset + 1) << "\n";
}


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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second

#ifdef OJ
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#else
#define debug(x)
#define debugv(x)
#endif

#define all(x) (x).begin(), (x).end()
#define rsort(x) sort((x).rbegin(), (x).rend())
#define sz(x) ((int)x.size())
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n, e) for (int i = (int)(n); i >= (int)(e); --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << (x) << '\n'; return ;}while(0)

const int MOD = 1e9+7;
const int MAXN = 2e6+3;
const int INF = 1e9;

int solve() {
    int n; cin >> n;
    vector<int> m(n+1);
    fore(x,1,n) {
        if(6LL*x*x > n) break;
        fore(y,x,n) {
            if(1LL*x*x + 2LL*y*y + 2LL*x*y > n) break;
            fore(z,y,n) {
                LL v = 1LL*x*x + 1LL*y*y + 1LL*z*z + x*y + y*z + x*z;
                if(v > n) break;
                if(x < y && y < z) m[v] += 6;
                else if(x < y && y == z) m[v] += 3;
                else if(x == y && y < z) m[v] += 3;
                else m[v] += 1;
            }
        }
    }
    fore(i,1,n) cout << m[i] << '\n';
    return 0;
} 

int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int ntest = 1;
    //cin >> ntest;
    fori(test, ntest) {
        solve();
    }

    return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
long long MOD = 1e9 + 7;
constexpr ll INF = 1e17;

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

    int n;
    cin >> n;

    for (int i = 1; i <= 9; i++)
    {
        if (n % i == 0) {
            if (n / i <= 9) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int na, nb, m;
  cin >> na >> nb >> m;
  vector<int> a(na);
  for (auto&& e : a) {
    cin >> e;
  }
  vector<int> b(nb);
  for (auto&& e : b) {
    cin >> e;
  }
  int res = *min_element(begin(a), end(a));
  res += *min_element(begin(b), end(b));
  while (m--) {
    int x, y, c;
    cin >> x >> y >> c;
    --x, --y;
    res = min(res, a[x] + b[y] - c);
  }
  cout << res << '\n';
}


Measured memory_bytes: 1024
while True:
    n = int(input())
    if n == 0: 
        break
    
    a = [0]*10

    for i in range(n): 
        a[int(input())] += 1
    for i in range(10):
        if a[i] == 0: 
            print("-")
        else: 
            print("*"*a[i])


Measured memory_bytes: 5624
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
void print_container(T &container, string delim=" ") {
    bool first = true;
    for(auto &t: container){
        if(!first){
            cout << delim;
        }
        first = false;
        cout << t;
    }
    cout << endl;
}

const int MOD = 1e9 + 7;
int main() {
    ll n, k;
    cin >> n >> k;
    vector<int> a(n);
    REP(i, n){
        cin >> a[i];
    }

    ll ans = 0;
    vector<ll> bef(n), aft(n);
    REP(i, n){
        FOR(j, 0, i){
            if(a[i] > a[j])
                bef[i]++;
        }
        FOR(j, i+1, n){
            if(a[i] > a[j])
                aft[i]++;
        }

        ans = (ans + ((k*(k+1)/2)%MOD) * aft[i] + ((k*(k-1)/2)%MOD) * bef[i]) % MOD;
    }

    cout << ans << endl;



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define LL long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
//
int main(){
  int X;
  cin>>X;
  if(X%7==1){
    cout<<"fri"<<endl;
  }else if(X%7==2){
    cout<<"sat"<<endl;
  }else if(X%7==3){
    cout<<"sun"<<endl;
  }else if(X%7==4){
    cout<<"mon"<<endl;
  }else if(X%7==5){
    cout<<"tue"<<endl;
  }else if(X%7==6){
    cout<<"wed"<<endl;
  }else{
    cout<<"thu"<<endl;
  }
  return 0;
}



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

# define REP(i,n) for (int i=0;i<(n);++i)
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){cout << (v[i]) << " ";} cout << endl;
typedef long long int ll;

int main(void) {

  string s;
  cin >> s;

  int md = 2019;

  int now = 0;
  int ten = 1;
  vector<int> mp(2019, 0);
  for(int i = s.size()-1; i >= 0; i--){
    (now += (s[i] - '0') * ten) %= md;
    mp[now]++;
    (ten *= 10) %= md;
  }

  ll ans = mp[0];
  for(auto m : mp) {
    ans += m * (m - 1) / 2;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3748
// Author: H. Gakhar
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, w;
	cin>>n>>w;
	ll dp[w+1]={};
	for(int i=0; i<n; i++) 
	{
		ll m, v;
		cin>>m>>v;
		for(int i=w-m; i>=0; i--)
		{
			dp[i+m]=max(dp[i+m], dp[i]+v);
		}
		//for(auto i: dp) cout<<i<<" ";
		//	cout<<"\n";
	}
	cout<<dp[w];
	return 0;
}
 

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include <map>
#include <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
#include <complex>
#include <omp.h>
using namespace std;
#define eps 0.000001
#define LONG_INF 10000000000000
#define GOLD 1.61803398874989484820458
#define seg_size 65536*4
#define REP(i,n) for(long long i = 0;i < n;++i)
unsigned long xor128() {
	static unsigned long x = time(NULL), y = 362436069, z = 521288629, w = 88675123;
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}


const string YES = "Yes";
const string NO = "No";

void solve(long long A, long long B, long long C){
    if(A == B&&B == C) cout << YES << endl;
    else cout << NO << endl;
}

// Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(int i =(a);i<(n);i++)
#define urep(i,a,n) for(int i = (a);i>(n);i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;

int N;
ll A[200000];
int main(){
	cin >> N;
	rep(i, 0, N){
		cin >> A[i];
	}
	ll lenge = 0;
	int oldpos = 0;
	ll num = 0;
	ll xornum = 0;
	ll ans = 0;
	rep(i, 0, N) {
		num += A[i];
		xornum ^= A[i];
		if (num == xornum) {
			lenge++;
			ans += lenge;
		}
		else {
			num -= A[oldpos];
			xornum ^= A[oldpos];
			num -= A[i];
			xornum ^= A[i];
			lenge--;
			i--;
			oldpos++;
		}
	}
	cout << ans << endl;
	cin >> ans;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;
using vvll = vector<vector<lli>>;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

vll graph[601];
double dist[601] = {};

int main(void) {

	lli N, M;
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		lli s, t;
		cin >> s >> t;

		graph[s].push_back(t);
	}

	double answer = 1000;

	for (int target = 1; target <= N; target++) {

		dist[N] = 0;

		for (int i = N - 1; i > 0; i--) {
			dist[i] = 0;
			double maxi = 0;
			for (auto t : graph[i]) {
				dist[i] += dist[t];
				CHMAX(maxi, dist[t]);
			}
			if (target == i && graph[i].size() > 1) {
				dist[i] -= maxi;
				dist[i] /= (graph[i].size() - 1);
			}
			else {
				dist[i] /= graph[i].size();
			}
			dist[i] += 1;
		}

		CHMIN(answer, dist[1]);
	}
	//ABC144_E
	//解説動画AC
	//DAGだと気づけなかったところが精進不足を感じさせる。
	//Si > Tiという条件をみたら==DAGをすぐに意識できるようにする。
	//DPで期待値距離を求めるところは詰まらずかけた。
	//そこから、行先の期待値が一番大きいのを
	//消せばいいというところまで発想の飛躍が必要だった。
	//実装もちょい詰まった。
	//最終的に計算時に試行している頂点なら最大を引くようにした。

	COUT(std::setprecision(15) << answer);



	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926525
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

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

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  string s;cin>>s;
  for(int i=-1;i<=1;i+=2){
    for(int j=-1;j<=1;j+=2){
      for(int k=-1;k<=1;k+=2){
        if((int)(s[0]-48)+(int)(s[1]-48)*i+(int)(s[2]-48)*j+(int)(s[3]-48)*k==7){
          string ss;
          ss+=s[0];
          ss+=((i==-1)?'-':'+');
          ss+=s[1];
          ss+=((j==-1)?'-':'+');
          ss+=s[2];
          ss+=((k==-1)?'-':'+');
          ss+=s[3];
          ss+="=7";
          P(ss);
          return 0;
        }
      }
    }
  }
  return 0;
}


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

using namespace std;

int cnt = 0;
vector<int>G;
void insertionsort(int A[], int n, int g)
{
    int i,v,j;
    for(i = g;i<n;i++)
    {
        v = A[i];
        j = i-g;
        while(j>=0 && A[j] >v)
        {
            A[j+g] = A[j];
            j=j-g;
            cnt++;
        }
        A[j +g]= v;
    }
}

void shellsort(int A[], int n)
{
    for(int h =1;;)
    {
        if(h>n)break;
        G.push_back(h);
        h = 3*h+1;
    }
    for(int i= G.size()-1;i>=0;i--)
    {
        insertionsort(A,n,G[i]);
    }

}

int main()
{
   int n;
   int A[1000000];
   cin >> n;
   for(int i=0;i<n;i++)
    scanf("%d", &A[i]);
   shellsort(A,n);
   insertionsort(A,n,1);
   cout <<G.size()<<endl;
   for(int i =G.size()-1;i>=0;i--)
   {
       printf("%d",G[i]);
    if(i)
        printf(" ");
   }
   printf("\n");
   cout <<cnt<<endl;
   for(int i =0;i<n;i++)
    cout <<A[i]<<endl;



    return 0;
}



Measured memory_bytes: 7184
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    A=LLIN(3)
    M=I()
    B=[[0]*3 for _ in range(3)]
    for _ in range(M):
        b = I()
        for i in range(3):
            for j in range(3):
                if A[i][j] == b:
                    B[i][j] = 1
    for i in range(3):
        if B[i]==[1]*3:
            print("Yes")
            return
        if [B[0][i],B[1][i],B[2][i]] == [1]*3:
            print("Yes")
            return
    if [B[0][0],B[1][1],B[2][2]] == [1]*3:
        print("Yes")
        return
    if [B[0][2],B[1][1],B[2][0]] == [1]*3:
        print("Yes")
        return
    print("No")
if __name__ == '__main__':
    main()

Measured memory_bytes: 66156
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int r[200000];
int n;

int main()
{
    memset(r,0,sizeof(r));
    cin>>n;
    int i;
    for(i=0;i<n;i++){
        cin>>r[i];
    }
    int minnum=r[0];
    int maxnum=-2000000000;
    for(i=1;i<n;i++){
        maxnum=max(maxnum,r[i]-minnum);
        minnum=min(minnum,r[i]);
    }
    cout<<maxnum<<endl;
    return 0;
}

Measured memory_bytes: 3872
#include <stdio.h>
#define swap(a, b) do{int t=a; a=b; b=t;}while(0)

int main(){
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  swap(a, b);
  swap(a, c);
  printf("%d %d %d\n", a, b, c);
  return 0;
}


Measured memory_bytes: 128
//package Atcoder;
import java.util.*;
import java.io.*;
public class Main
{
	static final int mod=(int)1e9+7;
	static final int inf=(int)1e9;
	static final long INF=(long)1e18;
	public static void main(String[] args)
	{
		FastScanner fs=new FastScanner();
		int dist=fs.nextInt();
		int req=fs.nextInt();
		int time=fs.nextInt();
		if(dist/time==req)
		{
			if(dist%time==0)
				System.out.println("Yes");
			else
				System.out.println("No");
		}
		else if(dist/time<req)
			System.out.println("Yes");
		else
			System.out.println("No");
	}
}
class FastScanner 
{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() 
		{
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
			
		}
		
		long pow(long x,long n)
		{
			long res=1;
			while(n>0)
			{
			   	if(n%2!=0)
			   	{
			   		res=(res*x);n--;
			   	}
			   	else
			   	{
			   		x=(x*x);n/=2;
			   	}
			}
			return res;
		}
		int gcd(int a,int b)
		{
			if(b==0)
			{
				return a;
			}
			return gcd(b,a%b);
		}
		long longgcd(long a,long b)
		{
			if(b==0)
			{
				return a;
			}
			return longgcd(b,a%b);
		}
		int[] sort(int arr[])
		{
			ArrayList<Integer> list = new ArrayList<Integer>();
			for(int i:arr)list.add(i);
			Collections.sort(list);
			for(int i=0;i<arr.length;i++)
			{
				arr[i]=list.get(i);
			}
			return arr;
		}
		char[] charsort(char arr[])
	        {
	    	ArrayList<Character> list = new ArrayList<>();
	    	for(char c:arr)list.add(c);
	    	Collections.sort(list);
	    	for(int i=0;i<list.size();i++)
	    	{
	    		arr[i]=list.get(i);
	    	}
	    	return arr;
	        }
		long[] longsort(long arr[])
		{
			ArrayList<Long> list = new ArrayList<Long>();
			for(long i:arr)list.add(i);
			Collections.sort(list);
			for(int i=0;i<arr.length;i++)
			{
				arr[i]=list.get(i);
			}
			return arr;
		}
		public int nextInt() 
		{
			return Integer.parseInt(next());
		}
		public int[] readArray(int n)
		{
			int[] arr=new int[n];
			for (int i=0; i<n; i++) arr[i]=nextInt();
			return arr;
		}	
		public long nextLong()
		{
			return Long.parseLong(next());
		}
		public long[] longreadArray(int n) 
		{
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
}

Measured memory_bytes: 32924
#include<cstdio>
#include<vector>


using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;


int main(void)
{
	int w, h;
	int dx[]={ 0, 1, 0,-1, 0};
	int dy[]={ 0, 0,-1, 0, 1};

	while(scanf("%d%d", &h, &w)==2)
	{
		vvi s(h), n(h);
		for(int y=0;y<h;y++)
		{
			s[y].resize(w);
			n[y].resize(w);
		}
		for(int y=0;y<h;y++)
		{
			char buf[w+2];
			scanf("%s", buf);
			for(int x=0;x<w;x++)
			{
				s[y][x]=buf[x];
				if(buf[x]=='#')
				{
					for(int i=0;i<5;i++)
					{
						int nx=x+dx[i];
						int ny=y+dy[i];
						if(nx<0 || w<=nx || ny<0 || h<=ny) continue;
						n[ny][nx]++;
					}
				}
			}
		}
		int ans=1;
		for(int y=0;y<h;y++)
		{
			for(int x=0;x<w;x++)
			{
				if(s[y][x]=='#' && n[y][x]==1) ans=0;
//				printf("%d ", n[y][x]);
			}
//			printf("\n");
		}
		printf("%s\n", ans?"Yes":"No");
	}

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b,c,d,e,f;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  if(a<b)e=a;
  else e=b;
  if(c<d)f=c;
  else f=d;
  printf("%d\n",e+f);
  return 0;
}

Measured memory_bytes: 128
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

int N,i,l,r,ans;
inline void solve(){
  IN(N);
  REP(i,N){
    IN2(l,r);
    ans+=(r-l+1);
  }
  OUT(ans);
}

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


Measured memory_bytes: 256
program prob1
    implicit none
    character(len=12)::c
    character(len=13)::S
    read(*,*) c
    S(1:4) = c(1:4)
    S(5:5) = " "
    S(6:13) = c(5:12)
    write(*,'(a)') S
    stop
end program

Measured memory_bytes: 2888
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	cin>>n>>k;
	long long ans=k;
	if(n>1)
	{
		for(int i=1;i<=n-1;i++)
			ans*=k-1;
	}
	cout<<ans<<endl; 
} 

Measured memory_bytes: 256