akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;

struct vertex {
    long long counter;
    vector<int> next;
};

void add(struct vertex *vertices, int p, long long x) {
    vertices[p].counter += x;
    for (int i = 0; i < vertices[p].next.size(); i++)
        add(vertices, vertices[p].next[i], vertices[p].counter);
}

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

    int N, Q;
    cin >> N >> Q;
    struct vertex *vertices = new struct vertex[N + 1];
    for (int i = 0, a, b; i < N - 1; i++) {
        cin >> a >> b;
        vertices[a].next.push_back(b);
    }
    for (int i = 0, p, x; i < Q; i++) {
        cin >> p >> x;
        vertices[p].counter += x;
    }

    add(vertices, 1, 0);

    cout << vertices[1].counter;
    for (int i = 2; i <= N; i++)
        cout << ' ' << vertices[i].counter;
    cout << '\n';

    return 0;
}

Measured memory_bytes: 21120
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
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++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
typedef priority_queue<string> priquest;
typedef priority_queue<string,vector<string>,greater<string>> rpriquest;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}

const ll big=1000000007;
ll exp(ll x,ll y){
    if(y==0)return 1;
    if(x==1||x==0)return x;
    if(y%2==1)return (exp(x,y-1)*x)%big;
    ll t=exp(x,y/2);
    return (t*t)%big;
}
void chmin(ll a,ll b){
    if(a>b)a=b;
    return;
}

int main(){
  int n,k;cin >> n >> k;
  vector<int> h(n);
  rep(i,n)cin >> h[i];
  vector<long long> ans(100100,10000000000);
  ans[0]=0;
  rep(i,n){
    rep2(j,1,k+1)ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]));
  }
  cout << ans[n-1] << endl;
}


Measured memory_bytes: 1408
//2020年3月21日現在

#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>
#include <cstdio>

using namespace std;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }

namespace {
    // printElems(&a[0], &a[n]);　みたいな感じで使う。
    void printElems(const int* begin, const int* end)
    {
        for (const int* p = begin; p != end; ++p) {
            std::cout << *p << ' ';
        }
        std::cout << std::endl;
    }
}

#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-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)
#define FOR(i,j,n) for(int i=j; i < n; i++)
#define souatari rep1(i,n-1)rep(j,i)
#define souatari1 for(int i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<int,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;
const ll BIG = 10000000000000000;




int main(){
	ll k;
	cin >> k;
	if(k <= 9){
		prints(k);
		return 0;
	}


	vector<ll> num[11];
	rep1(i,9)num[1].push_back(i);
//	prints(num[1].size());

 	int cnt = 2;

	for(int i = 2; int(k-num[i-1].size())>0; i++){
		k-=num[i-1].size();
//		prints(k);
		rep(j,num[i-1].size()){
			if(num[i-1][j]%10 != 0){
				num[i].push_back(num[i-1][j]*10+num[i-1][j]%10-1);
			}
			num[i].push_back(num[i-1][j]*10+num[i-1][j]%10);

			if(num[i-1][j]%10 != 9){
				num[i].push_back(num[i-1][j]*10+num[i-1][j]%10+1);
			}
//			num[i].push_back(num[i-1][j]+to_string(int(num[i-1][j][i-1]-'0')-1));

//			if(num[i-1][j][i-1] != '9'){
//				num[i].push_back(num[i-1][j]+to_string(int(num[i-1][j][i-1]-'0')+1));
//			}
		}
		sort(num[i].begin(),num[i].end());
		cnt = i;
	}

	prints(num[cnt][k-1]);


	return 0;
}



Measured memory_bytes: 1976
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pat(ll n, ll x,vector<ll>total) {
	ll ans;
	if (n == 0 && x == 1)return 1;
	if (x <= 1)ans = 0;
	else if (x <= 1 + total.at(n - 1))ans = pat(n - 1, x - 1, total);
	else if (x <= 2 + total.at(n - 1))ans = pat(n - 1, total.at(n - 1), total) + 1;
	else if (x <= 2 + total.at(n - 1) * 2)ans = pat(n - 1, total.at(n - 1), total) + 1 + pat(n - 1, x - total.at(n - 1) - 2, total);
	else ans = pat(n - 1, total.at(n - 1), total) * 2 + 1;
	return ans;
}

int main() {
	ll n, x;
	cin >> n >> x;
	vector<ll>total(51);
	for (int i = 0; i < 51; i++) {
		if (i == 0)total.at(i) = 1;
		else total.at(i) = total.at(i - 1) * 2 + 3;
	}
	ll ans = pat(n, x,total);
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val (n, m) = readIntegerList()
    val boxes = BooleanArray(n)
    val counts = IntArray(n) { 1 }
    boxes[0] = true
    repeat(m) {
        val (x, y) = readIntegerList().map { it - 1 }
        if (counts[x] == 1) {
            if (boxes[x]) {
                boxes[y] = true
                boxes[x] = false
            }
        } else {
            if (boxes[x]) {
                boxes[y] = true
            }
        }

        counts[x]++
        counts[y]--
    }

    println(boxes.count { it })
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 60064
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}

