akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
using ll = long long;

int main() {
    int M,K;
    cin >> M >> K;
    if(K != 0){
        if(K >= pow(2, M)){
            cout << -1;
        }else if(M == 1 && K == 1){
            cout << -1;
        } else{
            cout << 0 << " " << K << " " << 0 << " ";
            for (int i = 1; i < pow(2, M); ++i) {
                if(i != K){
                    cout << i << " ";
                }
            }
            cout << K << " ";
            for (int i = pow(2, M) - 1; i >= 1; --i) {
                if(i != K){
                    cout << i << " ";
                }
            }
        }
    }else{
        for (int i = 0; i < pow(2, M) - 1; ++i) {
            cout << i << " " << i << " ";
        }
        cout << pow(2, M) - 1 << " " << pow(2, M) - 1;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

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

    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }

    vl L(n-1);  // L[i] : a[0]からa[i]までのGCD
    L[0] = a[0];
    exrep(i, 1, n-2) {
        L[i] = gcd(L[i-1], a[i]);
    }

    vl R(n-1);  // R[i] : a[n-1]からa[(n-1) - i]までのGCD
    R[0] = a[n-1];
    exrep(i, 1, n-2) {
        R[i] = gcd(R[i-1], a[(n-1) - i]);
    }

    ll ans = max(L[n-2], R[n-2]);
    exrep(i, 1, n-2) {
        chmax(ans, gcd(L[i-1], R[(n-2) - i]));
    }

    out(ans);
    re0;
}

Measured memory_bytes: 2560
n=int(input())
a=list(map(int,input().split()))
l=m=0
for i in range(n):
  if a[i]%2==0:
    l+=1
    if a[i]%3==0 or a[i]%5==0:
      m+=1
    else:
      print("DENIED")
      break    
if l==m:
  print("APPROVED")


Measured memory_bytes: 3060
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if v <= w:
  print('NO')
  exit(0)
if abs(a-b)%(v-w) == 0:
  f = abs(a-b)//(v-w)
else:
  f = abs(a-b)//(v-w)+1
if f <= t:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 9200
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC096A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b;
            var word = Console.ReadLine().Split(' ');
            a = int.Parse(word[0]);
            b = int.Parse(word[1]);

            if (a <= b)
                Console.WriteLine(a);
            else
                Console.WriteLine(a - 1);

                Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int h[20];
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> h[i];

    int sol = 1;
    for (int i = 1; i < n; ++i)
    {
        bool g = true;
        for (int j = 0; j < i; ++j)
            if (h[j] > h[i])
                g = false;
        sol += g;
    }
    cout << sol;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {
    
    new Main().run();
  }

  public void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      int[][] graph = new int[n][n];
      String[] vInfo;
      int degree;

      for(int i=0,v=0; i<n; i++) {
        vInfo = br.readLine().split(" ");
        degree = Integer.parseInt(vInfo[1]);
        for(int j=0,k=2; j<degree; j++) {
          v = Integer.parseInt(vInfo[k++]);
          graph[i][--v] = 1;
        }
      }

      StringBuilder buf = new StringBuilder(n*n);
      for (int[] vertex : graph) {
        for (int v : vertex) {
          buf.append(v).append(" ");
        }
        buf.setLength(buf.length()-1);
        buf.append("\n");
      }

      System.out.print(buf);
    }
    catch (IOException e) {
      System.err.println(e);
    }
  }
}


Measured memory_bytes: 25584
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int a,k;
    string s;
    std::cin>>a>>s>>k;
    for(int i=0;i<a;i++){
        if(s[k-1]!=s[i]){
            s[i]='*';
        }
    }
        std::cout <<s<< std::endl;
}


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

using namespace std;

int main(int argc, char *argv[]) {
    int N;
    cin >> N;

    int64_t sum = 0;
    int cur;
    vector<int> arr;
    for (int i = 0; i < N; i++) {
        cin >> cur;
        sum += cur;
        arr.push_back(cur);
    }
    sort(arr.begin(), arr.end());

    if (sum % 10 != 0) {
        cout << sum << endl;
        return 0;
    } else {
	    for (int j = 0; j < N; j++) {
	        int one = arr[j];
	        if ((sum - one) % 10 != 0) {
	            cout << sum - one << endl;
	            return 0;
	        }
	    }
    }
    cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int[] num = new int[3];
        num[0] = sc.nextInt();
        num[1] = sc.nextInt();
        num[2] = sc.nextInt();
        
        Arrays.sort(num);
        
        System.out.println(num[0] + " " + num[1] + " " + num[2]);
    
    }
}


Measured memory_bytes: 26208
n, k = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))

for i, j in enumerate(a):
    if(j == 1): break

count = 0
tmp = i
while(i > 0):
    count += 1
    i -= (k - 1)

i = tmp - i
while(i < n - 1):
    count += 1
    i += (k - 1)

print(count)

Measured memory_bytes: 13880
#include <iostream>

using namespace std;

