akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using namespace std;
using namespace __gnu_pbds;

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    int n;
    cin >> n;
    map<int, int> m;
    int pv = 1e9;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x > pv + 1) {
            cout << -1 << "\n";
            return 0;
        }

        pv = x;
        int y = i - x;
        if (y < 0) {
            cout << -1 << "\n";
            return 0;
        }

        m[y] = x;
    }

    ll ans = 0;
    for (auto val : m) {
        ans += val.second;
    }

    cout << ans << "\n";
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  double N; cin >> N;
  vector<int> a(N); REP(i, N) cin >> a[i];
  double b = round(accumulate(all(a), 0) / N);
  ll ans = 0;
  REP(i, N) {
    ans += pow(a[i] - b, 2);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = k; i < (int)(n); i++)
const int maxN = int(1e5 + 10);
int e[maxN] = {}, o[maxN] = {};
int num[maxN] = {};
using ll = long long;

using st = struct {
    int y;
    int index;
};

bool cmp(const st &a, const st &b) { return a.y < b.y; }

int main() {
    int n, m;
    const int maxN = int(1e5 + 10);
    cin >> n >> m;
    vector<st> k[maxN];
    char ans[maxN][20];
    rep(i, m) {
        int p, y;
        cin >> p >> y;
        k[p].push_back({y, i});
    }
    rep(i, maxN) {
        if(k[i].size() != 0) {
            sort(k[i].begin(), k[i].end(), cmp);
            rep(j, k[i].size()) {
                sprintf(ans[k[i][j].index], "%06d%06d", i, j + 1);
            }
        }
    }
    rep(i, m) { cout << ans[i] << endl; }

    return 0;
}


Measured memory_bytes: 8960
#include<iostream>
#include<string>
#include <map>
#include <queue>
using namespace std;

bool check[26] = {false};

string S;
bool isFeasible = true;
map<char, int> mp;


int main()
{
    // 整数の入力

    for (int i = 0; i < 26; i++) {
        mp['a' + i] = false;
    }
    cin >> S;

    for (int i = 0; i < S.size(); i++) {
        mp[S[i]] = true;
    }

    int pos =  S.size(); //最大で26文字:配列は0-25それ+1


    bool isfinish = false;
    string Answer = "";


    while (true) {
        // cout << pos <<endl;
        if (pos < 0)break;
        if (pos == 26) {
            pos--;
            continue;
        }

        char startchar;
        if (pos < S.size())startchar = S[pos] + 1;
        if (pos >= S.size())startchar = 'a';


        for (char i = startchar; i < 'z' + 1 ; i++) {//答えがあるか調べる
            if (i > 'z')break;
            if (mp[i] == false) {
                isfinish = true;
                for (int j = 0; j < pos; j++) {
                    Answer += S[j];
                }
                Answer += (char)(i);
            }
            if (isfinish == true)break;
        }


        if (pos < S.size())mp[S[pos]] = false;
        pos--;
        
        if (isfinish == true)break;
    }

    if (isfinish == false || isFeasible == false)Answer = "-1";

    cout << Answer << endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define int long long
int p[114514];
bool check(int n) {
	for (int i = 0; i < n; i++) {
		if (p[i] == i + 1)return true;
	}
	return false;
}
signed main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> p[i];

	int ans = 0;
	
	for (int i = 0; i < n - 1; i++) {
		if (p[i] == i + 1 && p[i + 1] == i + 2) {
			ans++;
			swap(p[i], p[i + 1]);
		}
		else if (p[i] == i + 1) {
			ans++;
			swap(p[i], p[i + 1]);
		}
	}
	if (p[n - 1] == n)ans++;
	cout << ans << endl;
}

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

int main(){
	int n , m , k ;
	cin >> n >> m >> k ;
  	for(int i = 0 ; i <= n ; ++i){
    	for(int j = 0 ; j <= m ; ++j){
        	int cnt = (m - j) * i + (n - i) * j;
          	if(cnt == k){
            	cout << "Yes";
              	return 0;
            }
        }
    }
  	cout << "No";
}

Measured memory_bytes: 3616
import collections
N = int(input())
W = []
f = input()
W.append(f)
ans = "Yes"
for _ in range(N-1):
    w = input()
    if f[-1] != w[0]:
        ans = "No"
    W.append(w)
    f = w
    
cnt = collections.Counter(W)
for v in cnt.values():
    if v >= 2:
        ans = "No"
        
print(ans)

Measured memory_bytes: 9400
#include<stdio.h>
int func(int *,int,int);