int main(void){
  fast_io
  int n,k;cin>>n>>k;
  vector<int> H;
  rep(i,n){
    int h;cin>>h;
    H.push_back(h);

  }
  sort(all(H));
  reverse(all(H));
  rep(i,k){
    if(i >= n) break;
    H[i] = 0;
  }
  ll ans = 0;
  rep(i,n){
    ans += H[i];
  }
  cout<<ans<<endl;
  return 0;
}

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

using namespace std;

#define endl "\n"
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = 2e9;
const int MAX=1e7;
const int mod=1e9+7;


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

	string s;
	while(cin>>s){
		s[3]='8';
		cout<<s<<endl;
	}

	return 0;
}


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

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

char grid[25][25];

void init()
{
	for (int i = 0; i < 25; i++){
		for (int j = 0; j < 25; j++){
			grid[i][j] = '#';
		}
	}
}

int search(int ny, int nx)
{
	grid[ny][nx] = '#';
	
	int sum = 1;
	for (int i = 0; i < 4; i++){
		int ty = ny + dy[i];
		int tx = nx + dx[i];
		if (grid[ty][tx] == '.'){
			if (grid[ty][tx] == '.'){
				sum += search(ty, tx);
			}
		}
	}
	
	return (sum);
}

int main()
{
	int h, w;
	while (scanf("%d %d", &w, &h), w + h){
		init();
		
		int sy, sx;
		for (int i = 1; i <= h; i++){
			for (int j = 1; j <= w; j++){
				scanf(" %c", &grid[i][j]);
				
				if (grid[i][j] == '@'){
					sy = i;
					sx = j;
				}
			}
		}
		
		printf("%d\n", search(sy, sx));
	}
	
	return 0;
}

Measured memory_bytes: 1204
// Problem : H - Grid 1
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_h
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
 
#define endl "\n"
#define int long long
#define FAST {ios_base::sync_with_stdio(false);cin.tie(NULL);}
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
#define rep(n) for(int i=0;i<(n);i++)
#define rrep(n) for(int i=(n)-1;i>=0;i--)
#define mem(a,b) memset((a),(b),sizeof (a))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define INF (long long) 1e18
#define MOD 1000000007
int dp[1005][1005];
int32_t main(){
      int n,m;
      cin>>n>>m;
      bool arr[1005][1005];
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  char ch;
                  cin>>ch;
                  if(ch == '#') arr[i][j] = 0;
                  else arr[i][j] = 1;
            }
      }
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  if(i==1 && j==1) dp[i][j] = 1;
                  else if(arr[i][j] == 1){
                        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
                  }else {
                        dp[i][j] = 0;
                  }
            }
      }
      cout<<dp[n][m]<<endl;
      return 0;
}




Measured memory_bytes: 12392
#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>
#include<iomanip>
#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;
constexpr double pi=3.14159265358979;
 
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 n;
 cin>>n;
 vector<ll>l(n);
 map<ll,ll>mp;
 rep(i,n){
   cin>>l[i];
   mp[l[i]]++;
 }
 sort(begin(l),end(l));
 l.pb(INF);
 ll ans=0;
 int m1=0,m2=1;
 for(int i=2;i<n;++i){
   for(int j=0;j<i-1;++j){
     ll x=l[i]-l[j];
     auto itr=upper_bound(l.begin()+j+1,l.begin()+(i),x);
     if(mp[*itr]==1&&*itr>=l[i])continue;
     ans+=distance(itr,l.begin()+i+1)-1;
   }
 }
 cout<<ans<<"\n";
 return;
}
 