int main() {
  int k, s;
  cin >> k >> s;

  int ans = 0;
  for (int x = 0; x <= k; x++) for (int y = 0; y <= k; y++) 
    if (x+y <= s && s-x-y <= k) ans++;

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


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

int main()
{
    double N,K;
    cin >> N >> K;

    
    double per = 0;
    for(double i = 1; i <= N; i++)
    {
        double tmp = 0;
        for(double j = 1; i*pow(2,j-1) < K; j++)
        {
            tmp++;
        }
        per += 1 / (N * pow(2,tmp));
    }

    cout << fixed << setprecision(12) << per << endl; 
}

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

ll a[100001],n,dp[100001];

ll frog(ll ind){
   if(ind==n-1)
    return 0;
    if(dp[ind]!=-1)
        return dp[ind];
 ll l=frog(ind+1)+abs(a[ind]-a[ind+1]);
ll r=1000000;
if(ind+2<n)
   r=frog(ind+2)+abs(a[ind]-a[ind+2]);
  return dp[ind]=min(l,r);
}

int main(){
memset(dp,-1,sizeof(dp));
cin>>n;
ll i;
for(i=0;i<n;i++)
    cin>>a[i];
cout<<frog(0)<<endl;
  	return 0;
}


Measured memory_bytes: 9812
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a<b){
            System.out.println("a < b");
        }else if(a>b){
            System.out.println("a > b");
        }else if(a==b){
            System.out.println("a == b");
        }
        sc.close();
    }
}


Measured memory_bytes: 26296
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mod 1000000007
int main()
{
    int n,K;
    cin>>n>>K;
    lli arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    vector<lli> dp(K+1,0);
    vector<lli> pre(K+1,1);
    dp[0]=1;
    for(int i=0;i<n;i++)
    {   
        for(int j=K;j>0;j--)
        {   
            int l=1;
            int r=min(arr[i],(lli)j);
            int x=j-r;
            dp[j]=dp[j]+pre[j-1]-pre[x]+dp[x];
            dp[j]%=mod;
        }
       pre=dp;
       for(int m=1;m<=K;m++) pre[m]+=pre[m-1];
    }
    cout<<dp[K]<<endl;
    return 0;
}

Measured memory_bytes: 1792
import sys

W, H, N = map(int, input().split())
l = d = 0
u = H
r = W
for i in range(N):
    x, y, a = list(map(int, input().split()))
    if a == 1:
        l = max(x, l)
    if a == 2:
        r = min(x, r)
    if a == 3:
        d = max(y, d)
    if a == 4:
        u = min(y, u)

ans = (r - l) * (u - d)
if r - l < 0 or u - d < 0:
    ans = 0
print(max(ans, 0))


Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<climits>
using namespace std;

int N, M;
int step[110000];
unsigned long pat[110000];