int main(){
  int i,n,a[100000],base;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  base=func(a,0,n-1);
  for(i=0;i<base;i++){
    printf("%d ",a[i]);
  }
  printf("[%d] ",a[i]);
  for(i=base+1;i<n-1;i++){
    printf("%d ",a[i]);
  }
  printf("%d\n",a[i]);
  return 0;
}
int func(int a[],int p,int r){
  int x,i,j,temp,base;
  x=a[r];
  i=p-1;
  for(j=p;j<=r-1;j++){
    if(a[j]<=x){
      i=i+1;
      temp=a[j];
      a[j]=a[i];
      a[i]=temp;
    }
  }
  temp=a[i+1];
  a[i+1]=a[r];
  a[r]=temp;
  base=i+1;
  return base;
}



Measured memory_bytes: 2244
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	var sum float64

	for i := 0; i < n; i++ {
		var x int64
		fmt.Scan(&x)
		sum += 1.0 / float64(x)
	}

	fmt.Println(1. / sum)

}


Measured memory_bytes: 512
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    char ch;
    cin>>ch;
    if('a'<=ch&&ch<='z') cout<<'a'<<endl;
    else cout<<'A'<<endl;

    return 0;
}


Measured memory_bytes: 3636
import java.util.*;

public class Main{
  public static int dp[];
  public static int func(int a[],int i)
  {
    if(i>=a.length)
    return 10000000;
    if(i==a.length-1)
    return 0;
    if(dp[i]!=-1)
    return dp[i];
    if(i<a.length-2)
    {
      dp[i]=Math.min(Math.abs(a[i]-a[i+2])+
            func(a,i+2),
            Math.abs(a[i]-a[i+1])+
            func(a,i+1));
    }
    else
    {
      dp[i]=Math.abs(a[i]-a[i+1])+func(a,i+1);
    }
    return dp[i];
  }
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    dp=new int[n+1];
    for(int i=0;i<n;i++)
    a[i]=sc.nextInt();
    for(int i=0;i<=n;i++)
    dp[i]=-1;
    System.out.println(func(a,0));
  }
}

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