signed main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
  cout<<fixed<<setprecision(20);
	solve();
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    int N, L;
    cin >> N >> L;
    int ans = 0;
    int l = 0, r = 0;
    cin >> l;
    for(int i = 1; i < N; i++) {
        cin >> r;
        if(l + r >= L) ans = i;
        l = r;
    }
    cout << (ans ? "Possible" : "Impossible") << endl;
    if(ans) {
        for(int i = 1; i < ans; i++) {
            cout << i << endl;
        }
        for(int i = N - 1; i >= ans; i--) {
            cout << i << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<utility>
#include<cstdio>
using namespace std;
#define rep(i,x,n) for(int i=x;i<n;i++)
using ll=long long;

string ans;

void ps(int n,char a){
    for(int i=0;i<n;i++) ans+=a;
    return;
}

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    int ans=0;
    for(int i=1;i<=n;i++){
        string m=to_string(i);
        int c=0;
        for(int j=0;j<m.size();j++){
            c+=(int)(m[j]-'0');
        }
        if(c>=a&&c<=b) ans+=i;
    }
    cout<<ans<<endl;
}    

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

long long x;
long long i = 0;
long long num_pathi[51] = {};

long long dfs(long long n, long long j)
{
    long long count = 0;
    
    if(n == 1){
        i++;
        return 1;
    }
    if(i >= x)
        return 0;
    
    i++;
    if(i >= x)
        return count;
    
    if(i + (n - 3) / 2 < x){
        count += num_pathi[j-1];
        i += (n - 3) / 2;
    }
    else{
        count += dfs((n - 3) / 2, j-1);
        i++;
    }
    
    if(i >= x)
        return count;

    i++;
    count++;
    if(i >= x)
        return count;

    if(i + (n - 3) / 2 < x){
        count += num_pathi[j-1];
        i += (n - 3) / 2;
    }
    else{
        count += dfs((n - 3) / 2, j-1);
        i++;
    }
    
    return count;
}

int main(void){
    // Your code here!
    long long n, num = 1;
    
    cin >> n >> x;
    
    num_pathi[0] = 1;
    for(long long i = 0; i < n; i++){
        num = num * 2 + 3;
        num_pathi[i+1] = num_pathi[i] * 2 + 1;
    }

    cout << dfs(num, n) << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define Rep(i, m, n) for(ll i = m; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x, y, z) max((x), max((y), (z)))
#define tmin(x, y, z) min((x), min((y), (z)))
#define MINUS(a) memset(a, 0xff, sizeof(a))
#define ZERO(a) memset(a, 0, sizeof(a))
const ll INF = 1LL << 60;
const ll MM = 1000000000; const ll MOD = MM + 7; const ll MMM=9223372036854775807;//2^63 -1
#define ADD(a,b) a = (a + ll(b)) % MOD
#define MUL(a,b) a = (a * ll(b)) % MOD
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
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;}
template<typename A, size_t N, typename T> void FILL(A (&array)[N], const T &val){ fill( (T*)array, (T*)(array+N), val );}
using Graph = vector<vector<ll>>;
ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
ll ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1}, ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//cout << fixed << setprecision(10);


int main(){
    ll x, k, d, ans;
    cin >> x >> k >> d;
    if(x < 0) x *= -1;
    ans = x % d;
    if(chmin(ans, abs(x % d - d))) ans *= -1;
    // 最小位置までの必要移動回数がk以上の場合
    if((x-ans)/d >= k) cout << abs(x - d*k) << endl;
    // 最小位置到着後、回数が余ってしまう場合
    else{
        // 残り偶数回
        if((k - (x-ans)/d) % 2 == 0) cout << abs(ans) << endl;
        // 残り奇数回
        else{
            if(ans < 0) cout << ans + d << endl;
            else cout << abs(ans - d) << endl;
        }
    }
}


Measured memory_bytes: 3524
/*B - Power Socket*/
#include <bits/stdc++.h>