int main(void){
    cin >> N >> M;
    for(int i=0;i<M;i++){
        int a;
        cin >> a;
        step[a] = 1; // hole
    }
    pat[0] = 1;
    for(int i=1;i<N+1;i++){
        if(step[i] == 0)
            pat[i] = (pat[i-1] + pat[i-2]) % 1000000007;
    }
    cout << pat[N];
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int n, m;
    cin >> n >> m;
    vector<string> a, b;
    rep(i, n){
        string s;
        cin >> s;
        a.push_back(s);
    }
    rep(i, m) {
      string s;
      cin >> s;
      b.push_back(s);
    }
    rep(i, n-m+1){
        rep(j, n-m+1){
            bool flag = true;
            rep2(k, i, i+m){
                if(a[k].substr(j, m) != b[k-i]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3620
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<queue>
#include<stack>
#include<utility>
#include<vector>
using namespace std;

typedef long long lint;

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0 ; i < n ; i++){
        cin >> p[i];
    }
    int ans = 0;
    bool flag = false;
    for(int i = 0 ; i < n ; i++){
        int cnta = 0, cntb = 0;
        if(p[i] == i + 1 && !flag){
            int tmp = i;
            bool a = false, b = false;
            while(p[tmp] == i + 1){
                tmp--;
                cnta++;
                if(tmp < 0){
                    a = true;
                    break;
                }
            }
            tmp = i;
            while(p[tmp] == i + 1){
                tmp++;
                cntb++;
                if(tmp >= n){
                    b = true;
                    break;
                }
            }
            if(!a && !b){
                ans += min(cnta, cntb);
            }else if(!a){
                ans += cnta;
            }else if(!b){
                ans += cntb;
            }
            flag = true;
            continue;
        }
        flag = false;
    }
    cout << ans << endl;
    return 0;
}

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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	ll n;
	cin >> n;

	ll a[n];
	rep(i,n) cin >> a[i];

	ll mx = -1;
	ll mn = 1e7;

	rep(i,n){
		if(a[i] > mx) mx = a[i];
		if(a[i] < mn) mn = a[i];
	}

	if(mx - mn >= 2) cout << "No" << endl;
	else if(mx - mn == 1){
		ll x = 0;
		rep(i,n) if(a[i] == mn) x++;
		if(x < mx && 2*(mx - x) <= n - x) cout << "Yes" << endl;
		else cout << "No" << endl;
	}else{
		if(a[0] == n-1 || 2 * a[0] <= n) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

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

long long dp[200000][4];

int main(void){
    int n;
    cin >> n;
    
    long long a[n];
    for(int i = 0;i < n;i++)cin >> a[i];
    
    dp[2][0] = a[0]+a[1],dp[2][1] = -a[0]-a[1];
    for(int i = 2;i < n;i++){
        dp[i+1][0] = max(dp[i][0],dp[i][1])+a[i];
        dp[i+1][1] = max(dp[i][0]-a[i-1]-a[i-1]-a[i],dp[i][1]+a[i-1]+a[i-1]-a[i]);
    }
    cout << max(dp[n][0],dp[n][1]) << endl;
}

Measured memory_bytes: 7452
n, m, d = map(int, input().split())

x = (m - 1) / n
y = 1
if d > 0:
    if n % 2 == 0:
        t = n // 2
        y = 1 - 2 * (d - t) / n
    else:
        t = (n + 1) // 2
        y = 1 - (2 * (d - t) + 1) / n

print(x * y)


Measured memory_bytes: 2940
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int N,M,A,B;
vector<int> G[1010],ans;
bool visited[1010];
bool done=false;

int main(){
    cin>>N>>M;
    rep(i,M){
        cin>>A>>B;
        A--;
        B--;
        G[A].push_back(B);
    }
    rep(i,N){
        // out(i+1);
        rep(j,1010)visited[j]=false;
        queue<pair<int,vector<int>>> que;
        vector<int> a;
        que.push({i,a});
        while(que.size()){
            pair<int,vector<int>> p = que.front();
            que.pop();
            visited[p.first]=true;
            p.second.push_back(p.first);
            for(int next:G[p.first]){
                // cout<<p.first<<" to "<<next<<endl;
                if(next==i){
                    if(ans.size()==0||ans.size()>p.second.size())ans=p.second;
                }
                if(!visited[next])que.push({next,p.second});
            }
        }
    }
    if(ans.size()!=0){
        out(ans.size());
        for(int x:ans)out(x+1);
    }
    else out(-1);

    
    
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = LLONG_MAX/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;


// xの桁数を返す関数
int digit_max(ll x){
    int dig = 0;
    while(x/pow(10,dig) >= 1)dig++;
    return dig;
}

// xのdigit桁目を返す関数
// 下から順にone-based（感覚に即しているはず）
int digit_num(ll x, int digit){
    assert(digit_max(x) >= digit);
    ll t1 = x/pow(10,digit-1);
    ll t2 = (x/pow(10,digit));
    // print(t1,t2);
    return t1 - t2 * 10;
}

int main(){
    ll n; cin >> n;
    ll ret = 0;
    if(n%2){cout << 0 << endl; return 0;}
    // vector<ll> dp(20,0);
    // rep(i,19)dp[i+1] = dp[i] * 10 + 9*(i+1);
    // for(int i = digit_max(n); 1 < i; i--){
    //     ll t = digit_num(n,i);
    //     ret += t * dp[i-2];
    //     ret += t;
    // }
    // cout << ret << endl;
    n /= 2;
    ll d = digit_max(n);
    ll s = 5;
    while(0 < n /s){
        ret += n/s;
        s *= 5;
    }
    cout << ret << endl;
}

Measured memory_bytes: 384
///
// File:  c.cpp
// Author: ymiyamoto
//
// Created on Tue Nov 21 23:24:08 2017
//

#include <cstdint>
#include <cstdlib>
#include <iostream>

using namespace std;

int32_t main()
{
  char A, B, C, D;
  cin >> A >> B >> C >> D;

  int32_t a = A - '0';
  int32_t b = B - '0';
  int32_t c = C - '0';
  int32_t d = D - '0';

  if (a + b + c + d == 7) {
    cout << a << "+" << b << "+" << c << "+" << d << "=7" << endl;
  } else if (a + b + c - d == 7) {
    cout << a << "+" << b << "+" << c << "-" << d << "=7" << endl;
  } else if (a + b - c + d == 7) {
    cout << a << "+" << b << "-" << c << "+" << d << "=7" << endl;
  } else if (a + b - c - d == 7) {
    cout << a << "+" << b << "-" << c << "-" << d << "=7" << endl;
  } else if (a - b + c + d == 7) {
    cout << a << "-" << b << "+" << c << "+" << d << "=7" << endl;
  } else if (a - b + c - d == 7) {
    cout << a << "-" << b << "+" << c << "-" << d << "=7" << endl;
  } else if (a - b - c + d == 7) {
    cout << a << "-" << b << "-" << c << "+" << d << "=7" << endl;
  } else if (a - b - c + d == 7) {
    cout << a << "-" << b << "-" << c << "-" << d << "=7" << endl;
  }

  return 0;
}


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

using namespace std;

int main(){
    char b, ans;
    cin >> b;


    if (b=='A') ans = 'T';
    else if (b=='C') ans = 'G';
    else if (b=='G') ans = 'C';
    else if (b=='T') ans = 'A';

    cout << ans << '\n';
}

   

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

int gcd(int a, int b) {
  for (int i = a; i >= 1; --i) {
    if (a%i == 0 && b%i == 0) {
      return i;
    }
  }
  return 1;
}

int main()
{
  int a, b;
  cin >> a >> b;
  ll ans = ll(a)*b/gcd(a,b);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
class Partition:
    def partion(self, a, p, r): 
        x = a[r]
        i = p - 1
        for j in range(p, r):
            if a[j] <= x:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[r] = a[r], a[i + 1]
        return(i+1)

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(x) for x in input().rstrip().split(" ")]
    x = Partition()
    i = x.partion(a, 0, n-1)
    a = [str(i) for i in a]
    a[i] = "[{}]".format(a[i])
    print(" ".join(a))

Measured memory_bytes: 18344
n,m=map(int,input().split())
a=[]
for _ in range(m):
    a.append(int(input()))
for i in range(m-1):
    if a[i+1]-a[i]==1:
        print(0)
        exit()
dp=[0 for x in range(n+1)]
for j in range(m):
    dp[a[j]]=-1
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for k in range(1,n):
    if dp[k+1]!=-1:
        dp[k+1]=dp[k]+dp[k-1]
    else:
        dp[k+1]=0
print(dp[n]%1000000007)


Measured memory_bytes: 460056
//list index out of rangeエラー表示用
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)


int main(){
  int n;
  cin >> n;
  int tem = 0;
  int flag = 0;
  rep(i, 0, n){
    int d1, d2;
    cin >> d1 >> d2;
    if(d1 == d2){
      tem += 1;
    }
    else{
      tem = 0;
    }
    if(tem >= 3){
      flag = 1;
    }
  }
  if(flag){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}



Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

struct SegmentTree{
    static const int MAX_N = 1<<17;
    int n,dat[2 * MAX_N -1];
    SegmentTree(int n_){
        n=1;
        while(n<n_) n*= 2;
        for(int i=0;i<2*n-1;i++) dat[i] = 0;
    }
    void update(int k,int a){
        k += n-1;
        dat[k]+=a;
        while(k>0){
            k=(k-1)/2;
            dat[k]+=a;
        }
    }
    int query(int a,int b,int k,int l,int r){
        if(r<=a || b<=l) return 0;
        if(a<=l && r<=b) return dat[k];
        else{
            int vl = query(a,b,k*2+1,l,(l+r)/2);
            int vr= query(a,b,k*2+2,(l+r)/2,r);
            return (vl+vr);
        }
    }
    int query(int a,int b){
        return query(a,b,0,0,n);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    SegmentTree sg(n);
    rep(i,q){
        int c,x,y;
        cin>>c>>x>>y;
        if(c) cout<<sg.query(x-1,y)<<endl;
        else sg.update(x-1,y);
    }
    return 0;
}


Measured memory_bytes: 4168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll powmod(ll a, ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

const int N = 300 + 20;
const int INF = 0x3f3f3f3f;

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

  int n;
  cin >> n;
  vector<string> S(n);
  for (auto && s : S) {
    cin >> s;
  }

  int ans = 0;
  for (int k = 0; k < n; ++k) {
    int ok = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <  n; ++j) {
        int ii = (i + k) % n;
        int jj = (j - k + n) % n;
        ok &= (S[i][j] == S[jj][ii]);
      }
    }
    if (ok) ans++;
  }

  cout << ans * n << endl;
}


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

int main() {
  vector<int> a={0,0,0,0,0};
  int time;
  cin >> a.at(0) >> a.at(1) >> a.at(2) >> a.at(3) >> a.at(4) ;
  time = a.at(0)+a.at(1)+a.at(2)+a.at(3)+a.at(4);
  for (int i=0; i<5; i++) {
    if (a.at(i)%10==0) {
      a.at(i) = 10;
    }
    else {
      a.at(i) = a.at(i) % 10;
    }
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  for (int i=0; i<4; i++) {
    time += 10-a.at(i);
  }
  cout << time << endl;
  }


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<list>
#include<deque>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
#include<numeric>
using namespace std;

using ll = int64_t;

/// <summary>
/// 単純なcoutの時に使う
/// </summary>
#define co(a) cout<<a<<"\n"


/// <summary>
/// [beg, end)の範囲を，添え字indexでループするfor文に置換します
/// </summary>
#define rep(i,a) for(ll i=0; i<a; ++i)

/// <summary>
/// 迷路等で使う方向のベクトル
/// </summary>
const vector<ll> dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };

/// <summary>
/// デバッグ時に使う
/// </summary>
#define DEBUG(x)     std::cout << #x << " : " << x << "\n"


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

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

	string N;
	cin >> N;

	unordered_set<char> S;
	rep (i, N.size ()) {
		S.insert (N[i]);
	}

	if (S.size () == 2) {
		cout << "Yes" << endl;
	}
	else {
		co ("No");
	}
}

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

typedef long long ll;

struct Node{
	ll a, b, i;
	bool operator < (const Node &t) const {
		return a * t.b < t.a * b; // a/b < t.a/t.b
	}
}node[202020];

int par[202020];
void init(){
	for(int i=0; i<202020; i++) par[i] = i;
}
int find(int v){
	return v == par[v] ? v : par[v] = find(par[v]);
}

priority_queue<Node> pq;
int chk[202020], p[202020];
int n;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	cin >> n;
	for(int i=2; i<=n; i++) cin >> p[i];
	for(int i=1; i<=n; i++){
		int t; cin >> t;
		if(t == 0) node[i] = {1, 0, i};
		else node[i] = {0, 1, i};
		if(i != 1) pq.push(node[i]);
	}
	ll ans = 0;
	while(pq.size()){
		auto t = pq.top(); pq.pop();
		int now = t.i;
		if(chk[now]) continue;
		chk[now] = 1;
		int nxt = find(p[now]);
		ans += node[now].a * node[nxt].b;
		node[nxt].a += node[now].a;
		node[nxt].b += node[now].b;
		if(nxt != 1) pq.push(node[nxt]);
		par[now] = nxt;
	}
	cout << ans;
}

Measured memory_bytes: 13808
A,B=map(int,input().split())

if B==0 and 0>A:
    print(abs(A))
elif B==0 and A>0:
    print(abs(A)+1)
elif B>=A and A>=0:
    print(B-A)
elif B>=0 and 0>=A:
    if abs(B)>=abs(A):
        print(abs(B)-abs(A)+1)
    else:
        print(abs(A)-abs(B)+1)
elif 0>=B and B>=A:
    print(abs(A)-abs(B))
    
elif A>B and B>=0:
    print(A-B+2)
elif A>=0 and 0>=B:
    if abs(A)>=abs(B):
        print(abs(A)-abs(B)+1)
    else:
        print(abs(B)-abs(A)+1)
elif 0>=A and A>=B:
    print(abs(B)-abs(A)+2)

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

map<int,list<int>> l;
map<vector<int>,bool> par;

int bfs(int src,vector<int>&visited)
{
    int ans=1;
    visited[src]=true;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto it:l[x])
        {
            if(visited[it]==false)
            {
                q.push(it);
                ans++;
                visited[it]=true;
            }
        }
    }
    return ans;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y;
        cin>>x>>y;
        if(par[{x,y}]==false)
        {
            l[x].push_back(y);
            l[y].push_back(x);
            par[{x,y}]=true;
            par[{y,x}]=true;
        }
    }
    int cnt=0;
    vector<int> visited(n+1);
    for(int i=1; i<=n; i++)
    {
        if(visited[i]==false)
            cnt=max(cnt,bfs(i,visited));
    }
    cout<<cnt;
}

