akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
const ll mod = 1000000007;
const ll INF = 1000000000000099;
vector<vector<ll>> e(310,vector<ll>(310,INF));
ll n;
ll dp[310][310];


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

    ll ans=0;cin>>n;

    for(int i=0;i < n;i++)
    {    
        for(int j=0;j < n;j++)
        {
            cin>>e[i][j];
            dp[i][j]=e[i][j];
            if(i<j)ans+=e[i][j];
        }
    }

    for(int k=0;k < n;k++)
    {
        for(int i=0;i < n;i++)
        {
            for(int j=0;j < n;j++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }

    for(int i=0;i < n;i++)
    {
        for(int j=i;j < n;j++)
        {
            bool flag=true;
            for(int k=0;k < n;k++)
            {
                if(dp[i][k]+dp[k][j]<e[i][j]){
                    cout<<-1<<endl;
                    return 0;
                }else if(flag && k!=i && k!=j && dp[i][k]+dp[k][j]==e[i][j]){
                    ans-=e[i][j];
                    flag=false;;//一本分切る
                    //cout<<"a"<<endl;
                }
            }
        }
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 1920
#include <stdio.h>
  
int main(void){
    int i,dice[7];
    char order[101];
      
    for(i=1;i<7;i++)
        scanf("%d", &dice[i]);
      
    scanf("%s", order);
      
    for(i=0;order[i]!='\0';i++){
          
        dice[0] = dice[1];
          
        switch(order[i]){
                  
            case 'E':
                dice[1] = dice[4];
                dice[4] = dice[6];
                dice[6] = dice[3];
                dice[3] = dice[0]; 
                break;
              
            case 'N':
                dice[1] = dice[2];
                dice[2] = dice[6];
                dice[6] = dice[5];
                dice[5] = dice[0]; 
                break;
              
            case 'S':
                dice[1] = dice[5];
                dice[5] = dice[6];
                dice[6] = dice[2];
                dice[2] = dice[0]; 
                break;
                  
            case 'W':
                dice[1] = dice[3];
                dice[3] = dice[6];
                dice[6] = dice[4];
                dice[4] = dice[0]; 
                break;
  
        }
    }
      
    printf("%d\n", dice[1]);
      
    return 0;
}




Measured memory_bytes: 2124
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
using vbvb = vector<vector<bool>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int mod = 1000000007;
const int inf = 1001001001;



int main(void) {
  string s;
  ll k;
  cin >> s >> k;
  ll n = s.size();
  ll cnt = 1;
  ll ans = 0;
  if(s[0]!=s[n-1]){
    rep(i,n-1){
      if(s[i]==s[i+1])cnt++;
      if(s[i]!=s[i+1] || i==n-2) {
        ans+=cnt/2*k;
        cnt = 1;
        //cout << i << " " << ans <<endl;
      }
    }
    cout << ans << endl;
  }
  else{
    bool ok = true;
    rep(i,n){
      if(s[i]!=s[0])ok =false;
    }
    if(ok){
      cout << (n*k)/2 << endl;
      return 0;
    }
    ll p = 0;
    ll j = 0;
    while(s[j]==s[0]){
      if(j==n)break;
      p++;
      j++;
      
    }
    ll l = n-1;
    while(s[l]==s[n-1]){
      if(l<=j)break;
      l--;
      p++;
    }
    //cout << p << endl;
    ans+=p/2*(k-1);
    rep(i,n){
      if(i<j || i>l)continue;
      if(s[i]==s[i+1])cnt++;
      if(s[i]!=s[i+1] || i==l-1) {
        //cout << i << " " << (cnt+1)/2*k << endl;
        ans+=(cnt)/2*k;
        cnt = 1;
      }
    }
    //cout << p/2*(k-1) << endl;
    //cout << j/2*k << " " << (n-1-l)/2 << endl;
    ans+= j/2+(n-1-l)/2;
    cout << ans << endl;
  }
  
      
}






Measured memory_bytes: 256
# 入力を取得
N = gets
B = gets

b_str = B.split(" ")

a = []

a.push(b_str[0].to_i)
b_str.each.with_index{|b,i|
    if i == N.to_i-2
        a.push(b_str[i].to_i)
    else
        a.push([b_str[i].to_i,b_str[i+1].to_i].min)
    end
}

# 結果を出力
print a.inject(:+)

Measured memory_bytes: 1916
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

H, W  = map(int, input().split())

A = [[0]*(W+1)]
for i in range(H):
    A.append([0] + list(map(int, input().split())))

B = [[0]*(W+1)]
for i in range(H):
    B.append([0] + list(map(int, input().split())))

C = [[0 for j in range(W+1)] for i in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j] = abs(A[i][j] - B[i][j])

dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1<<6400
dp[1][0] = 1<<6400
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] = dp[i-1][j]<<C[i][j] | dp[i-1][j]>>C[i][j] | dp[i][j-1]<<C[i][j] | dp[i][j-1]>>C[i][j]

for i in range(6400,INF):
    if dp[H][W]>>i & 1:
        print(i-6400)
        sys.exit()

Measured memory_bytes: 89416
#include <bits/stdc++.h>
#include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
using namespace atcoder;
void Main()
{
    string S;
    cin >> S;

    // 1文字の部分文字列数 + 2文字 + 3文字 + ... + n文字
    ll res = S.size() * (1 + S.size()) / 2;
    
    auto sa = suffix_array(S);
    for (auto x: lcp_array(S, sa)) {
        res -= x;
    }
    
    put(res);
}
signed main(){ Main();return 0;}

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

int main() {
	int d;
	cin >> d;
	string ans = "Christmas";
	int n = 25 - d;
	for (int i = 0; i < n; i++) {
		ans += " Eve";
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define inf 1000000005
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define mod 1000000007
#define sz(a) ((ll)(a).size())

template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcount(s);}
#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define eps 1e-9
typedef pair<int, int> II;
typedef pair<ll, ll> LL;
template<class T> T gcd(T a, T b){ T r; while (b != 0) { r = a % b; a = b; b = r; } return a;}
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define PI (2 * acos((ld)0))
#define linf (1ll << 60)
#define y1 y32432
#define y0 y435346

#define maxn 500005

string s;
int a[maxn];
int f[maxn][30];
int nex[maxn][22];
int n, m;
int q, l, r;

void solve(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    m = 'z' - 'a' + 1;
    cin >> s;
    n = sz(s);
    For(i, 1, n){
    	a[i] = s[i - 1] - 'a';
    }
    ms(f, 0x3f);
    Ford(i, n, 1){
    	f[i][a[i]] = i + 1;
    	For(j, a[i], m - 1){
    		if(f[i][j] > n) f[i][j + 1] = n + 2;
    		else{
    			f[i][j + 1] = f[f[i][j]][j];
    		}
    	}
    	For(j, 0, a[i] - 1){
    		if(f[i][m] > n) f[i][j] = n + 2;
    		else f[i][j] = f[f[i][m]][j];
    	}
    }

    For(i, 1, n) nex[i][0] = f[i][m];
    For(t, 0, 20) For(i, 1, n){
    	if(nex[i][t] > n) nex[i][t + 1] = n + 2;
    	else nex[i][t + 1] = nex[nex[i][t]][t];
    }
//    cout << f[11][0] << endl;
//    For(i, 11, 13) cout << a[i] << endl;
    cin >> q;
    Rep(iq, q){
    	cin >> l >> r;
    	r++;
    	int run = l;
    	Ford(i, 20, 0) {
    		if(run > r) break;
    		if(run == r){
    			break;
    		}
    		if(nex[run][i] <= r){
    			run = nex[run][i];
    		}
    	}
    	if(run == r) cout << "Yes\n";
    	else cout << "No\n";
    }

}

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


Measured memory_bytes: 104732
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

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












int main() {
	string s;
	cin >> s;
	cout << [&]()->ll{
		ll cnt = 0;
		REP(i, s.size() / 2) {
			if (s[i] != s[s.size() - 1 - i]) cnt++;
		}
		return cnt;
	}() << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(ll i=0;i<N;++i)
typedef long long int ll;
ll INF = 1LL<<60;
int MOD = 1e9 + 7;

int main(){
    int n; cin >> n;
    double ans;
    vector<double> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());
    ans = a[0];
    rep(i,n-1){
        ans = (ans + a[i+1])/2;
    }
    cout << fixed;
    cout << setprecision(5) << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP1(i,n) for(int i = 1; i < n+1 ;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 INF 2e9
#define ALL(v) v.begin(), v.end()
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
typedef long long ll;

int main(){
    int n,m,p,ac=0,wa=0;
    string s;cin >> n >> m;
    vector<bool> AC(n,false);
    vector <int> w_count(n,0);
    REP(i,m){
        cin >> p >> s;
        if (s == "WA"){
            w_count[p-1]++;
        }
        if(s=="AC" and !AC[p-1]){
            ac++;
            AC[p-1] = true;
            wa+=w_count[p-1];
        }
    }
    cout << ac << " " << wa << endl;
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#pragma warning (disable:4996)

typedef struct { int D1; int D2; }DICE;


int main() {
	//input
	int N;
	(void)scanf("%d", &N);
	DICE dice[3] = {};
	for (int i = 0; i < 3; i++) {
		(void)scanf("%d%d", &dice[i].D1, &dice[i].D2);
	}

	//judge
	bool ans = false;
	if ((dice[0].D1 == dice[0].D2) && (dice[1].D1 == dice[1].D2) && (dice[2].D1 == dice[2].D2)) {
		ans = true;
	}
	for (int i = 0; i < N - 3; i++) {
		if ((dice[0].D1 == dice[0].D2) && (dice[1].D1 == dice[1].D2) && (dice[2].D1 == dice[2].D2)) {
			ans = true;
			break;
		}
		else {
			dice[0] = dice[1];
			dice[1] = dice[2];
			(void)scanf("%d%d", &dice[2].D1, &dice[2].D2);
		}
	}

	//output
	if (ans)printf("Yes"); else printf("No");
}

Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b;
	cin>>a>>b;
	cout<<max({a+b,a-b,a*b})<<endl;
}

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

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

    string s;
    cin >> s;
    if(s == "Sunny")
        cout << "Cloudy";
    else if(s == "Rainy")
        cout << "Sunny";
    else if(s == "Cloudy")
        cout << "Rainy";
    cout << "\n";
    return 0;
}


Measured memory_bytes: 3608
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	int N, A, B;
	int result = 0;
	std::cin >> N >> A >> B;
	
	for (int i = 1; i <= N; ++i) {
		int sum = 0;
		for (int j = i; j > 0; j /= 10) {
			sum += j % 10;
		}
		if (sum >= A && sum <= B)
			result += i;
	}
	std::cout << result << "\n";
}


Measured memory_bytes: 384
package main
import "fmt"
func main(){
	var N, P int
	fmt.Scan(&N, &P)
	primeDividers := make(map[int]int)
	for i:=2; i*i<=P; i++{
		tmp := 0
		for P % i == 0{
			tmp++
			P/=i
		}
		if tmp>0{
			primeDividers[i]=tmp
		}
	}
	if P > 1{
		primeDividers[P] = 1
	}
	ans := 1
	for k, v := range primeDividers{
		if v >= N{
			ans *= pow(k, v/N)
		}
	}
	fmt.Println(ans)
}

func pow(a, x int)int{
	if x == 0{
		return 1
	}
	ret := 1
	for x > 0{
		x--
		ret *= a
	}
	return ret
}

Measured memory_bytes: 1832
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int main(){
  int a,b,n;cin>>a>>b>>n;
  int x,y;cin>>x>>y;
  string s,t;cin>>s>>t;
  int i;
  int ue=1,sita=a;
  for(i=n-1;0<=i;i--){
    if(t[i]=='U') sita=min(a,sita+1);
    if(t[i]=='D') ue=max(1,ue-1);
    if(s[i]=='U') ue++;
    if(s[i]=='D') sita--;
    if(a<ue or sita==0){cout<<"NO"<<endl;return 0;}
    //cout<<ue<<" "<<sita<<endl;
  }
  int right=b,left=1;
  for(i=n-1;0<=i;i--){
    if(t[i]=='L') right=min(b,right+1);
    if(t[i]=='R') left=max(1,left-1);
    if(s[i]=='L') left++;
    if(s[i]=='R') right--;
    if(b<left or right==0){cout<<"NO"<<endl;return 0;}
  }
  //cout<<ue<<" "<<sita<<endl;
  //cout<<left<<" "<<right<<endl;
  if(x<ue or sita<x or y<left or right<y) cout<<"NO"<<endl;
  else cout<<"YES"<<endl;
}


Measured memory_bytes: 776
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main(void){
  int i,j,k,t,tmp;
  string s;
  int a,b;
  int H,W;
  char c;
  cin>>H>>W;
  t=0;
  for(i=1;i<=H;i++){
    for(j=1;j<=W;j++){
      cin>>c;
      if(c=='#') t++;
    }
  }
  if(t==W+H-1) cout<<"Possible";
  else cout<<"Impossible";
  cout<<endl;

  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main(){
	var n,k,sum int
	fmt.Scan(&n,&k)
	h := make([]int,n)
	for i := 0 ; i < n ; i++ {
		fmt.Scan(&h[i])
	}
	if n > k {
		sort.Sort(sort.Reverse(sort.IntSlice(h)))
		for i := k ; i < n ; i++ {
			sum += h[i]
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 5504
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Globalization;
using static System.Console;
using static System.Math;

namespace dwango_5_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nk = ReadLine().Split().Select(int.Parse).ToArray();
            int n = nk[0];
            int k = nk[1];
            long[] input = ReadLine().Split().Select(long.Parse).ToArray();

            var list = new List<long>();
            for (int i = 0; i < n; i++){
                long sub = 0;
                for (int j = i; j < n; j++){
                    sub += input[j];
                    list.Add(sub);
                }
            }
            long ans = 0;

            //foreach (var item in list)
            //{
            //    WriteLine(item);
            //}

            for (int i = 40; i >= 0; i--){
                var check = new List<long>();
				foreach (var item in list){
					if ((item & 1L << i) > 0){
                        check.Add(item);
                    }
				}
				if (check.Count >= k){
					ans += 1L << i;
                    list = check;
				}
			}
            WriteLine(ans);
        }
    }
}

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

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb puah_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int h, w; cin >> h >> w;
    int count = 0;
    REP(i, 0, h){
        string s; cin >> s;
        REP(l, 0, w){
            if(s[l] == '#'){
                count++;
            }
        }
    }
    if(count == h + w - 1){
        cout << "Possible";
    }else{
        cout << "Impossible";
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
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;
}
using namespace std;
 
void solve(){
	int h,w,a,b;
	cin>>h>>w>>a>>b;
	vector<vector<int>>ans(h,vector<int>(w,0));
    rep(i,b){
        for(int j=a;j<w;++j)ans[i][j]=1;
    }
    for(int i=b;i<h;++i){
        rep(j,a)ans[i][j]=1;
    }
    rep(i,h){
        rep(j,w){
            cout<<ans[i][j];
        }
        cout<<"\n";
    }
}
 
signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}

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



using namespace std;




int main()
{
vector <vector <int>> a(3,vector <int>(3));
vector <vector <bool>> d(3,vector <bool>(3,false));

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

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

    for (int i=0; i<3; i++)
        for (int j=0; j<3; j++)
            if (now==a[i][j]){ d[i][j] = true;}
}

/*
for (int i=0; i<3; i++)
    for (int j=0; j<3; j++)
        cout << d[i][j] << "\n"[j!=2];
*/





bool is = false;
for (int i=0; i<3; i++)
    {   bool xis = true;
            for (int j=0; j<3; j++)
                xis&=d[i][j];
            is|=xis;
    }

for (int i=0; i<3; i++)
    {   bool xis = true;
            for (int j=0; j<3; j++)
                xis&=d[j][i];
            is|=xis;
    }
bool xis = true;
for (int i=0; i<3; i++)
    xis&=d[i][i];
is|=xis;

 xis = true;
for (int i=0; i<3; i++)
    xis&=d[i][2-i];
is|=xis;

if (is) cout << "Yes"; else cout << "No";

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vi vector <ll> 
#define qu queue <ll>
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl;
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}


void solve()
{
    ll n, m; cin >> n >> m;
    ll a, s = 0;
    for (ll i = 0; i < m; i++)
    {
        cin >> a; s += a;
    }
    if (n-s<0) nout(-1);
    else nout(n-s);
}

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

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


int main() {
  int H,W,D;
  cin >> H >> W >> D;
  int a;
  vector<vector<int>> A(H,vector<int>(W)),lis(H*W,vector<int>(2,0));
  rep(i,H)rep(j,W) {
    cin >> a;
    a--;
    A[i][j]=a;
    lis[a] = {i,j};
  }
  vector<int> cost(H*W,0);
  rep2(i,D,H*W) {
    auto t = lis[i-D], n = lis[i];
    cost[i] += cost[i-D] + abs(t[0]-n[0]) + abs(t[1]-n[1]);
  }
    
  int Q,l,r;
  cin >> Q;
  rep(i,Q) {
    cin >> l >> r;
    l--;r--;
    cout << cost[r] - cost[l] << endl;
  }
} 

Measured memory_bytes: 6784
#include<iostream>
#include<cstdio>
#include<ctime>

using namespace std;

//math
//------------------------
template<class T>inline T sqr(T x){ return x*x; };



int a,b;


void solve(int a,int b){
	if (a < b){
		cout << "a < b" << endl;
	}
	else if (a == b){
		cout << "a == b" << endl;
	}
	else{
		cout << "a > b" << endl;
	}
}






int main(){
	//std::clock_t start = clock();
	std::cin >> a>>b;
	solve(a, b);
	//printf("time is %d",(clock()-static_cast<double>(start)/CLOCKS_PER_SEC));
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    string s, t;
    cin >> s >> t;
    map<int, int> match;
    for( int i = 0; i < s.size(); ++i ) {
        if( match[t[i]] == 0 ) {
            match[t[i]] = s[i];

        } else {
            if( match[t[i]] != s[i] ) {
                cout << "No" << endl;
                return 0;

            }
        }
    }

    map<int, int> mat;
    for( int i = 0; i < t.size(); ++i ) {
        if( mat[s[i]] == 0 ) {
            mat[s[i]] = t[i];

        } else {
            if( mat[s[i]] != t[i] ) {
                cout << "No" << endl;
                return 0;

            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 916
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        x: String,
        y: String,
    }
    if x < y {
        println!("<");
    } else if x > y {
        println!(">");
    } else {
        println!("=");
    }
}


Measured memory_bytes: 4352
#include <stdio.h>

int main()
{
    int i;
    long long c=0,sum=0,num=0;
    scanf("%llu",&num);
    for(i=0;i<num;i++){
        scanf("%llu",&c);
        sum += c;
    }
    printf("%llu\n",sum / num);
	return 0;
}

Measured memory_bytes: 604
#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(dead_code)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(dead_code)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(dead_code)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        h: i64,
        n: usize,
        magic: [(i64, i64); n],
    }

    // DP
    // とりあえずでかい数
    // iダメージを与えるのに必要なMP dp[i]
    // ダメージ0でいいならMP0
    let mut dp = vec![0];
    // dp[0] = 0;
    for v in 1..(h + 1) {
        let mut min_mp = 1_000_000_000;
        // i番目の魔法を使うときの最小MPをresultにもとめて、それがvダメージ与える最小MPならmin_mpを更新する
        for i in 0..n {
            let current_magic = magic[i];
            let (cma, cmb) = (current_magic.0, current_magic.1);
            // let before = mv[i];
            // let mut vmut = v;
            // let mut mp = 0;
            let others = if v > cma {
                dp[(v - cma) as usize]
            } else {
                0
            };
            min_mp = min(min_mp, cmb + others);
        }
        // let result = mv.into_iter().min().unwrap();
        // dp[v as usize] = min_mp;
        dp.push(min_mp);
    }

    // DEBUG
    // for (i, &d) in dp.iter().enumerate() {
    //     println!("i: {:3}, d: {:6}", i, d);
    // }
    // DEBUG END

    // println!("{}", used + dp[h as usize]);
    println!("{}", dp.pop().unwrap());
}


Measured memory_bytes: 4352
// Problem : E - LISDL
// Contest : AtCoder Regular Contest 091
// URL : https://atcoder.jp/contests/arc091/tasks/arc091_c
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define size(x) (int)x.size()
#define reverse(l, sz) reverse(c + l, c + l + sz)

const int N = 1e6 + 1, mod = 1e9 + 7, inf = 2e9;

int n, a, b, c[N];

int main() { cin.tie(0)->sync_with_stdio(0);
	cin >> n >> a >> b;
	if (a + b - 1 > n || 1ll * a * b < n) {
		return cout << -1, 0;
	}
	int first = n - n / a * a;
	for (int i = 1; i <= first; i++) {
		c[i] = i + n - first;
	}
	for (int i = 1; i <= n / a; i++) {
		for (int j = 1; j <= a; j++) {
			c[a * (i - 1) + j + first] = j + (n / a - i) * a;
		}
	}
	int need = b - (n / a + !!(n % a));
	if (first >= 1) {
		if (need >= first - 1) {
			reverse(1, first);
			need -= first - 1;
		} else {
			reverse(1, need + 1);
			need = 0;
		}
	}
	for (int i = 1; i < n / a; i++) {
		if (!need) {
			break;
		}
		int f = first + a * (i - 1) + 1;
		if (need >= a - 1) {
			reverse(f, a);
			need -= a - 1;
		} else {
			reverse(f, need + 1);
			need = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << c[i] << ' ';
	}
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define each(i, a) for(auto &i : a)
#define SORT(a) sort(a.begin(),a.end())
#define rSORT(a) sort(a.rbegin(),a.rend())
#define fSORT(a,f) sort(a.begin(),a.end(),f)
#define all(a) a.begin(),a.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define tp(a,i) get<i>(a)
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }

int main() {
    init();

    int n; cin >> n;
    VI f(n + 1);
    FOR(x, 1, n)eFOR(y, 1, n) {
        for (int z = 1; x * x + y * y + z * z + x * y + y * z + z * x <= n; ++z) {
            ++f[x * x + y * y + z * z + x * y + y * z + z * x];
        }
    }
    eFOR(i, 1, n)print(f[i]);

    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;

ll cnt[2050];
ll to[2050];
ll a[200050];
ll ans;

void shift() {
    ll cntt[2050] = {};
    for (int i = 0; i < 2019; i++) {
        cntt[to[i]] = cnt[i];
    }
    for (int i = 0; i < 2019; i++) {
        cnt[i] = cntt[i];
    }
}

int main() {
    string s;
    cin >> s;
    cnt[0] = 1;
    for (int i = 0; i < 2019; i++) {
        to[i] = i * 10 % 2019;
    }
    for (int i = 0; i < s.size(); i++) {
        ll num = s[i] - '0';
        if (i != 0) {
            a[i] = a[i-1] * 10 + num;
            a[i] %= 2019;
        } else {
            a[i] = num;
        }
        shift();
        ans += cnt[a[i]];
        // if (cnt[a[i]] != 0) cout << i << endl;
        cnt[a[i]]++;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

#define MAX 110
#define INF 1e9
#define F first
#define S second
typedef pair<int,int> pii;
typedef pair<pii,int> State;

struct Edge{
  int to,cost;
  Edge(){}
  Edge(int to,int cost) : to(to),cost(cost) {}
};

int N,M,L,K,A,H;
bool l[MAX];
vector<Edge> G[MAX];

void init(){
  for(int i = 0 ; i < MAX ; i++){
    l[i] = false;
    G[i].clear();
  }
}

int dijkstra(){
  priority_queue<State,vector<State>,greater<State> > Q;
  Q.push(State(pii(0,A),M));
 
  int Time[MAX][MAX];
  fill(Time[0],Time[0]+MAX*MAX,INF);
  Time[A][M] = 0;

  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    int v = s.F.S, m = s.S;
    if(Time[v][m] < s.F.F) continue;

    if(l[v]){
      for(int i = 1 ; i <= M-m ; i++){
        if(Time[v][m] + i < Time[v][m+i]){
          Time[v][m+i] = Time[v][m] + i;
          Q.push(State(pii(Time[v][m+i],v),m+i));
        }
      }
    }

    for(int i = 0 ; i < (int)G[v].size() ; i++){
      Edge e = G[v][i];
      if(m - e.cost >= 0){
        if(Time[v][m] + e.cost < Time[e.to][m-e.cost]){
          Time[e.to][m-e.cost] = Time[v][m] + e.cost;
          Q.push(State(pii(Time[e.to][m-e.cost],e.to),m-e.cost));
        }
      }
    }
  }
  return *min_element(Time[H],Time[H]+M);
}

int main(){
  int a,b,c;
  while(cin >> N >> M >> L >> K >> A >> H, N){
    init();
    for(int i = 0 ; i < L ; i++){
      cin >> a;
      l[a] = true;
    }
    for(int i = 0 ; i < K ; i++){
      cin >> a >> b >> c;
      G[a].push_back(Edge(b,c));
      G[b].push_back(Edge(a,c));
    }
    int res = dijkstra();
    if(res == INF){
      cout << "Help!" << endl;
    }else{
      cout << res << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1476
#include<stdio.h>
int main(){
char s[111111];
int i,a=-1,b=-1;
for(i=0;i<111111;i++)
s[i]='\0';
scanf("%s",s);
if(s[0]==s[1]){
a=1;
b=2;
}
for(i=2;s[i]!='\0';i++){
if(s[i]==s[i-1]){
a=i;
b=i+1;
}
if(s[i]==s[i-2]){
a=i-1;
b=i+1;
}
}
printf("%d %d\n",a,b);
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ROOP(i, N) for(int i=0; i++; i<N)
#define RVROOP(i, N) for(int i=N; i--; i>=0)
#define ALL(v) v.begin(), v.end()
const int INF = 1e9;
const int MAX = 510000;
const int MOD = 1000000007;
const double PI = acos(-1);
using namespace std;
typedef long long ll;

/*C++になってるか確認したほうがよくない？WOWWOW*/
/*DP使ったほうがよくない？？WOWWOW*/

int main(){
  int n, m; cin>>n>>m;
  if(n<=m){
    cout<<"unsafe"<<endl;
  }
  else{
    cout<<"safe"<<endl;
  }
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <math.h>
using namespace std;

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

	int x_max = Y / 10000;
	int y_max = Y / 5000;	
	
	for (int i = 0; i <= x_max; i++)
	{
		for (int j = 0; j <= y_max; j++)
		{
			int k = N - i - j;
			if (k < 0)
			{
				break;
			}

			int tmp = 10000 * i + 5000 * j + 1000 * k;
			if (tmp == Y)
			{
				cout << i << " " << j << " " << k;
				return 0;
			}
		}
	}

	cout << -1 << " " << -1 << " " << -1;

	return 0;
}

Measured memory_bytes: 256
import math


def main():
    X = int(input())
    ans = 0
    for b in range(1, int(math.sqrt(X))+1):
        p = 2
        while b**p <= X:
            if b**p > ans:
                ans = b**p
            p += 1
            if b == 1:
                break
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int x, a, b;
    cin >> x >> a >> b;
    int A = abs(x - a);
    int B = abs(x - b);
    if(A < B) cout << "A" << endl;
    else cout << "B" << endl;
    return 0;
}

Measured memory_bytes: 3612
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
typedef unsigned long long ull;
typedef signed long long sll;
using namespace std;

#define INF 0x7FFFFFFFFFFFFFFF
#define BIG_PRIME 1000000007

int main()
{
  ull i,j,a,k,N,K,MAX;
  cin >> N >> K;
  //dp[x][y]:xまでの子供に合計でy個分け与える組み合わせ
  vector<vector<ull>> dp(N+1);
  dp[0].resize(K+1,0);
  dp[0][0]=1;
  MAX=0;
  for(i=1;i<=N;++i)
  {
    dp[i].resize(K+1,0);
    cin >> a;
    MAX=min(MAX+a,K);
    dp[i][0]=1;
    for(j=1;j<=MAX;++j)
    {
      dp[i][j]=(dp[i-1][j]+dp[i][j-1])%BIG_PRIME;
      if(j>a)
      {
        dp[i][j]=(dp[i][j]+BIG_PRIME-dp[i-1][j-a-1])%BIG_PRIME;
      }
    }
  }
  cout << dp[N][K];
  return 0;
}

Measured memory_bytes: 79488
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for (ll i=0; i<(n); ++i)
#define rep1(i,n) for (ll i=1; i<=(n); ++i)
typedef long long ll;
bool debug=false;
string yes = "Yes";
string no = "No";
const ll mod = 998244353;
const double e = 0.000000001;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define DEBUG 0
#define nl          '\n'
#if     DEBUG
#define trace(var)  {cerr << "Line " << __LINE__ << ": " << #var << "=" << var << nl;}
#else
#define trace(var)	{}
#endif
#define fori(n)			for(int i = 0; i < n; ++i) 
#define forj(n)			for(int j = 0; j < n; ++j)
#define fork(n)			for(int k = 0; k < n; ++k)
#define forl(n)			for(int l = 0; l < n; ++l)

typedef long long ll;typedef pair<int,int> pii;typedef vector<bool> vbool;typedef vector<int> vint;typedef vector<ll> vll;typedef long double ld;typedef vector<vector<int>> vvi;

const ll N = 3000;
const ll INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n;
ll memo[N][N][2];

ll solve(vll &a, int i, int j, bool mxmz) {
	if (i > j) return 0;
	if (memo[i][j][mxmz] != -1) {
		return memo[i][j][mxmz];
	}
	ll ans;
	if (mxmz) {
		ans = memo[i][j][mxmz] = max(a[i] + solve(a, i+1, j, !mxmz), a[j] + solve(a, i, j-1, !mxmz));
	} else {
		ans = memo[i][j][mxmz] = min(-a[i] + solve(a, i+1, j, !mxmz), -a[j] + solve(a, i, j-1, !mxmz));
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(memo, -1, sizeof memo);
	cin >> n; 
	vll a(n);
	fori(n) {cin >> a[i];}
	cout << solve(a, 0, n-1, true) << nl;

	#if DEBUG
	cerr << "Time: " << (ld)clock() / CLOCKS_PER_SEC << " s" << nl;
	#endif
	return 0;
}


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

int POWINT(int x, int n) {
  int ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

ll POWLL(int x, int n) {
  ll ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

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

pair<vector<char>, vector<ll>> Block(string s) {
  ll num = 1;

  vector<char> v1;
  vector<ll> v2;

  rep (i, 0, s.size()) {
    char c = s[i];
    if (i == 0) {
      v1.pb(c);
    } else if (c == s[i - 1]) {
      num++;
    } else {
      v2.pb(num);
      v1.pb(c);
      num = 1;
    }

    if (i == s.size() - 1) v2.pb(num);
  }

  return make_pair(v1, v2);
};

ll calc(vector<char> &b_ch, vector<ll> &b_num) {
  ll ans = 0;
  rep(i, 0, (int)b_ch.size()) {
    ll n = b_num[i];
    char ch = b_ch[i];
    if (ch == '<' && i < (int)b_ch.size()-1) {
      ans += (n)*(n-1ll)/2ll;
    } else if (ch == '>') {
      ll m = b_num[i-1]; // left '<'
      if (m > n) {
        ans += (n)*(n-1ll)/2ll + m;
      } else {
        ans += (n+1ll)*n/2ll;
      }
    } else if (ch == '<' && i == b_ch.size() - 1){
      ans += (n+1ll)*n/2ll;
    }
  }

  return ans;
};

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

  string S;
  cin >> S;

  auto block = Block(S);

  auto b_ch = block.first;
  auto b_num = block.second;

  // PrintVec(b_ch);
  // PrintVec(b_num);


  if (S[0] == '<') {
    ll ans = calc(b_ch, b_num);
    cout << ans << endl;
    return 0;
  }

  if (S[0] == '>') {
    vector<char> b_ch2 = vector<char> (b_ch.begin()+1, b_ch.end());
    vector<ll> b_num2 = vector<ll> (b_num.begin()+1, b_num.end());
    ll ans = calc(b_ch2, b_num2);
    ll n0 = b_num[0];
    ans += (n0+1ll)*n0/2ll;
    cout << ans << endl;
    return 0;
  }

  return 0;
};


Measured memory_bytes: 7304
let s = read_line ()
let n = String.length s
let l, r, ans = ref 0, ref @@ n - 1, ref 0
let _ = while !l < !r do if s.[!l] <> s.[!r] then if s.[!l] = 'x' then (incr l; incr ans) else if s.[!r] = 'x' then (decr r; incr ans)
  else (print_endline "-1"; exit 0) else (incr l; decr r) done; Printf.printf "%d\n" !ans

Measured memory_bytes: 2688
n = int( input() )

a = [ 0 ] * n
b = [ 0 ] * n
c = [ 0 ] * n
for i in range( n ):
    a[ i ], b[ i ], c[ i ] = map( int, input().split() )
#    print( a[ i ], b[ i ], c[ i ] )

dpa = a[ 0 ]
dpb = b[ 0 ]
dpc = c[ 0 ]
for i in range( 1, n ):
    dpa_new = max( dpb+a[ i ], dpc+a[ i ] )
    dpb_new = max( dpa+b[ i ], dpc+b[ i ] )
    dpc_new = max( dpa+c[ i ], dpb+c[ i ] )
    dpa = dpa_new
    dpb = dpb_new
    dpc = dpc_new

print( max( dpa, dpb, dpc ) )


Measured memory_bytes: 14836
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long 
#define il inline
ll x,k,d,ans;
int main(){
    cin>>x>>k>>d; x=abs(x);
    ll rem=x/d;
    if (rem<=k){
        k-=rem; x-=rem*d;
        if (k%2==0){
            ans=x;
        }else{
            ans=abs(x-d);
        }
    }else{
        x-=k*d;
        ans=x;
    }
    cout<<ans;
}

Measured memory_bytes: 3636
import sys
h, w = map(int, input().split())

if h == 1 or w == 1:
    print(1)
    sys.exit()
count_1 = (h+1) // 2
count_2 = h // 2

loop_num = w // 2
add_num = w - (loop_num * 2)
print((count_1+count_2) * loop_num + (count_1 * add_num))


Measured memory_bytes: 3060
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){
  char s[10],t[10],u[10];
  int a=0,b=0,flag=0,flag2=0;
  
  scanf("%s",&s); printf(" "); scanf("%s",&t);
  scanf("%d",&a); printf(" "); scanf("%d",&b);
  scanf("%s",&u);
  
  flag=strcmp(s,u);
  flag2=strcmp(t,u);
  
  if(flag==0){
    a--;
  }
  if(flag2==0){
    b--;
  }
  
  printf("%d %d",a,b);
}

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

int main() {
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a, a+3);
  if (a[0]==5 && a[1]==5 && a[2]==7) {
    cout << "YES";
  }
  else
    cout << "NO";
}

Measured memory_bytes: 256