using namespace std;

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

	int A, B;

	cin >> A >> B;
	int ans = 0;
	int aux = 1;

	while(aux < B){
		aux--;
		aux += A;
		ans++;
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 256
import sys

n, m, *ab = map(int, sys.stdin.read().split())
g_1 = set()
g_n = set()
for a, b in zip(*[iter(ab)] * 2):
    if a == 1 or b == 1:
        g_1.add(b)
    elif a == n or b == n:
        g_n.add(a)

def main():
    return 'POSSIBLE' if g_1 & g_n else 'IMPOSSIBLE'

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 46660
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repe(i,n) for (int i = 0; i <= (n); ++i)
#define repe1(i,n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(k,v) emplace_back(k,v)
#define ct(res) cout << res << "\n";
#define vi vector<int>
#define vl vector<ll>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {return (a%b) ? gcd(b, a%b) : b;}
ll modPow(ll x, ll n) {
    if(n==0) return 1;
    ll res = modPow(x*x%MOD, n/2);
    if(n&1) res=res*x%MOD;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool j = true;
    int i = 1;
    while(true) {
        int x; cin >> x;
        if (x==0) {
            return 0;
        }
        cout << "Case " << i << ": " << x << "\n";
        ++i;
    }
}



Measured memory_bytes: 3092
#include <iostream>

using namespace std;

int main()
{
    int total,value;
    cin >> total;
    while(total!=0) {
        for(int i=0; i<9; ++i) {
            cin >> value;
            total-=value;
        }
        cout << total << endl;
        cin >> total;
    }
    return 0;
}

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

int main() {
  int h,w;
  cin >> h >> w;
  
  vector<string> rows(h);
  
  for(int i=0; i<h; i++){
    cin >> rows.at(i);
  }
  
  for(int i=0; i<h; i++){
    for(int j=0;j<w; j++){
      if(rows[i][j]=='#'){
        cout << "#";
      } else {
        int counter = 0;
        if(i != 0 && rows[i-1][j] == '#') counter++;
        if(i != 0 && j != 0 && rows[i-1][j-1] == '#') counter++;
        if(i != 0 && j != w-1 && rows[i-1][j+1] == '#') counter++;
        if(j != 0 && rows[i][j-1] == '#') counter++;
        if(j != w-1 && rows[i][j+1] == '#') counter++;
        if(i != h-1 && rows[i+1][j] == '#') counter++;
        if(i != h-1 && j != 0 && rows[i+1][j-1] == '#') counter++;
        if(i != h-1 && j != w-1 && rows[i+1][j+1] == '#') counter++;
        
        cout << counter;        
      }
    }
    cout << endl;
  }
  
}

Measured memory_bytes: 256
package main

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

var (
	sc = bufio.NewScanner(os.Stdin)
	mod int = 1e9 + 7
)

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	N := getInt()
	var ds []int
	for i := 0; i < N; i++ {
		ds = append(ds, getInt())
	}

	sum := 0
	for i := 0; i < len(ds); i++ {
		for j := i; j < len(ds); j++ {
			if i == j {
				continue
			}

			sum += ds[i] * ds[j]
		}
	}
	fmt.Println(sum)
}

func getInt() int {
	sc.Scan()
	str := sc.Text()
	value, _ := strconv.Atoi(str)
	return value
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func printIntArray(array []int) {
	strArray := fmt.Sprint(array)
	fmt.Println(strArray[1 : len(strArray) - 1])
}

func calcMod(x int) int {
	return x % mod
}


Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

long mp[2020][2020] = {0};

int main(void) {
  cout.precision(12);

  // N <= 2000, M <= 2000
  long N, M;
  cin >> N >> M;

  vector<long> S(N);
  rep (i, N) cin >> S[i];

  vector<long> T(M);
  rep (i, M) cin >> T[i];

  for (long n = 0; n <= N; n++) {
    for (long m = 0; m <= M; m++) {
      if (n == 0) {
        mp[n][m] = 1;
        continue;
      }
      if (m == 0) {
        mp[n][m] = 1;
        continue;
      }
      if (S[n-1] == T[m-1]) mp[n][m] = mp[n-1][m] + mp[n][m-1];
      else mp[n][m] = mp[n-1][m] + mp[n][m-1] - mp[n-1][m-1];
      mp[n][m] = (mp[n][m] + MOD) % MOD;
    }
  }

  cout << mp[N][M] << endl;

  return 0;
}


Measured memory_bytes: 31872
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;i++)
const ll INF=1e15;
const int inf=1e9;
const ll MOD=1000000007;