Measured memory_bytes: 76128
//om namah shivaay
//faith over fear
//no one wants to die,yet death is the destination we all share 

#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main(){
    ll a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    cout<<(a[0]+a[1]);
    
}

Measured memory_bytes: 3596
import java.util.Scanner;

public class Main {
    static Scanner stdIn = new Scanner(System.in);
    public static void main(String[] args){
        int n = stdIn.nextInt();
        int d = stdIn.nextInt();
        int[][] x = new int[n][d];
        for(int i=0; i<n; i++){
            for(int j=0; j<d; j++){
                x[i][j] = stdIn.nextInt();
            }
        }

        int cnt = 0;
        int dist = 0;
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                dist = 0;
                for(int k=0; k<d; k++){
                    dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
                }
                if(isSquareNumber(dist)){
                    cnt++;
                }
            }
        }

        System.out.println(cnt);
    }
    
    static boolean isSquareNumber(int n){
        double sqrtN = Math.sqrt(n);
        for(int i=0; i<=sqrtN; i++){
            if(i * i == n){
                return true;
            }
        }
        return false;
    }
}


Measured memory_bytes: 35504
// Package main provides
//
// File:  b.go
// Author: ymiyamoto
//
// Created on Sat Aug  4 19:16:48 2018
//
package main

import "fmt"