int main()
{
    ll n,k;
    cin >>n>>k;
    if(!(n%k))
        cout <<0;
    else
    {
        ll mod  = n%k;
        if(mod < (k-mod))
        {
            cout <<mod;
        }
        else
        {
            cout <<k - (mod);
        }
        
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
 
#define PI 3.14159265
 
int main(void)
{
    int side1, side2, deg;
    scanf("%d %d %d", &side1, &side2, &deg);
 
    double rad = deg * PI / 180;
 
    double area = side1 * side2 * sin(rad) / 2;
    double side3 = sqrt(pow(side1, 2) + pow(side2, 2)
                        - 2 * side1 * side2 * cos(rad));
    double round = side1 + side2 + side3;
    double height = side2 * sin(rad);
 
    printf("%f\n%f\n%f\n", area, round, height);
 
    return 0;
}


Measured memory_bytes: 2060
#include "iostream"
using namespace std;

int main() {
  int n;
  cin >> n;
  bool check = false;
  char s[110];
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    if (s[i] == 'Y') check = true;
  }
  cout << (check ? "Four" : "Three") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

int main(void){
	ll n;
	cin >> n;
	Vec a(n), b(n), c(n);
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	rep(i, n) cin >> c[i];
	sort(all(a));
	sort(all(b));
	sort(all(c));

	ll ans = 0;
	rep(i, n) ans += (lower_bound(all(a), b[i]) - a.begin()) * (c.end() - upper_bound(all(c), b[i]));
	co(ans);

	return 0;
}


Measured memory_bytes: 5644
a=int(input())

dp = [[0 for i in range(10)] for j in range(10)]

for i in range(a+1):
    if i%10 == 0:
        continue
    x = str(i)
    dp[int(x[0])][int(x[-1])] += 1


count = 0

for i in range(10):
    for w in range(10):
        count += dp[i][w]*dp[w][i]

print(count)

Measured memory_bytes: 3064
//config = { input: 'tmp', newline: '\r\n' }; // win
config = { input: '/dev/stdin', newline: '\n' }; // linux

s = require('fs').createReadStream(config.input, {encoding: 'ascii'});
rl = require('readline').createInterface({input: s, output: process.stdout});
rl.on('line', onRead);
rl.on('end', function () { s.close(); });

const MAXSIZE = 2000000;
const MIN = -1;
h/*eap*/ = new Array(MAXSIZE+1);
s/*ize*/ = 0;
for (i = 0; i <= MAXSIZE; i++) h[i] = MIN;

function maxHeapify(A, i) {
  var l, r, largest, tmp;
  l = i * 2;
  r = i * 2 + 1;
  if (l <= s && A[l] > A[i]) largest = l;
  else largest = i;
  if (r <= s && A[r] > A[largest])
    largest = r;
  if (largest !== i) {
    tmp = A[largest];
    A[largest] = A[i];
    A[i] = tmp;
    maxHeapify(A, largest);
  }
}

function heapExtractMax(A) {
  var max;
  if (s < 1) {
    console.error("???????????¢??????????????????");
    process.exit();
  }
  max = A[1];
  A[1] = A[s];
  s--;
  maxHeapify(A, 1);
  return max;
}

function heapIncreaseKey(A, i, key) {
  var parent, tmp;
  if (key < A[i]) {
    console.error("??°????????????????????¨????????????????°???????");
    process.exit(1);
  }
  A[i] = key;
  while (i > 1) {
    parent = Math.floor(i / 2);
    if (A[parent] >= A[i]) return;
    tmp = A[parent];
    A[parent] = A[i];
    A[i] = tmp;
    i = parent;
  }
}

function maxHeapInsert(A, key) {
  s++;
  A[s] = MIN;
  heapIncreaseKey(A, s, key);
}

function print() {
  console.log(h.slice(1, s + 1));
}

function onRead(line) {
  if (line === 'end') {
    rl.close();
  } else if (line === 'extract') {
    console.log(heapExtractMax(h));
  } else {
    maxHeapInsert(h, parseInt(line.split(' ')[1]));
  }
}

Measured memory_bytes: 69088
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <climits>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

double bin_pow(double a, LL b){
    double res = 1;
    while(b > 0){
        if(b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main() {
    //cout << fixed << setprecision(20);
    int r,g,b,n; cin >> r >> g >> b >> n;


    LL ans =0;
    for(int i=0; i<=3000; ++i){
        if(i*r >n) break;
        for(int j=0; j<=3000; ++j){
            if(i*r + j*g>n) continue;
            if((n-i*r-j*g)%b==0) ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n*2-1; i++) {
    if (i == n*2-1-1) {
      cout << m - (n-1) + i << endl;
    } else {
      cout << m - (n-1) + i << ' ';
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>
#include <set>
#define DB cerr<<"D"<<endl
#define pb push_back
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";}
using P=pair<double,int>;
const ll M = 1e9+7;
void add(ll& x, ll y) {x+=y; x%=M;}
void chmax(ll& x, ll y) {if (x<y) x=y;}
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % M; x = x * x % M; a >>= 1;} return an;}

int main() {
  int n,m; cin>>n>>m;
  int s[n], t[m+1]; m++; t[0]=-1;
  for(int i=0;i<n;i++) cin>>s[i];
  for(int i=1;i<m;i++) cin>>t[i];

  ll sm[m]={1};

  for(int i=0;i<n;i++) {
    ll su = 0;
    // 使わない場合 : sm_new[i] = sm_old[i]
    // 使う場合
    for(int j=0;j<m;j++) {
      ll tm = sm[j];
      if (s[i] == t[j]) add(sm[j],su);
      su += tm;
    }
    /*
    for(int j=0;j<m;j++) {
      cout<<sm[j]<<" ";
    } cout<<endl;*/
  }
  ll an=0;
  for(int i=0;i<m;i++) {
    add(an,sm[i]);
  }
  cout<<an<<endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {
  int H, W;
  while(cin >> H >> W && H && W) {
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W && (i == 0 || i == H - 1); j++) {
        cout << "#";
      }
      for(int k = 0; k < 1 && (i && i != H - 1); k++) {
        cout << "#";
      }
      for(int l = 0; l < W - 2 && (i && i != H - 1); l++) {
        cout << ".";
      }
      for(int m = 0; m < 1 && (i && i != H - 1); m++) {
        cout << "#";
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 3084
#include <stdio.h>
#include <string.h>
#define LEN 100005
 
typedef struct pp {
  char name[100];
  int t;
} P;
 
P Q[LEN];
int head, tail, n;
 
void enqueue(P x) {
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}
 
P dequeue() {
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}
 
int min(int a,int b) {
  return a < b ? a : b; 
}
 
int main() {
  int elaps = 0, c;
  int i, q;
  P u;
  char str[64];
  
  scanf("%d %d",&n ,&q);
  for(i=1; i<=n; i++) {
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n + 1;
 
  while(head != tail) {
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if(u.t > 0) enqueue(u);
    else {
      printf("%s %d\n",u.name,elaps);
    }
  }
  return 0;
}


Measured memory_bytes: 11868
N, A, B, C = map(int,input().split())
l = [int(input()) for i in range(N)]

x = [1]*N

ans = []


def f(p):
    y1 = []
    y2 = []
    y3 = []
    for i in range(len(p)):
        if p[i] == 1:
            y1.append(l[i])
        elif p[i] == 2:
            y2.append(l[i])
        elif p[i] == 3:
            y3.append(l[i])
    if len(y1)*len(y2)*len(y3)!=0:
        return (len(y1)+len(y2)+len(y3)-3)*10 + abs(sum(y1)-A) + abs(sum(y2)-B) + abs(sum(y3)-C)
    else:
        return 'No'

for i1 in range(1,5):
    x[0]=i1
    for i2 in range(1,5):
        x[1]=i2
        for i3 in range(1,5):
            x[2]=i3
            if N==3:
                q=f(x)
                if q != 'No':
                    ans.append(q)
                continue
            else:
                for i4 in range(1,5):
                    x[3]=i4
                    if N==4:
                        q=f(x)
                        if q != 'No':
                            ans.append(q)
                        continue
                    else:
                        for i5 in range(1,5):
                            x[4]=i5
                            if N==5:
                                q=f(x)
                                if q != 'No':
                                    ans.append(q)
                                continue
                            else:
                                for i6 in range(1,5):
                                    x[5]=i6
                                    if N==6:
                                        q=f(x)
                                        if q != 'No':
                                            ans.append(q)
                                        continue
                                    else:
                                        for i7 in range(1,5):
                                            x[6]=i7
                                            if N==7:
                                                q=f(x)
                                                if q != 'No':
                                                    ans.append(q)
                                                continue
                                            else:
                                                for i8 in range(1,5):
                                                    x[7]=i8
                                                    q=f(x)
                                                    if q != 'No':
                                                        ans.append(q)

                                                    

print(min(ans))

Measured memory_bytes: 4980
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int mex=100001;
#define ll long long 
#define test int t;cin>>t;while(t--)
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,a,b) for(int i=a;i>=b;i--)
#define bg begin()
#define en end()
#define fi first
#define se second
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define veci vector<int>
#define veclli vector<long long int> 
#define all(x) x.begin(),x.end()
#define sci(x) scanf("%d",&x);
#define scc(x) scanf("%c",&x);
#define scs(x) scanf("%s",x);
#define debug(arr,n) for(int i=0;i<n;i++) printf("%d ",arr[i]);
#define sz(x) x.size()
#define loop(x) for(auto it=x.begin();it!= x.end();it++)
ll int p;
ll int power(ll int a,int b)
{
    ll int ans=1,f=a;
    while(b)
    {
        if(b&1) ans=(ans*f)%p;
        b=b>>1;
        f=(f*f)%p;
    }
    return ans;
}
int main()
{
   ll int n;
   cin>>n>>p;
   string s;
   cin>>s;
   ll int ans=0;
   if(p==2)
   {
       rfo(i,n-1,0)
       {
           if((s[i]-'0')%2==0) ans+=(i+1);
       }
       cout<<ans;
   }
   else if(p==5) 
   {
       rfo(i,n-1,0)
       {
           if((s[i]-'0')%5==0) ans+=(i+1);
       }
       cout<<ans;
   }
   else
   {
   ll int d=10,dpow[sz(s)]={0};
   dpow[0]=1;
   veci v;
   fo(i,1,sz(s))
   {
   dpow[i]=(dpow[i-1]*d)%p;
   //ll int u=power(dpow[i],p-2)%p;
   }
   ll int cf1[sz(s)]={0};
   cf1[sz(s)-1]=(s[sz(s)-1]-'0')%p;
   //int n=sz(s);
   rfo(i,sz(s)-2,0)
   {
       cf1[i]=(cf1[i+1]+((s[i]-'0')*dpow[(n-1-i)])%p)%p;
      // cout<<cf1[i]<<" ";
   }
   map<ll int,ll int> mp;
  // ll int ans=0;
   mp[0]++;
   rfo(i,n-1,0)
   {
      cf1[i]%=p;
       ans+=mp[cf1[i]];
      // if(!binary_search(all(v),i)) 
        mp[cf1[i]]++;
       // if(cf1[i]==0) ans++;
       
   }
   
   cout<<ans<<endl;
   }
}


Measured memory_bytes: 4100
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
	ll n,k,mx=-1;
	cin>>n>>k;
	ll dp[n+1][k+1];
	memset(dp,0,sizeof(dp));
	ll a[n][2];
	for(ll i=0;i<n;i++)cin>>a[i][0]>>a[i][1];
	for(ll i=1;i<=n;i++)
	for(ll j=1;j<=k;j++){
		if(j-a[i-1][0]>=0)
		dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i-1][0]]+a[i-1][1]);
		else
		dp[i][j]=dp[i-1][j];
	}
	cout<<dp[n][k];
}

Measured memory_bytes: 79104
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class BIMissYou {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        string s;
        cin >> s;
        string res;
        REP(i, s.size()) {
            res += 'x';
        }
        cout << res << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    BIMissYou solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
w = input()
ww = list(set(w))
cnt = []
for i in range(len(ww)):
    cnt.append(w.count(ww[i]))
flag = 0
for i in cnt:
    if i%2==1:
        flag=1
        break
if flag:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
int ordena(const void *a, const void *b){
	return *(int*)a-*(int*)b;
}
int main(){
	int n;
	int l[112345][2];
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		l[i][0] = a+b;
		l[i][1] = a-b;
	}
	qsort(l, n, sizeof(int)*2, ordena);
	int ans=1;
	long now=l[0][0];
	for(int i=1; i<n; i++){
		if(l[i][1]>=now){
			now = l[i][0];
			ans++;
		}
	}
	printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define LLI long long int
#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
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
#define co(i) cout<<i<<endl
using namespace std;
//
const int INF=1e9+7;
const int MOD=1e9+7;
//
int b[100001]={};
void addnum(int k){
    FOR(i,0,100001){
        if(i>=k) b[i]=min(b[i],b[i-k]+1);
    }
}
int main(){
    int n; cin>>n;
    FOR(i,0,100001) b[i]=INF;
    b[0]=0;
    FOR(i,0,70){
        addnum(1);
        addnum(6);
        addnum(36);
        addnum(216);
        addnum(1296);
        addnum(7776);
        addnum(46656);
        addnum(9);
        addnum(81);
        addnum(729);
        addnum(6561);
        addnum(59049);
    }
    co(b[n]);
}


Measured memory_bytes: 640
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    cnt = 0
    for i in range(1, n):
        if s[i] != s[i-1]:
            cnt += 1
    print(cnt + 1)


if __name__ == '__main__':
    solve()


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

int main(){
    string s;
    cin >>s;
    //s=string(100000,'?');
    int n=13;
    long mod=1000*1000*1000+7;
    long *dp=new long[n]() ;
    dp[0]=1;
    int cal[n][10];
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            cal[i][j]=i*j%13;
        }
    }
    long b=0;
    long mul=1;
    for(int i=s.length()-1;i>=0;i--){
        //cout<<mul%mod<<endl;
        if(char(s[i])!='?'){b+=int(s[i]-'0')*mul%13;}
        else{
            long *tmp_dp = new long[n]();
            for(int j=0;j<n;j++){
                for(int k=0;k<10;k++){
                    tmp_dp[(cal[mul%13][k]+j)%13]+=dp[j]%mod;
                    tmp_dp[(cal[mul%13][k]+j)%13]%=mod;
                }
            }
            //dp=tmp_dp;
           
            
            for(int j=0;j<n;j++){
                //cout<<tmp_dp[j]<<endl;
                dp[j]=tmp_dp[j]%mod;
            }
            

        }

        mul*=10;
        mul%=n;
    }
    b%=13;
    int ans;
    if (b<=5){ans=5-b;}
    else{ans=18-b;}
    //cout << ans << endl;
    cout << dp[ans]%mod << endl;
    return 0;
}

Measured memory_bytes: 11264
package main

import "fmt"

func main() {
	var A, B int
	var S string
	fmt.Scan(&A, &B)
	fmt.Scan(&S)

	ans := "Yes"
	for i := 0; i < len(S); i++ {
		if i < A {
			if !('0' <= S[i] && S[i] <= '9') {
				ans = "No"
				break
			}
		} else if i == A {
			if S[i] != '-' {
				ans = "No"
				break
			}
		} else {
			if !('0' <= S[i] && S[i] <= '9') {
				ans = "No"
				break
			}
		}
	}

	fmt.Println(ans)
}


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

int main()
{
  string S;
  cin >> S;
  
  int a = 0, b = 0, c = 0;
  for (int i = 0; i < 3; i++)
  {
    if (S.at(i) == 'a') a++;
    else if (S.at(i) == 'b') b++;
    else c++;
  }
  
  string ans = "No";
  if (a == 1 && b == 1 && c == 1) ans = "Yes";
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n, val, d1;
    ll mod = 998244353;
    cin >> n;
    map<int, ll> cnt;
    cin >> d1;
    cnt[d1]++;
    for(int i = 1; i < n; i++) {
        cin >> val;
        cnt[val]++;
    }
    ll ans = 1;
    if (prev(cnt.end())->first != cnt.size()-1 || cnt[0] != 1 || d1 != 0) {
        cout << 0 << endl;
    } else {
        for(int i = 1; i < cnt.size(); i++) {
            for(int freq = 0; freq < cnt[i]; freq++) {
                ans *= cnt[i-1];
                ans %= mod;
            }
        }
        cout << ans << endl;
    }
    return 0;
}




Measured memory_bytes: 6528
#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int mod=1e9+7;
const int MN=190;
int n,m,a[MN][MN],s[MN][MN],f[MN][MN][MN][15];
char ch[MN][MN];
inline int S(int x,int y,int X,int Y){
	return s[X][Y]-s[X][y-1]-s[x-1][Y]+s[x-1][y-1];
}
int main(){
	scanf("%d%d",&n,&m);
	for(reg int i=1;i<=n;i++){
		scanf("%s",ch[i]+1);
		for(reg int j=1;j<=m;j++){
			a[i][j]=(ch[i][j]=='.');
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	for(reg int i=1;i<=n;i++)
		for(reg int j=1;j<=m;j++)
			for(reg int k=j;k<=m;k++){
				reg int l=i,r=n,mid,res=i-1,tmp;
				while(l<=r){
					mid=(l+r>>1);tmp=S(i,j,mid,k);
					if(!tmp||tmp==(mid-i+1)*(k-j+1))res=mid,l=mid+1;
					else r=mid-1;
				}
				f[i][j][k][0]=res;
			}
	reg int Ans=1;
	for(;f[1][1][m][Ans-1]<n;Ans++)
		for(reg int len=1;len<=m;len++)
			for(reg int i=1;i<=n;i++)
				for(reg int l=1,r=l+len-1;r<=m;l++,r++){
					if(f[i][l][r][Ans-1]==n){
						f[i][l][r][Ans]=n;continue;
					}
					f[i][l][r][Ans]=f[f[i][l][r][Ans-1]+1][l][r][Ans-1];
					if(f[i][l][r][Ans]==n)continue;
					reg int L=l,R=r-1,res=0,mid,x,y;
					while(L<=R){
						mid=(L+R>>1);
						x=f[i][l][mid][Ans-1];
						y=f[i][mid+1][r][Ans-1];
						res=max(res,min(x,y));
						if(x<y)R=mid-1;
						else L=mid+1;
					}
					f[i][l][r][Ans]=max(f[i][l][r][Ans],res);
				}
	printf("%d\n",Ans-1);
	return 0;
}


Measured memory_bytes: 393856
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << min(a,b)+min(c,d) << endl;
}


Measured memory_bytes: 256
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=1e5+5;
const int mod=1e9+7;

int n,k,a[105],sum[N],dp[105][N];
signed main(){
    FastIO;
    cin>>n>>k;
    rep(i,1,n) cin>>a[i];
    dp[0][0]=1;
    rep(i,1,n){
        sum[0]=dp[i-1][0];
        rep(j,1,k) sum[j]=(sum[j-1]+dp[i-1][j])%mod;
        rep(j,0,k){
            if(j>=a[i]) dp[i][j]=(sum[j]-sum[j-a[i]-1]+mod)%mod;
            else dp[i][j]=sum[j];
        }
    }
    cout<<dp[n][k];
    return 0;
}



Measured memory_bytes: 43160
#include <iostream>
#include <set>
using namespace std;
int main(void){
    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(s==u) cout << a-1 << " " << b << endl;
    else cout << a << " " << b-1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
 
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
 
int main(){
  
  string s;
  int i,j;
  cin >> s;
  int a=s.size();
  int z=0;
  
  rep(i,s.size()){
    if(s[i]=='A'){
      if(i<a){
	a=i;
      }
    }
  }

  for(j=s.size();j>0;j--){
    if(s[j]=='Z'){
      if(j>z){
	z=j;
      }
    }
  }
  cout << z-a+1 << endl;
     
  return 0;
} 


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int a[N];
int K;
cin>>K;
for(int i=0; i<N; i++){
    cin>>a[i];
}

int count=0;

for(int j=0; j<N; j++){
    if(a[j]>=K){
        count++;
    }
}
cout<<count<<endl;
}

Measured memory_bytes: 640
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n;
  cin >> n;

  vector<int> a(n);
  set<int> st;
  REP(i,n) cin >> a[i], st.insert(a[i]);
  
  sort(a.begin(),a.end());

  int ans = 0;
  REP(i,n-1){
    FOR(j,i+1,n){
      int now = a[j], tmp = a[j]-a[i], cnt = 2;
      while(st.find(now+tmp) != st.end()) cnt++, now += tmp;
      ans = max(ans,cnt);
    }
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define pan(i,n) for(int i=0;i<n;i++)
#define pans(i,n,a) for(int i=a;i<n;i++)
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define INF 1000000007
#define PI 3.141592653
#define inf 100007
#define pll pair<ll,ll>
#define pii pair<int,int>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

int main(){
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll n=k-a-b;
    if(k<=a) cout<<k;
    else if(n<=0)  cout<<a;
    else if(k>0) cout<<a-n;
}

Measured memory_bytes: 3644
S = input()

if len(S) % 2 != 0:
    print("No")
    exit(0)

ans = True
for i, s in enumerate(S):
    if (i % 2 == 0) and (s != 'h'):
        ans = False
        break
    if (i % 2 != 0) and (s != 'i'):
        ans = False
        break

if ans:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
H, W = map(int, input().split())
Ass = [list(map(int, input().split())) for _ in range(H)]

ans = []
for i in range(H):
    for j in range(W - 1):
        if Ass[i][j] % 2:
            ans.append((i, j, i, j + 1))
            Ass[i][j] -= 1
            Ass[i][j + 1] += 1

for i in range(H - 1):
    if Ass[i][W - 1] % 2:
        ans.append((i, W - 1, i + 1, W - 1))
        Ass[i][W - 1] -= 1
        Ass[i + 1][W - 1] += 1

print(len(ans))
for a, b, c, d in ans:
    print(a + 1, b + 1, c + 1, d + 1)


Measured memory_bytes: 22792
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = int(1e9+7)
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr
    
def main():
    N = int(stdin.readline().rstrip())
    H = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    ans = 0
    now = 0
    ok = 0
    while H.count(0) != N:
        while True:
            if H[ok] == 0:
                ok += 1
                break
            else:
                now = ok
                while True:
                    if now >= N or H[now] == 0:
                        ans += 1
                        break
                    else:
                        H[now] -= 1
                        now += 1

    print(ans)
                
main()

Measured memory_bytes: 27176
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

def resolve():
    # nCk = n! / n!(n-k)! のテーブル作成
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv
 
    # 二項係数計算
    def Combination(n, k, MOD=998244353):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret
 
    MOD = 998244353
    N, M, K = map(int, inp().split())
 
    # テーブルを作成し、K回使いまわす
    fac, finv = COMinit(N-1, MOD)
 
    ans = 0
    for k in range(K+1):
        cmb = Combination(N-1, k)
        m_pow = pow(M-1, (N-k-1), MOD)
        ans += M * m_pow * cmb
        ans %= MOD
 
    print(ans)
  
if __name__ == "__main__":
    resolve()

Measured memory_bytes: 33004
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		List<Integer> result = new ArrayList<Integer>();
		
		int n = stdIn.nextInt();
		int count = 0;
		int[] base = new int[4];
		while( n != 0 ){
			String str = stdIn.next();
			if( str.equals("HIT") ){
				base[3] += base[2];
				base[2] = base[1];
				base[1] = base[0];
				base[0] = 1;
			} else if( str.equals("HOMERUN") ){
				base[3] += ( base[2]+base[1]+base[0]+1 );
				base[2] = 0; base[1] = 0; base[0] = 0;
			} else {
				count++;
			}
			if( count == 3 ){
				n--;
				result.add(base[3]);
				base = new int[4];
				count = 0;
			}
		}
						
		for(Integer score : result){
			System.out.println(score);
		}
	}
}

Measured memory_bytes: 12000
<?php
fscanf(STDIN,"%d %d",$n,$k);
$line = fgets(STDIN); // STDIN(スタンダードインプット:標準入力)から1行を取得
$arr=explode(" ",$line);
for($i=0;$i<$n;$i++){

$arr2[$i]=((int)$arr[$i]);
}
sort($arr2,SORT_DESC);
for($i=0;$i<$k;$i++){
$score+=$arr2[$i];
}
print ($score);
?>


Measured memory_bytes: 16332
sToHour :: (Integral a) => a -> a
sToHour x = x `div` 3600

sToMin :: (Integral a) => a -> a
sToMin x = x `div` 60 `mod` 60

sToSec :: (Integral a) => a -> a
sToSec x = x `mod` 60

makeStrf :: (Show a) => a -> a -> a -> String
makeStrf h m s = show h ++ ":" ++ show m ++ ":" ++ show s

main = do
  hoge <- getLine
  let h = sToHour $ read hoge
      m = sToMin $ read hoge
      s = sToSec $ read hoge
  putStrLn $ makeStrf h m s


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
	int N,M;
	while(cin>>N>>M){
		if(N==0 && M==0) break;
		int r,q;
		vector<int> pc(N+1,0);
		vector<vector<int> >time(M+1,vector<int>(1261,0));
		cin>>r;
		for(int i=0;i<r;i++){
			int t,n,m,s;
			cin>>t>>n>>m>>s;
			if(s==1){
				time[m][t]=1;
				pc[n]=t;
			}else if(s==0){
				for(int j=pc[n];j<t;j++){
					time[m][j]=1;
				}
				pc[n]=0;
			}
		}
		cin>>q;
		for(int i=0;i<q;i++){
			int ts,te,mn,count=0;
			cin>>ts>>te>>mn;
			for(int j=ts;j<te;j++){
				if(time[mn][j]==1) count++;
			}
			cout<<count<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 49156
#include <iostream>
#include <algorithm>
using namespace std;
long long a[25];
long long dfs(int l,int r,int xl,int xr)
{
 if(r-l<=1)return 0;
 long long ans=1e18;
 for(int i=l+1;i<=r-1;i++)
  ans=min(ans,dfs(l,i,xl,xl+xr)+dfs(i,r,xl+xr,xr)+a[i]*(xl+xr));
 return ans;
}
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 cout<<a[1]+a[n]+dfs(1,n,1,1)<<endl;
 return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define FOR(i,a,b) for(long long i=a; i<b; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define PB(x) push_back(x)
#define MP make_pair
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<'Y'<<'e'<<'s'<<endl
#define coutn cout<<'N'<<'o'<<endl
#define coutY cout<<'Y'<<'E'<<'S'<<endl
#define coutN cout<<'N'<<'O'<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
const long long dx[4]={1,0,-1,0};
const long long dy[4]={0,1,0,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;
//cout<<fixed<<setprecision(15)<<

signed main(){
    int a,b; cin >> a >> b;
    yn(a*500>=b);
}

Measured memory_bytes: 256
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int k,x;
    scanf("%d %d", &k ,&x);
    if(500 * k >= x){
        printf("Yes");
    } else {
        printf("No");
    }
    
    return 0;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a,b,n,l,dis[200100],S;
vector<int> G[200100];
void dfs(int u,int f)
{
    dis[u]=dis[f]+1;
    for(int i=0;i<G[u].size();i++){
        if(G[u][i]!=f) dfs(G[u][i],u);
    }
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1;i < n;i ++){
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1,0);
    for(int i=1;i<=n;i++) if(dis[i]>dis[S]) S=i;  
    dfs(S,0);
    for(int i=1;i<=n;i++) l=max(l,dis[i]-1);
	if(l %3 == 1)
		cout <<"Second"<<endl;
	else
		cout<<"First"<<endl;
    return 0;
}


Measured memory_bytes: 21376
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

struct BIT{
  int size;
  vector<ll> dat;
  void init(int n){
    size=n;
    dat.clear();
    dat.resize(n+1);
  }
  void add(int i,ll x){
    while(i<=size){
      dat[i]+=x;
      i +=i&-i;
    }
  }
  ll sum(int i){
    ll s=0;
    while(0<i){
      s +=dat[i];
      i -=i&-i;
    }
    return s;
  }
};
  
int main(){
    int n,q,c,s,t,x;
    cin>>n>>q;
    BIT b1,b2;
    b1.init(n);
    b2.init(n);
    rep(i,q){
        cin>>c;
        if(c==0){
            cin>>s>>t>>x;
            b1.add(s,x);
            b2.add(s,-x*(s-1));
            b1.add(t,-x);
            b2.add(t,x*t);
        }
        else{
            cin>>t;
            ll ans;
            ans=b1.sum(t)*t+b2.sum(t)-b1.sum(t-1)*(t-1)-b2.sum(t-1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 4416