int main(){
    int N,K;cin>>N>>K;
    int info[200005];
    rep(i,200005)info[i]=0;
    rep(i,N){
        int m;cin>>m;
        info[m]++;
    }
    sort(info,info+200005);
    int ans=0;
    rep(i,200005-K)ans+=info[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
import os
from sys import stdin, stdout


def solve(tc):
  n = int(stdin.readline().strip())
  rem = n%1000
  print(1000-rem if rem>0 else 0)


tcs = 1
tc = 1
while tc <= tcs:
  solve(tc)
  tc += 1

Measured memory_bytes: 61684
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<complex>
#include<stack>
#include<queue>
#include<unordered_map>
#include<map>
using namespace std;

int main() {
  string s, t;
  cin >> s;
  int i;
  for (i = 0; i < s.size(); i++) {
    if (s[i] == '0') {
      t += "0";
    } else if (s[i] == '1') {
      t += "1";
    } else {
      if (!t.empty()) {
        t.pop_back();
      }
    }
  }
  cout << t << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}
int a[101][101],ans=-1,check[101],n;

void calc(int now,int g,int count){
  if(count>ans && ans!=-1) return;
  if(now==g){
    if(ans==-1){
      ans=count;
      return;
    }
    else{
      ans=min(ans,count);
      return;
    }
  }
  if(check[now]>count) check[now]=count;
  else return;
  lp(i,n+1){
    if(a[now][i]==1)
      calc(i,g,count+1);
  }
}

int main(){
  cin>>n;
  lp(i,n){
    int x,y;
    cin>>x>>y;
    lp(j,y){
      int z;
      cin>>z;
      a[x][z]=1;
    }
  }
  lp(i,n){
    lp(j,101){
      check[j]=1000;
    }
    ans=-1;
    calc(1,i+1,0);
    cout<<i+1<<" "<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl

using ld = double;
using P = complex<ld>;
using G = vector<P>;
const ld pi = acos(-1);
const ld eps = 1e-10;
const ld inf = 1e12;

ld cross(const P& a, const P& b) { return a.real()*b.imag() - a.imag()*b.real(); }
ld dot(const P& a, const P& b) { return a.real()*b.real() + a.imag()*b.imag(); }

using C = pair<ld, P>;
#define rad first
#define pnt second

C smallest_enclosing_disc(vector<P> ps){
    auto c3 = [](const P &a, const P &b, const P &c){
        ld A = norm(b - c);
        ld B = norm(c - a);
        ld C = norm(a - b);
        ld S = abs(cross(b - a, c - a));
        P p = (A*(B+C-A)*a + B*(C+A-B)*b + C*(A+B-C)*c) / (4*S*S);
        ld r = abs(p - a);
        return make_pair(r, p);
    };

    auto c2 = [](const P &a, const P &b){
        P c = (a + b) / (ld)2;
        ld r = abs(a - c);
        return make_pair(r, c);
    };

    auto in_circle = [](const P &a, const C &c){
        return norm(a - c.pnt) <= c.rad*c.rad + eps;
    };

    int n = ps.size();
    random_shuffle(ps.begin(), ps.end());
    C c = c2(ps[0], ps[1]);
    for(int i = 2; i < n; ++i){
        if(!in_circle(ps[i], c)){
            c = c2(ps[0], ps[i]);
            for(int j = 1; j < i; ++j){
                if(!in_circle(ps[j], c)){
                    c = c2(ps[j], ps[i]);
                    for(int k = 0; k < j; ++k){
                        if(!in_circle(ps[k], c)){
                            c = c3(ps[i], ps[j], ps[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}

int main(){
    srand(time(0));
    int n;
    cin >> n;
    vector<P> ps(n);
    for(int i = 0; i < n; ++i){
        ld x,y;
        cin >> x >> y;
        ps[i] = P(x,y);
    }

    printf("%.9lf\n", (double)smallest_enclosing_disc(ps).rad);
}

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

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

using ll = long long;

int main() {
    int n;
    ll  ans = 0LL;
    std::string s;
    std::map<std::string, ll> mp;
    std::cin >> n;

    rep(i, n) {
        std::cin >> s;
        std::sort(s.begin(), s.end());
        ++mp[s];
    }

    for (auto m : mp) {
        ans += (m.second * (m.second - 1)) / 2;
    }

    std::cout << ans << std::endl;

    return 0;
}



Measured memory_bytes: 11136
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

typedef pair<char, char> pc;

int main() {
  int n,q;
  string s;

  cin >> n >> q;
  cin >> s;

  vector<char> t(q), d(q);
  rep(i, q) cin >> t[i] >> d[i];

  ll a, b;
  {
    auto check = [&] (int mid) {
      ll mmid = mid;
      for (int i = 0; i < q; ++i) {
        if (s[mmid] == t[i]) {
          if (d[i] == 'R') mmid += 1;
          else mmid -= 1;
        }
        // 左に落ちた
        if (mmid < 0) return true;
      }
      // 落ちない or 右に落ちる
      return false;
    };

    int l = 0, r = n - 1;
    while (r - l >= 0) {
      int mid = (l + r) / 2;
      if (check(mid)) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    a = l;
  }

  {
    auto check = [&] (int mid) {
      ll mmid = mid;
      for (int i = 0; i < q; ++i) {
        if (s[mmid] == t[i]) {
          if (d[i] == 'R') mmid += 1;
          else mmid -= 1;
        }
        // 右に落ちた
        if (mmid >= n) return true;
      }
      // 落ちない or 左に落ちる
      return false;
    };

    int l = 0, r = n - 1;
    while (r - l >= 0) {
      int mid = (l + r) / 2;
      if (check(mid)) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }

    b = r;
  }
//  cout << a << " " << b << endl;
  if (b - a < 0) cout << 0 << endl;
  else cout << b - a + 1 << endl;
}


Measured memory_bytes: 900
#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;
typedef pair<int, pair<int, int> > E; //(dest, (dist, cost))
typedef pair<int, pair<int, int> > Elem; //(-cost, (pos, money))

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

int main() {
    int n,m,l;
    while(cin >> n >> m >> l, n) {
        vector<E> G[n];
        rep(i,m) {
            int a,b,d,e;
            cin >> a >> b >> d >> e;
            a--,b--;
            G[a].push_back(make_pair(b, make_pair(d,e)));
            G[b].push_back(make_pair(a, make_pair(d,e)));
        }
        
        set<pair<int, int> > vis;
        priority_queue<Elem> q;
        q.push(make_pair(0, make_pair(0, l)));
        while (!q.empty()) {
            Elem e = q.top();
            int cost = -e.first;
            int pos = e.second.first;
            int money = e.second.second;
            q.pop();
            if (vis.find(make_pair(pos, money)) != vis.end()) continue;
            vis.insert(make_pair(pos, money));
            if (money < 0) continue;
            if (pos == n - 1) {
                cout << cost << endl;
                break;
            }
            rep(i, G[pos].size()) {
                E edge = G[pos][i];
                int dest = edge.first;
                int dist = edge.second.first;
                int num = edge.second.second;
                q.push(make_pair(-cost, make_pair(dest, money - dist)));
                q.push(make_pair(-(cost + num), make_pair(dest, money)));
            }
        }
    }
    return 0;
}

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

using namespace std;

using ll = long long;

const long long MOD_NUMBER = 1000000007;
const double PI = 3.14159265358979323846;

int main() {
  ll x, y;
  cin >> x >> y;
  if (4 * x < y || y % 2 || y < 2 * x) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 3620
N,K = map(int,input().split())
p = list(map(int,input().split()))

# 期待値の累積和リストを生成
ex_list = list() 
for i in range(len(p)):
	if i != 0:
		ex_list.append(((1+p[i])/2)+ex_list[-1])
	else:
		ex_list.append((1+p[i])/2)

ans = ex_list[K-1]
for i in range(N-K):
	# print(i,ex_list[i],ex_list[i+K])
	ex = abs(ex_list[i] - ex_list[i+K])
	if ans < ex:
		ans = ex
print(ans)

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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(){
    ll n,m,v,p;cin>>n>>m>>v>>p;
    ll t=m*v;
    vl a(n);
    rep(i,n)cin>>a[i];
    sort(all(a));
    int r=n-1,l=0;
    while(r-l>1){
        int mid=(r+l)/2;
        ll sum=(mid+1)*m,now=a[mid]+m;
        if(now<a[n-p]){
            l=mid;
            continue;
        }
        for(int i=mid+1;i<=n-p;++i){
            sum+=now-a[i];
        }
        if(sum+(p-1)*m<t){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    ll ans=r;
    ll sum=(l+1)*m,now=a[l]+m;
    if(now>=a[n-p]){
    for(int i=l+1;i<=n-p;++i){
        sum+=now-a[i];
    }
    if(sum+(p-1)*m>=t){
        ans=l;
    }        
    }
    cout<<n-ans<<endl;
}


Measured memory_bytes: 1024
def main():
    X,Y=map(int,input().split())
    if X==1 and Y==1:
        print('1000000')
    elif (X==1 and Y==2) or (X==2 and Y==1):
        print('500000')
    elif (X==1 and Y==3) or (X==3 and Y==1):
        print('400000')
    elif (X==1 and Y>3) or (X>3 and Y==1):
        print('300000')
    elif (X==2 and Y==2):
        print('400000')
    elif (X==2 and Y==3) or (X==3 and Y==2):
        print('300000')
    elif (X==2 and Y>3) or (X>3 and Y==2):
        print('200000')
    elif (X==3 and Y==3):
        print('200000')
    elif (X==3 and Y>3) or (X>3 and Y==3):
        print('100000')
    else:
        print('0')
        

        
if __name__=='__main__':
    main()


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

int main() {
    int N;
    cin >> N;
    if(N%10 == 2 || N%10 == 4 ||N%10 == 5 ||N%10 == 7 ||N%10 == 9 ){
        cout << "hon" << endl;
    }
    else if(N%10 == 3 ){
        cout << "bon" << endl;
    }
    else{
        cout << "pon" << endl;
    }
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,cnt=0;
  cin >>N;
  vector<int> a(N);
  for(int i=0;i<N;i++)
    cin>>a.at(i);
  
  for(int i=0;i<N;i++){
    while(1){
      if(a.at(i)%2!=0)
        break;
      a.at(i) /=2;
      cnt++;
    }
  }
  cout <<cnt<<endl;
}


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

int main(void) {
	int X;
	char buf[32], *ch;

	fgets(buf, sizeof(buf), stdin);
	ch = strtok(buf, " ");
	X = atoi(ch);

	if(X >= 30) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 2020
#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>


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(short i = 0; i < n; i++)



int main() {
    int n, m, d[50] = {};
    
    cin >> n >> m;
    REP(i, m){
        int a, b;
        cin >> a >> b;
        a--;b--;
        d[a]++;
        d[b]++;
    }
    
    REP(i, n){
        cout << d[i] << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i) < (N); (i)++)
#define all(V) V.begin(), V.end()
using i64 = int_fast64_t;
using P = pair<int,int>;

int main(){
    int N, M;
    cin >> N >> M;
    
    vector<int> S(N);
    vector<int> T(M);

    rep(i, N) cin >> S[i];
    rep(i, M) cin >> T[i];

    vector<vector<i64>> dp(N+1, vector<i64>(M+1, 0));
    rep(i, N+1) dp[i][0] = 1;
    rep(i, M+1) dp[0][i] = 1;

    const i64 MOD = 1e9 + 7;
    for(int i = 1; i <= N; i++ ){
        for(int j = 1; j <= M; j++){
            i64 diff = (dp[i-1][j] + dp[i][j-1]) % MOD;
            diff -= dp[i-1][j-1];
            if(diff < 0) diff += MOD;
            (dp[i][j] += diff) %= MOD;
            if(S[i-1] == T[j-1]) (dp[i][j] += dp[i-1][j-1]) %= MOD;
        }
    }

    cout << dp[N][M] << endl;
}


Measured memory_bytes: 31616
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll N, a, b; vector<ll> v;
int main() {
  scanf("%ld", &N);
  for(ll i = 1, t; i*i <= N; ++i) {
    if(N%i!=0) continue;
    v.push_back(i);
    t = N/i, v.push_back(t);
  }
  sort(v.begin(), v.end());
  a = v[v.size()/2-1], b = v[v.size()/2];
  printf("%ld", a+b-2);
}

Measured memory_bytes: 384
import java.util.Scanner;
   public class Main {
   public static void main(String[] args) {
     
        //sec--1 (definition)
        Scanner sc = new Scanner(System.in);
        String N = sc.next();
        
        //sec--2 (redefinition)
        N = N.substring(N.length() - 1);
         
        //sec--3 (branch)
        //if(N.equals(3)) {
        if(N.equals("2") || N.equals("4") || N.equals("5") || N.equals("7") || N.equals("9")) {
          System.out.println("hon");
        } else if (N.equals("0") || N.equals("1") || N.equals("6") || N.equals("8")) {
          System.out.println("pon");
        } else if (N.equals("3")) {
          System.out.println("bon");
        }
   }
}

Measured memory_bytes: 35640
class Main {
    public static void main(String args[]) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        // int[] keys = new int[n];
        BinaryTree binaryTree = new BinaryTree();
        for(int i=0; i<n; i++){
            String order = sc.next();
            switch(order){
                case "insert":
                    binaryTree.root = binaryTree.add(binaryTree.root, Integer.parseInt(sc.next()));
                    break;
                case "print":
                    binaryTree.print();
                    break;
                default:
                    break;
            }
        }
        
    }

    static class Node{
        int key;
        Node left;
        Node right;

        public Node(int key){
            this.key = key;
        }

    }

    static class BinaryTree{
        Node root = null;

        Node getRoot(){
            return this.root;
        }

        void print(){
            innorder(this.root);
            System.out.println();
            preorder(this.root);
            System.out.println();
        }
        void preorder( Node node){
            if(node == null){
                return;
            }
            System.out.print(" "+node.key);
            preorder(node.left);
            preorder(node.right);
        }
        void innorder(Node node){
            if(node == null){
                return;
            }   
            innorder(node.left);
            System.out.print(" "+node.key);
            innorder(node.right);
        }


        public Node add(Node current, int key){
            if(current == null) {
                return new Node(key);
            }
            if( key >= current.key){
                current.right = add(current.right, key);
            } else {
                current.left = add(current.left, key);
            }
            return current;
        }
    }
}




Measured memory_bytes: 192276
import java.util.Scanner;

public class Main 
{
	static int[] a;
	static int n;
	static int[] streak;
	static long MOD = 1000000007;
	static long[] dp;
	
	static long get(int i)
	{
		if(i<0||i>=n)return 1;
		else return dp[i];
	}
	
	static void test()
	{
		int n = 1000;
		System.out.println(n);
		for(int i = 0; i < n; i++)
		{
			System.out.println((int)(Math.random()*500));
		}
	}

	public static void main(String[] args) 
	{
//		test();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		int streaker = -1;
		int curstreak = 0;
		
		a = new int[n];
		streak = new int[n];
		
		for(int i = 0; i < n; i++)
		{
			a[i] = sc.nextInt();
			
			if(a[i] != streaker)
			{
				streaker = a[i];
				curstreak = 0;
			}
			curstreak++;
			streak[i] = curstreak;
		}
		
		long k = 1;
		dp = new long[n];
		long[] forcol = new long[200001];
		
		for(int i = 0; i < 200001; i++)
			forcol[i] = 0;
//		unlockedcol.add(-1);
		for(int i = 0; i < n; i++)
		{
			long cur = get(i-1);
			
			if(streak[i]==1)
			{
//				System.out.println("Go for " + i + ", streak " + streak[i]);
				cur = (cur + forcol[a[i]])%MOD;
				
				forcol[a[i]] = (forcol[a[i]] + get(i-1))%MOD;
			}
//			else cur = get(i-1);
			
			dp[i] = cur;
		}
		k=(dp[n-1])%MOD;
		if(k<0)k+=MOD;
		
//		System.out.println(Arrays.toString(streak));
//		System.out.println(Arrays.toString(dp));
		System.out.println(k);
	}

}


Measured memory_bytes: 86900
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    while(cin >> n, n){
        vector<int> v(n);
        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            v[i] = s.size();
        }
        vector<int> u{5, 7, 5, 7, 7, 100000};
        for (int i = 0; i < n; ++i) {
            int cur = 0, p = 0;
            int valid = true;
            for (int j = i; j < n; ++j) {
                p += v[j];
                if(u[cur] == p) cur++, p = 0;
                else if(u[cur] < p) valid = false;
            }
            if(valid && cur == 5){
                cout << i+1 << "\n";
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3136
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

ll lcm(ll n, ll m) { return (n / __gcd(n, m)) * m; }

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll h, w;
  cin >> h >> w;
  vector<string> mp(h);
  rep(i, h) cin >> mp[i];

  ll cnt = 0;
  rep(i, h) rep(j, w) if (mp[i][j] == '#') cnt++;

  string ans = "Impossible";
  if (cnt == h + w - 1) ans = "Possible";

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#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++)
const long long INF =  999999999;
const int MAX_V=10010;

int par[MAX_V],r[MAX_V];

void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    r[i]=0;
  }
}

//グループの根になっているちょうてんをかえす。
int find(int x){
  if(par[x]==x)return x;
  else return par[x]=find(par[x]);
}


bool same(int x,int y){
  return find(x)==find(y);
}

void unite(int x,int y){
  x=find(x);
  y=find(y);

  if(x==y)return;

  if(r[x]<r[y]){
    par[x]=y;
  }else {
    par[y]=x;
    if(r[y]==r[x])r[x]++;
  }
}

int n,q;

int main(){
  vector<int> ans;
  int s,x,y;
  cin >>n>>q;
  init(n);
  REP(i,q){
    cin >>s>>x>>y;
    if(!s){
      unite(x,y);
    }
    else if(s){
      if(same(x,y))ans.push_back(1);
      else ans.push_back(0);
    }
  }

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



Measured memory_bytes: 3372
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def bs(ar,eq,n) en=(eq==1 ? :>= : :>); ar.bsearch_index{|x|x.send(en,n)} end
def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n = gi
s = n.times.map{gi}.sort

sum = sum(s)
putsend(sum) unless sum%10==0

s.each do |ss|
  if ss%10==0
    next
  else
    sum -= ss
    putsend sum
  end
end

puts 0

Measured memory_bytes: 1788
N = int(input())
A = list(map(int,input().split()))

bunbo = 0
bunshi = 1
for i in range(N):
    tmp = 1
    for j in range(N):
        if i == j:
            continue
        else:
            tmp *= A[j]
    bunbo += tmp
    bunshi *= A[i]
    
print(bunshi/bunbo)

Measured memory_bytes: 3060
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,ans;
int main() {
	scanf("%lld",&n);
	for(LL i=1;i*i<=n;i++)
		if(n%i==0)
			ans=i+(n/i);
	printf("%lld\n",ans-2);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <map>
#include<set>
#include <cmath>
#include <stack>
#include<cstdio>
#include<stdio.h>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if ((b - 1) % (a - 1) == 0)cout << (b - 1) / (a - 1) << endl;
	else cout << (b - 1) / (a - 1) + 1 << endl;
}

Measured memory_bytes: 256
/** MIT License Copyright (c) 2018-2019 Vasilev Daniil **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
typedef long long ll;
//#define int ll
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
const long double EPS = 1e-12;
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//code starts here

void run() {
	str s;
	get s;
	int n = sz(s);
	int a[n];

	rep(i, 0, n)
		a[i] = (s[i] == 'A' || s[i] == 'G' || s[i] == 'C' || s[i] == 'T');

	int ans = 0;
	rep(i, 0, n) {
		rep(j, i, n) {
			if (a[j] == 0)
				break;
			ans = max(ans, j - i + 1);
		}
	}
	put ans;
}

signed main() {ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run();}



Measured memory_bytes: 256