var N int
var arr []int64

func max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func abs(a int64) int64 {
	if a > 0 {
		return a
	}
	return -a
}

func main() {
	fmt.Scan(&N)
	arr = make([]int64, N)

	for i := range arr {
		fmt.Scan(&arr[i])
	}

	var m int64
	for i := range arr {
		for j := i + 1; j < len(arr); j++ {
			m = max(m, abs(arr[i]-arr[j]))
		}
	}
	fmt.Println(m)
}


Measured memory_bytes: 512
import sys

n, m, *sc = map(int, sys.stdin.read().split())
sc = zip(*[iter(sc)] * 2)

def main():
    a = [0] * n
    b = [0] * n
    for s, c in sc:
        s -= 1
        if b[s] and a[s] != c:
            print(-1); return
        elif s == c == 0 and n > 1:
            print(-1); return
        b[s] = 1
        a[s] = c
    if not b[0] and n > 1: a[0] = 1
    print(''.join(map(str, a)))

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; (i) < (n); ++ (i))
#define loop(i,a,n) for (int i = (a); (i) < (n); ++ (i))
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 0
//#define int ll
using namespace std;
typedef vector<int> vi;

signed main(){
    int a,b,c,d;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a >> b >> c;
    if(c == 0) {
        cout << b << endl;
        return 0;
    }
    d = min(a + b,c-1);
    if(d == c - 1) {
        cout << b + c;
    } else {
        cout << d + 1 + b << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import re

A, B = map(int, input().split())
S = input()

m = re.match("([0-9]+)-([0-9]+)", S)

if m:
    t1 = m[1]
    t2 = m[2]
    if len(t1) == A and t1.isdecimal() and len(t2) == B and t2.isdecimal():
        print("Yes")
        exit()

print("No")

Measured memory_bytes: 10064
#include <stdio.h>
int n, m, i, j, k, ans, l, d[105], a[105]={0};
char s[10];
int main(){
	scanf("%d%d", &n, &k);
	for(i=1; i<=k; i++){
		scanf("%d", &d[i]);
		for(j=1; j<=d[i]; j++){
			scanf("%d", &m);
			a[m]++;
		}
	}
	for(i=1; i<=n; i++){
		if(a[i] == 0) ans++; 
	}
	printf("%d", ans);
	return 0;
}

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

typedef unsigned long long  ULL;
typedef long long LL;

#define pb push_back
#define mp make_pair
#define reset(a, b) memset(a, b, sizeof(a))
#define rep(i,b) for(int i=0; i<b; i++)
#define F first 
#define S second

 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
//    cin>>T;
    T=1;
    while(T--){
       
       int a,b,c;
       cin>>a>>b>>c;
       
       cout<<c<<" "<<a<<" "<<b;
       
       
       
    }
    
    return 0;
}

Measured memory_bytes: 256
#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()
 typedef long long int ll;
 typedef unsigned long long ull;
 template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
 template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
 typedef pair<ll,ll> P;
 const long long MOD = 1e9+7;
 const ll INF = 1LL << 60;


 int main(){
     int n;
     cin >> n;
     vector<tuple<string,int,int>> v(n);

     for(int i = 0; i < n; i++){
         string s;
         int p;
         cin >> s >> p;
         v[i] = make_tuple(s,-p,i+1);

     }

     sort(all(v));

     for(auto x: v){
         cout << get<2>(x) << endl;
     }






 }


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

int main(){
  int i,n,k,j,x,y,kotae;
  cin>>n>>k;
  int a[n];
  for(i=0;i<n;i++){
    a[i]=0;
  }
  for(i=0;i<k;i++){
    cin>>x;
    for(j=0;j<x;j++){
      cin>>y;
      a[y-1]++;
    }
  }
  for(i=0;i<n;i++){
    if(a[i]==0){
      kotae++;
    }
  }
  cout<<kotae;
}
    

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

int main(){
    string s;
    cin >> s;
    ll ans = 0;
    if(s =="0"){
        cout << "Yes" << endl;
        return 0;
    }
    rep(i,s.size()){
        ll num = ll(s.at(i));
        ans += num-48;
        //cout << ans << endl;
    }
    //cout << ans << endl;
    //cout << 0%9 << endl;
    if(ans%9==0 || ans == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

ll calc(int N, int K, string S){
  deque<pair<char,int>> v;
  rep(i,N){
    int j=i;
    while(j+1<N && S[i] == S[j+1]) j++;
    v.emplace_back(make_pair(S[i],j-i+1));
    i=j;
  }
  
  rep(k,K){
    if(v.size() == 1) break;
    if(v.size() == 2){
      pair<char,int> a, b;
      a = v[0]; v.pop_front();
      b = v[0]; v.pop_front();
      a.second += b.second;
      v.push_front(a);
    }
    if(v.size() >= 3){
      pair<char,int> a, b, c;
      a = v[0]; v.pop_front();
      b = v[0]; v.pop_front();
      c = v[0]; v.pop_front();
      a.second = a.second + b.second + c.second;
      v.push_front(a);
    }
    //rep(i,v.size()){
    //  cout << v[i].second << " ";
    //}
    //cout << endl;
  }
  
  ll ret = 0;
  rep(i,v.size()){
    ret += v[i].second -1;
  }
  return ret;
}

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

  ll ret = calc(N, K, S);
  reverse(ALLOF(S));
  ret = max(ret, calc(N, K, S));
 
  cout << ret << endl;
  
  return 0;
}


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

int sn(int n){
  int sn = 0;
  while(n > 0){
    sn += n%10;
    n /= 10;
  }
  return sn;
}

int main(void){
  int n;
  cin >> n;
  if(n%sn(n) == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
def resolve():
    mod = 998244353
    MAX_N = 2 * (10 ** 5)

    fact = [1]
    fact_inv = [0] * (MAX_N + 4)
    for i in range(MAX_N + 3):
        fact.append(fact[-1] * (i + 1) % mod)

    fact_inv[-1] = pow(fact[-1], mod - 2, mod)
    for i in range(MAX_N + 2, -1, -1):
        fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod

    def mod_comb_k(n, k, mod):
        return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod

    n, m, k = map(int, input().split())

    ans = 0
    for i in range(k+1):
        ans += mod_comb_k((n-1), i, mod) * m *pow((m-1), n-i-1, mod)
        ans %= mod
    print(ans)


resolve()

Measured memory_bytes: 82848
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = std::max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = std::min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
int get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int>engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/


signed main() {
	int n, k; cin >> n >> k;
	if (n % 2) {
		int a = n / 2 + 1, b = k + n - 1 + a;
		if (b > 2 * n) { puts("-1"); return 0; }
		rep(i, a) {
			cout << k + 2 * i << " " << b - i << " " << k + 2 * n + i << endl;
		}
		rep(i, n - a) {
			cout << k + 1 + 2 * i << " " << k + 2 * n - 1 - i << " " << k + 2 * n + a + i << endl;
		}
	}
	else {
		int a = n / 2, b = k + n - 1 + a;
		if (b + 1 > 2 * n) { puts("-1"); return 0; }
		rep(i, a) {
			cout << k + 1 + 2 * i << " " << b - i << " " << k + 2 * n + i << endl;
		}
		rep(i, n - a) {
			cout << k + 2 * i << " " << k + 2 * n - 1 - i << " " << k + 2 * n + a + i << endl;
		}
	}
}


Measured memory_bytes: 2304
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#include<cmath>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

int main()
{
    int n; cin >> n;
    double h, m;
    char t;
    double lv, sv;
    REP(n)
    {
        cin >> h >> t >> m;
        lv = m * 360 / 60;//[deg]

        sv = (h * 360 / 12) + m * 30/60;
        
        double dd = fabs(lv - sv);
        if(dd > 180) dd = 360 - dd;
        if(fabs(dd) < 30) { cout << "alert" << endl; continue;}
        if(fabs(dd) < 90) { cout << "warning" << endl; continue;}
        cout << "safe" << endl;
    }

    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int N,K;
    cin >> N >> K;
    int mini = -1;
    REP(i,N) {
        int a;
        cin >> a;
        if(a == 1) mini = i;
    }
    int left = mini;
    int right = N-1-mini;
    int power = K-1;
    int cnt = 0;

    cnt += (left+power-1)/power;
    if(cnt > 0) right -= (cnt*power)-left;
    if(right > 0)cnt += (right+power-1)/power;

    cout << cnt << endl;
}

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

Measured memory_bytes: 3612
use std::io::stdin;
use std::str::FromStr;
#[allow(dead_code, unused_mut)]
fn read<T: FromStr>() -> T {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().parse().ok().expect("1")
}
#[allow(dead_code, unused_mut)]
fn read_vec<T: FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().expect("2"))
        .collect()
}
#[allow(dead_code, unused_mut)]
fn read_two<T: FromStr>() -> (T, T) {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let mut x = s.split_whitespace().map(|x| x.parse().ok().unwrap());
    (x.next().unwrap(), x.next().unwrap())
}
#[allow(dead_code, unused_mut)]
fn read_three<T: FromStr>() -> (T, T, T) {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let mut x = s.split_whitespace().map(|x| x.parse().ok().unwrap());
    (x.next().unwrap(), x.next().unwrap(), x.next().unwrap())
}
#[allow(dead_code)]
fn remove_whitespace(s: &str) -> String {
    s.chars().filter(|c| !c.is_whitespace()).collect()
}
fn main() {
    let (k, n) = read_two::<i32>();
    let mut v:Vec<i32> = read_vec();
    v.sort();
    let mut vv: Vec<i32> = Vec::new();
    for i in 0..n-1 {
        vv.push(v[(i + 1) as usize] - v[i as usize]);
    }
    vv.push(v[0] + k - v.last().unwrap());
    vv.sort();
    println!("{}", k - vv.last().unwrap());
}

Measured memory_bytes: 9464
N, M = map(int, input().split())


if N == 1 and M == 1:
    ans = 1
elif N <= 2 and M <= 2:
    ans = 0
elif N == 1 or M == 1:
    ans = max(N, M) - 2
else:
    ans = N * M - (2 * N + 2 * M - 4)

print(ans)


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

using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define endl '\n'
#define snd second
#define fst first
#define fastio cin.tie(NULL),cout.sync_with_stdio(true)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector <int> vi;
typedef pair <ll, int> ii;
typedef pair <ii,int> iii;

const ll inf = 1e17;
const ll mod = 1e9 + 7;
const int N = 200005;

int n,m,k,ans = 0;
char v[10][10], f[10][10];

void cp(){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			f[i][j] = v[i][j];
}

void pnt(int x, int y){
	for(int i = 0; i < n; i++){
		if(x & (1<<i)){
			for(int j = 0; j < m; j++)
				f[i][j] = 'x';
		}
	}
	for(int j = 0; j < m; j++){
		if(y & (1<<j)){
			for(int i = 0; i < n; i++)
				f[i][j] = 'x';
		}
	}
}

int check(){
	int ans = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			ans += f[i][j] == '#';
	return ans==k;
}

void solve(){
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> v[i][j];
	int ans = 0;
	for(int i = 0; i < (1<<n); i++){ // the bin represents all possible paints
		for(int j = 0; j < (1<<m); j++){
			cp();
			pnt(i, j);
			ans += check();
		}
	}
	cout << ans << endl;
}

int main(){
	fastio;
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
  int N;
  cin >> N;
  vector<ll> H(N);
  for (int i = 0; i < N; i++) cin >> H.at(i);
  bool can = true;
  int check = 0;
  
  for (int i = 0; i < N-1; i++) {
    if (H.at(i) == H.at(i+1) + 1) {
      if (check == 1) can = false;
      H.at(i)--;
      check++;
    }
    else if (H.at(i) > H.at(i+1)) can = false;
    else if (H.at(i) < H.at(i+1)) check = 0;
  }
  
  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, M, ans;

int main()
{
	in >> N >> M;
	std::vector<LL>x(N), y(N), z(N);
	rep(i, N) in >> x[i] >> y[i] >> z[i];
	if (M == 0)
	{
		out << 0 << std::endl;
		return 0;
	}
	ans = -112345678901234;
	rep(bit, 8)
	{
		std::vector<LL>res(N, 0);
		rep(i, N)
		{
			LL a = x[i] * (bit & 1 ? 1 : -1);
			LL b = y[i] * (bit & 2 ? 1 : -1);
			LL c = z[i] * (bit & 4 ? 1 : -1);
			res[i] = a + b + c;
		}
		std::sort(res.rbegin(), res.rend());
		rep(i, M - 1) res[i + 1] += res[i];
		ans = std::max<LL>(ans, res[M - 1]);
	}
	out << ans << std::endl;
	return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> P(N);
  for (int i=0; i<N; i++) {
    cin >> P.at(i);
  }
  
  sort(P.begin(), P.end());
  
  int S=0;
  for (int i=0; i<K; i++) {
    S += P.at(i);
  }
  cout << S << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;

vector<int> v[10000];

int main(){
	int aN,bN,R;
	while(cin >> aN >> bN >> R , aN){	
		for(int i = 0 ; i < 10000 ; i++) v[i].clear();
		for(int i = 0 ; i < aN ; i++){
			int x,y;
			scanf("%d%d",&x,&y);
			v[y].push_back(x);
		}
		for(int i = 0 ; i < 10000 ; i++)
			sort(v[i].begin(),v[i].end());
		int D = 4 * R , ans = 0	;
		for(int i = 0 ; i < bN ; i++){
			int x,y;
			scanf("%d%d",&x,&y);
			for(int p = -D ; p <= D ; p++){
				if(y+p < 0 || y+p >= 10000) continue;
				int m = sqrt( (D-p)*(D+p) );
				ans += upper_bound(v[y+p].begin(),v[y+p].end(),x+m) -
					   lower_bound(v[y+p].begin(),v[y+p].end(),x-m);
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 2316
# AOJ0603

illu = []
n = 0

def findmax(begin, end):
    flag = illu[begin]
    l = 1
    maxlen = 1
    for i in range(begin + 1, end + 1):
        if illu[i] + flag == 1:
            l += 1
        else:
            if l > maxlen:
                maxlen = l
            l = 1
        flag = illu[i]
    return maxlen if maxlen > l else l

def find_alterseq():
    seq = []
    s = e = 0
    flag = illu[0]
    for i in range(1, n + 1):
        if illu[i] + flag != 1:
            seq.append([s, i - 1])
            s = i
        flag = illu[i]
    return seq
        
def reverse(s, e):
    for i in range(s, e + 1):
        illu[i] = 1 - illu[i]

def solve():
    alseq = find_alterseq()
    maxlen = 0
    alseq.insert(0, [0, 0])
    alseq.append([n, n])
    nindex = len(alseq)
    for i in range(1, nindex - 1):
        s, e = alseq[i]
        begin = alseq[i - 1][0]
        end = alseq[i + 1][1]
        if end - begin + 1 >= maxlen:
            reverse(s, e)
            l = findmax(begin, end)
            if l > maxlen:
                maxlen = l
            reverse(s, e)
    return maxlen

line = input()
n = int(line)
illu = list(map(int, list(input().split())))
illu.append(999)
ans = solve()
print(ans)


Measured memory_bytes: 13768
import java.util.Scanner;

/**
 * C - Otoshidama<br>
 * https://atcoder.jp/contests/abc085/tasks/abc085_c<br>
 * https://qiita.com/drken/items/e77685614f3c6bf86f44
 */
public class Main {

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

		int N = in.nextInt();
		int Y = in.nextInt();

		int man = Y / 10000;
		int gosen = 0;
		int sen = 0;

		int work = Y - man * 10000;
		if (work >= 5000) {
			gosen++;
			work -= 5000;
		}

		if (work >= 1000) {
			sen = work / 1000;
		}

		int minCnt = man + gosen + sen;
		if (N < minCnt) {
			System.out.println("-1 -1 -1");
			return;
		}

		// 歩幅は限定される 1, 5, 9
		int diff = N - minCnt;
		while (man > 0 && diff > 0) {
			if (diff >= 9) {
				diff -= 9;
				man -= 1;
				sen += 10;
			} else if (diff >= 5) {
				diff -= 5;
				man -= 1;
				gosen += 1;
				sen += 5;
			} else if (diff >= 1) {
				diff -= 1;
				man -= 1;
				gosen += 2;
			}
		}

		// 5000 -> -1 + 5 = 4
		while (gosen > 0 && diff > 0) {
			diff -= 4;
			gosen -= 1;
			sen += 5;
		}

		if (diff == 0) {
			System.out.println(man + " " + gosen + " " + sen);
		} else {
			System.out.println("-1 -1 -1");
		}
	}
}


Measured memory_bytes: 22868
#include <iostream>
#include <math.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
#define rep_r(i,s,n)for(ll i=n-1;i>=s;i--)
#define repe_r(i,s,n)for(ll i=s;i<=n;i++)
static const ll MOD = 1e9 + 7;
static const ll MAX_L = (ll)1 << 62;

ll A[100001] = {};
ll B[100001] = {};
map<ll, ll> AS;
map<ll, ll> BS;
int main() {
	ll n; cin >> n;
	repe(i, 1, n / 2) {
		ll x, y; cin >> x >> y;
		AS[x]++;
		BS[y]++;
		A[x]++, B[y]++;
	}
	ll topA = 0;
	ll topAI = 0;
	ll topB = 0;
	ll topBI = 0;
	rep(i, 1, 100001) {
		if (A[i] > topA) {
			topA = A[i];
			topAI = i;
		}
		if (B[i] > topB) {
			topB = B[i];
			topBI = i;
		}
	}

	sort(A + 1, A + 100001);
	reverse(A + 1, A + 100001);
	sort(B + 1, B + 100001);
	reverse(B + 1, B + 100001);

	/*
	ll topA = 0;
	ll topAI = 0;
	for (map<ll, ll>::iterator itA = AS.begin(); itA != AS.end(); itA++) {
		if (topAI < itA->second) {
			topA = itA->first;
			topAI = itA->second;
		}
	}
	ll topB = 0;
	ll topBI = 0;
	for (map<ll, ll>::iterator itB = BS.begin(); itB != BS.end(); itB++) {
		if (topBI < itB->second) {
			topB = itB->first;
			topBI = itB->second;
		}
	}*/

	if (topAI != topBI) {
		cout << n - A[1] - B[1] << endl;
	}
	else {
		ll ans1 = n - A[1] - B[2];
		ll ans2 = n - A[2] - B[1];
		cout << min(ans1, ans2) << endl;
	}
	return 0;
}

Measured memory_bytes: 8064