akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd (int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;



int main () {
	SpeedForce;
	setIO();
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	ll ans = a[1];
	int ptr = 2;
	int cur = 0;
	for (int i = 3; i <= n; ++i) {
		ans += a[ptr];
		++cur;
		if(cur == 2) {
			++ptr;
			cur = 0;
		}
	}

	cout << ans << '\n';

	return Accepted;
}

// B...a

Measured memory_bytes: 18520
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]

    for i in range(H):
        c = 0
        for j in range(W):
            if S[i][j] == '#':
                c = 0
            else:
                L[i][j] = c
                c += 1
        c = 0
        for j in range(W - 1, -1, -1):
            if S[i][j] == '#':
                c = 0
            else:
                R[i][j] = c
                c += 1

    for j in range(W):
        c = 0
        for i in range(H):
            if S[i][j] == '#':
                c = 0
            else:
                U[i][j] = c
                c += 1
        c = 0
        for i in range(H - 1, -1, -1):
            if S[i][j] == '#':
                c = 0
            else:
                D[i][j] = c
                c += 1

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] + 1)

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 203944
#include<stdio.h>

int main(){
  int a[5];
  for(int i=0;i<5;i++){
    scanf("%d",&a[i]);
  }
  int k,f=1;
  scanf("%d",&k);
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
      if(a[i]-a[j] > k){
        f=0;
      }
    }
  }
  if(f){
    printf("Yay!");
  }else{
    printf(":(");
  }

  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<math.h>

int koch(double x1,double y1,double x2,double y2,int n){
  if(n==0){
    printf("%f %f\n",x2,y2);
    return 0;
  }
  double Sx,Sy,Tx,Ty,Ux,Uy;
  Sx=(x2-x1)/3+x1;
  Sy=(y2-y1)/3+y1;
  Tx=(x2-x1)*2/3+x1;
  Ty=(y2-y1)*2/3+y1;
  Ux=(cos(M_PI/3)*(Tx-Sx)-sin(M_PI/3)*(Ty-Sy))+Sx;
  Uy=(sin(M_PI/3)*(Tx-Sx)+cos(M_PI/3)*(Ty-Sy))+Sy;
  koch(x1, y1, Sx, Sy, n-1);
  koch(Sx, Sy, Ux, Uy, n-1);
  koch(Ux, Uy, Tx, Ty, n-1);
  koch(Tx, Ty, x2, y2, n-1);
  
}
int main(){
  int n;
  double x1=0.0,y1=0.0;
  double x2=100.0,y2=0.0;
  scanf("%d",&n);
  printf("0.00000000 0.00000000\n");
  koch(x1,y1,x2,y2,n);
  return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> x(n);
    for(int i=0;i<n;i++) cin >> x[i];
    int ans=10000000;
    for(int place=0;place<=100;place++){
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=(place-x[i])*(place-x[i]);
        }
        ans=min(ans,sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>

using namespace std;

int father[100005];
int n, q;

int find(int a)
{
	//注意：不能压缩路径
	//路径压缩只能在不关注爹的情况下用 
	/*if(father[a] == a)
		return a;
	else
		return father[a] = find(father[a]);*/
	return a==father[a]?a:find(father[a]);
}

int main()
{
	while(cin>>n>>q and n and q)
	{
		for(int i = 1; i <= n; ++i)
			father[i] = i;
	
		int tx;
		for(int i = 2; i <= n; ++i)
			scanf("%d", &father[i]);	//注意：不需要unite， 因为这不是判断在不在一个集合内 
	
		char oper;
		long long ans = 0;
		for(int i = 1; i <= q; ++i)
		{
			cin>>oper>>tx;
			switch(oper)
			{
				case 'Q':
					ans += find(tx);
					break;
				case 'M':
					father[tx] = tx;
					break;
			}
		}
		printf("%lld\n", ans);
	}
}


Measured memory_bytes: 3512
#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
#define m 1000000007
#define MAXN 1000001
#define satya ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define cil(a,b) (((a-1)/b)+1)
//#define init int t;cin>>t;while(t--)
#define in(a) ll a;scanf("%lld",&a)
#define ine(a,b) ll a,b;scanf("%lld lld",&a,&b)



ll spf[MAXN]; 

void sieve1() 
{ 
	spf[1] = 1; 
	for (int i=2; i<MAXN; i++) 

		spf[i] = i; 

	for (int i=4; i<MAXN; i+=2) 
		spf[i] = 2; 

	for (int i=3; i*i<MAXN; i++) 
	{ 
		if (spf[i] == i) 
		{ 
			for (int j=i*i; j<MAXN; j+=i) 

				if (spf[j]==j) 
					spf[j] = i; 
		} 
	} 
} 

ll  getFactorization(int x) 
{ 
	vector<int> ret; 
	long long int p=0;
	while (x != 1) 
	{ 
		ret.push_back(spf[x]); 
		x = x / spf[x]; 
	} 
	sort(ret.begin(),ret.end());
	for(int i=0;i<ret.size()-1;i++) 
	{
	    if(ret[i]!=ret[i+1])
	    p=p+ret[i];
	}
	p=p+ret[ret.size()-1];
	return p;
} 

ll d[1000055],u=0;
	bool prime[100001]; 
void Sieve(int n) 
{ 
// 	bool prime[n+1]; 
//	ll u=0;
	memset(prime, true, sizeof(prime)); 

	for (int p=2; p*p<=n; p++) 
	{ 
		if (prime[p] == true) 
		{ 
			for (int i=p*2; i<=n; i += p) 
				prime[i] = false; 
		} 
	} 

	for (int p=2; p<=n; p++) 
	if (prime[p]) 
	{
	    d[u]=p;
	    u++;
	}
} 

ll minverse(ll x,ll n,ll M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return minverse((x*x)%M,n/2,M);
    else                             //n is odd
        return (x*minverse((x*x)%M,(n-1)/2,M))%M;

}
// ll prime(ll n){
//     ll i;
//     if(n==1||n==0)
//     return 0;
//     for(i=2;i<sqrt(n);i++)
//     {
//         if(n%i==0)
//         return 0;
//     }
//     return 1;
// }
int ftemp(int d)
{
    if(d==1)
    return 1;
   ll  temp=0;
   for(ll i=2;i<=d;i++)
   {
       if(d%i==0){
           if(prime[i]){
       if(d%(i*i)==0)
       {
           return 0;
       }
       temp++;
       }
       }
   }
   if(temp%2==0)
   return 1;
   return -1;
}
int main() {
       satya;
     //sieve1(); 
     Sieve(100000);
     ll p=0;
     ll n,k;
     cin>>n;
     ll a[n],i;
     vector<pair<ll,ll>>v;
     for(i=0;i<n;i++)
     {
         cin>>a[i];
         v.push_back(make_pair(a[i],i+1));
     }
     sort(v.begin(),v.end());
     for(i=0;i<n;i++)
     {
         cout<<v[i].second<<" ";
     }
     cout<<endl;
   return 0;
}

Measured memory_bytes: 3440
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <queue>
#include <string>

using namespace std;

const double PI = 3.14159265358979;

int G[101][101];
bool visited[101];
int timex[101][2];
int deep[101];
int now_time = 1;
int n;

void dfs(int node) {

	if (!visited[node]) {
		visited[node] = 1;
		timex[node][0] = now_time++;
		for (int i = 0; i < n; i++)	{
			if (G[node][i] && visited[i] == 0) {
				dfs(i);
			}
		}
		timex[node][1] = now_time++;
	}
}

void dfs_stack(int node) {

	stack<int> st;
	st.push(node);
	visited[node] = 1;
	timex[node][0] = now_time++;
	while (!st.empty()) {
		int ver = st.top();

		bool flag = false;
		for (int i = 0; i < n; i++)	{
			if (G[ver][i] && visited[i] == 0) {
				visited[i] = 1;
				timex[i][0] = now_time++;
				st.push(i);
				flag = true;
				break;
			}
		}
		if (!flag) {
			timex[ver][1] = now_time++;
			st.pop();
		}
	}
}

void bfs(int node, bool reach) {

	queue<int> Q;
	visited[node] = 1;
	if (!reach) deep[node] = -1;
	Q.push(node);

	while (!Q.empty()) {

		int top = Q.front();
		Q.pop();
		for (int i = 0; i < n; i++)	{
			if (G[top][i] && !visited[i]) {
				Q.push(i);
				visited[i] = 1;
				if (reach)
					deep[i] = deep[top] + 1;
				else
					deep[i] = -1;
			}
		}
	}
}


int main() {
	
	cin >> n;

	for (int i = 0; i < n; i++)	{
		int id, degree;
		cin >> id >> degree;
		for (int j = 0; j < degree; j++) {
			int idx; cin >> idx;
			G[id - 1][idx - 1] = 1;
		}
	}

	bool first = true;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			bfs(i, first);
			first = false;
		}
	}
	

	for (int i = 0; i < n; i++) {
		cout << i + 1 << " " << deep[i] << endl;
	}


	return 0;
}



Measured memory_bytes: 3108
#include<stdio.h>
#include<string.h>
#define MAX 1000
 
typedef struct dice{
 int num[7];
}dice;
 
 
 
 
int main(){
dice D;
int i,j;
int temp;
int q;
int mae,ue;
 
for(i=1;i<=6;i++)scanf("%d",&D.num[i]);
 
scanf("%d",&q);
 
for(i=0;i<q;i++){
 scanf("%d %d",&ue,&mae);
 
 if(D.num[1]==ue && D.num[2]!=mae){
 
  for(j=0;j<3;j++){
   temp=D.num[2];
   D.num[2]=D.num[4];
   D.num[4]=D.num[5];
   D.num[5]=D.num[3];
   D.num[3]=temp;
   if(D.num[2]==mae)break;
  }
 
 }
 
else if(D.num[1]!=ue && D.num[2]==mae){
 
 for(j=0;j<3;j++){
  temp=D.num[1];
  D.num[1]=D.num[4];
  D.num[4]=D.num[6];
  D.num[6]=D.num[3];
  D.num[3]=temp;
  if(D.num[1]==ue)break;
 }
 
}
 
else if(D.num[1]!=ue && D.num[2]!=mae){
 
 for(j=0;j<=3;j++){
  temp=D.num[1];
  D.num[1]=D.num[4];
  D.num[4]=D.num[6];
  D.num[6]=D.num[3];
  D.num[3]=temp;
  if(D.num[1]==ue)break;
 }
 
if(D.num[1]!=ue){
 
for(j=0;j<3;j++){
 temp=D.num[1];
 D.num[1]=D.num[2];
 D.num[2]=D.num[6];
 D.num[6]=D.num[5];
 D.num[5]=temp;
 if(D.num[1]==ue)break;
}
}
 
 
 
 
 
 for(j=0;j<3;j++){
   temp=D.num[2];
   D.num[2]=D.num[4];
   D.num[4]=D.num[5];
   D.num[5]=D.num[3];
   D.num[3]=temp;
   if(D.num[2]==mae)break;
  }
 
 
}
 
printf("%d\n",D.num[3]);
 
}
 
return 0;
}


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

int main(){
    string str;
    int i, cnt = 0;
    cin >> str;

    for(i = 0; i < str.size(); i++){
        if(str[i] == '+'){
            cnt++;
        }else{
            cnt--;
        }
    }

    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 50;

struct Part {
	char mozi;
	int right, left, up, down;
	int height, width;
};

int kaijou(unsigned int num)
{
	int ret = 1;

	for (unsigned int i = num; i > 1; i--) {
		ret *= i;
	}

	return ret;
}

string solve()
{
	int H, W;
	char grid[MAX][MAX];
	bool flag = false;
	vector<Part> parts;

	cin >> H >> W;
	
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> grid[i][j];
		}
	}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (grid[i][j] != '.') {
				bool f = true;
				for (unsigned int k = 0; k < parts.size(); k++) {
					if (grid[i][j] == parts[k].mozi) {
						parts[k].up = min(i, parts[k].up);
						parts[k].down = max(i, parts[k].down);
						parts[k].left = min(j, parts[k].left);
						parts[k].right = max(j, parts[k].right);
						f = false;
						break;
					}
				}

				if (f == true) {
					Part part;
					part.mozi = grid[i][j];
					part.up = i;
					part.down = i;
					part.right = j;
					part.left = j;
					parts.push_back(part);
				}
			}
		}
	}

	if (parts.empty() == true) {
		return "SAFE";
	}
	else {
		for (unsigned int i = 0; i < parts.size(); i++) {
			parts[i].height = parts[i].right - parts[i].left + 1;
			parts[i].width = parts[i].down - parts[i].up + 1;
		}
	}

	vector<vector<int>> permutation(kaijou(parts.size()));
	vector<int> p;
	for (int i = 0; i < parts.size(); i++) {
		p.push_back(i);
	}

	int cur = 0;
	do {
		permutation[cur] = p;
		cur++;
	} while (next_permutation(p.begin(), p.end()));

	for (int i = 0; i < kaijou(parts.size()); i++) {
		vector<vector<char>> temp(H, vector<char>(W, '.'));
		for (int j = 0; j < parts.size(); j++) {
			for (int y = parts[permutation[i][j]].up; y <= parts[permutation[i][j]].down; y++) {
				for (int x = parts[permutation[i][j]].left; x <= parts[permutation[i][j]].right; x++) {
					temp[y][x] = parts[permutation[i][j]].mozi;
				}
			}
		}


		bool f = true;
		for (int k = 0; k < H; k++) {
			for (int l = 0; l < W; l++) {
				if (grid[k][l] != temp[k][l]) {
					f = false;
					goto Label;
				}
			}
		}
	Label:
		if (f == true) {
			return "SAFE";
		}
	}

	return "SUSPICIOUS";
}

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

	for (int i = 0; i < n; i++) {
		cout << solve() << endl;
	}

	return 0;
}

Measured memory_bytes: 3548
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

const i64 mod = 998244353;
i64 n;
vector<i64> d;
int main() {
  cin >> n;
  read_n(d, n);

  i64 dmax = 0;
  vector<i64> c(n);
  for (i64 x : d) {
    c[x]++;
    dmax = max(dmax, x);
  }

  if (d[0] != 0 || c[0] != 1) {
    cout << 0 << endl;
    return 0;
  }

  i64 ans = 1;
  for (i64 x = 1; x <= dmax; ++x) {
    for (i64 i = 0; i < c[x]; ++i) {
      (ans *= c[x - 1]) %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
n = int(input())
sn = input().strip()

count = 0
for i in range(1000):
    lucky_num = False
    num = str(i).zfill(3)
    c = 0
    for j in range(n):
        if sn[j] == num[c]:
            c += 1
        if c >= 3:
            lucky_num = True
            break
    if lucky_num:
        count += 1

print(count)


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

using namespace std;

int main(){

    int N;
    cin >> N;
    vector<int> A;
    A.reserve(N);

    int temp;
    int count = 0;
    long long int sum = 0;
    int minimum = 10e9 + 1;
    for(int i = 0; i < N; i++){
        cin >> temp;
        A[i] = temp;
        if(temp < 0){
            count++;
        }
        sum += abs(temp);
        minimum = min(minimum, abs(temp));
    }

    long long int ans = 0;
    if(count % 2 == 0){
        ans = sum;
    }
    else{
        ans = sum - 2 * minimum;
    }

    cout << ans << "\n";

    return 0;
}

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

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

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

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

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

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  int q;
  cin >> s >> q;

  deque<char> d;
  for(char c : s) d.push_back(c);
  string buf1 = "", buf2 = "";
  bool is_rev = false;
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if(t==1){
      is_rev = !is_rev;
    } else{
      int f1;
      char c;
      cin >> f1 >> c;
      if(!is_rev){
        if(f1 == 1) d.push_front(c);
        else d.push_back(c);
      }else{
        if(f1 == 1) d.push_back(c);
        else d.push_front(c);
      }
    }
  }

  if(!is_rev){
    while(!d.empty()){
      cout << d.front();
      d.pop_front();
    }
  }else{
    while(!d.empty()){
      cout << d.back();
      d.pop_back();
    }
  }
  cout << endl;
}


Measured memory_bytes: 976
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>

using namespace std;

int main(void){
    long long h, w;
    char a[100][100];
    cin >> h >> w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> a[i][j];
        }
    }
    for(int i=0;i<w+2;i++){
        cout << "#";
    }
    cout << endl;
    for(int i=0;i<h;i++){
        cout << "#";
        for(int j=0;j<w;j++){
            cout << a[i][j];
        }
        cout << "#" << endl;;
    }
    for(int i=0;i<w+2;i++){
        cout << "#";
    }
    cout << endl;

    return 0;

}

Measured memory_bytes: 256
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

// Author:: Subash Singha Roy
// Institution:: Jalpaiguri Government Engineering College

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod (int)(1e9+7)
#define fr(i,a,b) for(ll i=a;i<b;i++)
#define frr(i,a,b) for(ll i=a-1;i>=b;i--)
#define tc(t) int t;cin >>t;while(t--)
#define pb(i) push_back(i)
#define rr return 0
#define mp make_pair
#define pr  pair <ll,ll> 
#define ff first
#define ss second
#define inf 999999999999999999
ll mult(ll a,ll b, ll p=mod){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=mod){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = mod) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n%p; n = n * n%p;} return r;}
ll inv(ll a, ll p = mod) {return fpow(a, p - 2, p);}
bool sa(const pair<int,int> &a,const pair<int,int> &b){return (a.second<b.second);}
bool fd(const pair<int,int> &a,const pair<int,int> &b){return (a.first>b.first);}
bool sd(const pair<int,int> &a,const pair<int,int> &b){return (a.second>b.second);}

int main(){
fio
ll n,m;
cin>>n>>m;
string s[n+5];
fr(i,0,n){
    cin>>s[i];
}
ll dp[n+5][m+5];
fr(i,0,n){
    fr(j,0,m){
        dp[i][j]=0;
    }
}
fr(i,0,n){
    if(s[i][0]=='.'){
        dp[i][0]=1;
    }
    else{
        break;
    }
}
fr(j,0,m){
    if(s[0][j]=='.'){
        dp[0][j]=1;
    }
    else{
        break;
    }
}
fr(i,1,n){
    fr(j,1,m){
            if(s[i][j]=='.'){
                if(s[i-1][j]=='.')
                    dp[i][j]=(dp[i][j]%mod+dp[i-1][j]%mod)%mod;
                if(s[i][j-1]=='.')
                    dp[i][j]=(dp[i][j]%mod+dp[i][j-1]%mod)%mod;
            }
        }
    }
cout<<dp[n-1][m-1]%mod<<"\n";
rr;}
        

Measured memory_bytes: 9216
#include <stdio.h>

int main() {
  int point_x[4], point_y[4];
  scanf("%d %d %d %d", &point_x[0], &point_y[0], &point_x[1], &point_y[1]);
  int vector[2];
  vector[0] = point_x[1] - point_x[0];
  vector[1] = point_y[1] - point_y[0];
  point_x[2] = point_x[1] - vector[1];
  point_y[2] = point_y[1] + vector[0];
  point_x[3] = point_x[2] - vector[0];
  point_y[3] = point_y[2] - vector[1];
  printf("%d %d %d %d\n", point_x[2], point_y[2], point_x[3], point_y[3]);
  return 0;
}


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

using namespace std;

int main(){
    int d, n, t = 1, ans = 0;
    cin >> d >> n;
    for(int i = 0; i < d; i++){
        t *= 100;
    }
    if(n == 100) n++;
    ans = t * n;
    cout << ans << endl;
    return 0;
}

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

typedef long long ll;

const ll M = 1e9+7;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)
//a,bの範囲的にこれだけ配列を用意していけば十分

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}

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

  fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<300000; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }

  ll ans;
  for(ll i=1;i<=k;i++){
    ans=comb(n-k+1,i)*comb(k-1,i-1)%M;
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 4992
import functools

import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def inpm(line):
    return [inp() for _ in range(line)]


def inpfm(line):
    return [inpf() for _ in range(line)]


def inpsm(line):
    return [inps() for _ in range(line)]


def inlm(line):
    return [inl() for _ in range(line)]


def inlfm(line):
    return [inlf() for _ in range(line)]


def inlsm(line):
    return [inls() for _ in range(line)]


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')

a, o, b = inls()
if o=='+':
    print(int(a) + int(b))
else:
    print(int(a) - int(b))


Measured memory_bytes: 3684
function Main(s){
  s = s.split(" ").map(a=>+a);
  var ans = 0;
  if(s[1] === 100) s[1]++;
  if(s[0] === 0)ans = s[1];
  else if(s[0] === 1)ans = 100 * s[1];
  else ans =10000 * s[1];
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));

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

int main() {
    int k;
    cin >> k;
    ll ans = 0;
    for (int i = 1; i <= k; ++i) {
        for (int j = 1; j <= k; ++j) {
            for (int l = 1; l <= k; ++l) {
                ans += __gcd(i, __gcd(j, l));
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3636
n = int(input())
SQ  = []
for i in range(n):
    s,q = input().split()
    SQ.append([s,q,i+1])
SQ.append(['zzzzzzzzzzzzzz',0,i+2])
X = sorted(SQ)
res = []
city = X[0][0]
for i in range(n+1):
    if X[i][0] == city:
        res.append([int(X[i][1]),X[i][2]])
    else:
        res.sort(reverse=True)
        for r in res:
            print(r[1])
        res = [[int(X[i][1]),X[i][2]]]
        city = X[i][0]

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

signed main() {
	ll n, a, b;
	scanf("%lld %lld %lld", &n, &a, &b);

	ll Max = a + b*(n - 1), Min = b + a*(n-1);


	if (Min > Max)
		printf("0\n");
	else 
		printf("%lld\n", Max - Min+1);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

int main() {
    int N; cin >> N;
    vector<int> V(N);
    vector<int> C(N);
    for (int i = 0; i < N; i++) {
        cin >> V[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }

    int ans = 0;
    for (int tmp = 0; tmp < (1 << 20); tmp++) {
        bitset<20> s(tmp);
        int x = 0;
        int y = 0;
        for (int i = 0; i < N; i++) {
            if (s.test(i)) {
                x += V[i];
                y += C[i];
            }
        }
        chmax(ans, x - y);
    }

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

Measured memory_bytes: 256
//verma_ankit484

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
const int mod = (int) 1e9+7;

using namespace std;
//using namespace __gnu_pbds;

//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


int32_t main() {
  IOS
  #ifdef AV
  freopen("input.txt", "r", stdin);
  #endif
  string s, t;
  cin >> s >> t;
  int ans = 0;
  for (int i = 0; i < (int)s.length(); i++) {
    if (s[i] != t[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3796
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n = I()
    a = [LI() + [_] for _ in range(n)]
    r = 0
    la = sorted(a,key=lambda x: [-x[0],-x[0]])
    ra = sorted(a,key=lambda x: [x[1],x[0]])
    u = set()
    li = 0
    ri = 0
    tr = 0
    c = 0
    for i in range(len(a)//2 + len(a) % 2):
        while li < n and la[li][2] in u:
            li += 1
        if c < la[li][0]:
            tr += la[li][0] - c
            c = la[li][0]
        u.add(la[li][2])

        while ri < n and ra[ri][2] in u:
            ri += 1
        if ri == n:
            break
        if c > ra[ri][1]:
            tr += c - ra[ri][1]
            c = ra[ri][1]
        u.add(ra[ri][2])

    r = tr + abs(c)
    u = set()
    li = 0
    ri = 0
    tr = 0
    c = 0
    for i in range(len(a)//2 + len(a) % 2):
        while ri < n and ra[ri][2] in u:
            ri += 1
        if c > ra[ri][1]:
            tr += c - ra[ri][1]
            c = ra[ri][1]
        u.add(ra[ri][2])

        while li < n and la[li][2] in u:
            li += 1
        if li == n:
            break
        if c < la[li][0]:
            tr += la[li][0] - c
            c = la[li][0]
        u.add(la[li][2])
    if tr + abs(c) > r:
        r = tr + abs(c)

    return r


print(main())



Measured memory_bytes: 45232
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
#define N 111
int win[ N ][ N ];
void build(){
  win[ 0 ][ 0 ] = 0;
  for( int s = 1 ; s < N ; s ++ )
    for( int i = 0 ; i <= s ; i ++ ){
      int j = s - i;
      int twin = 0;
      for( int k = 1 ; k + k <= i and not twin ; k ++ )
        if( not win[ i - k - k ][ j + k ] )
          twin = 1;
      for( int k = 1 ; k + k <= j and not twin ; k ++ )
        if( not win[ i + k ][ j - k - k ] )
          twin = 1;
      win[ i ][ j ] = twin;
    }
  for( int i = 0 ; i < 21 ; i ++ )
    for( int j = 0 ; j < 21 ; j ++ )
      printf( "%d%c" , win[ i ][ j ] , " \n"[ j == 20 ] );
}
LL a , b;
void init(){
  cin >> a >> b;
}
void solve(){
  if( abs( a - b ) <= 1 )
    puts( "Brown" );
  else
    puts( "Alice" );
}
int main(){
  //build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAXN 1000000+10
#define MOD 998244353

using namespace std;

int n,K;
long long Ans[MAXN];
int l[233],r[233];

int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=K;i++)
		scanf("%d%d",&l[i],&r[i]);
	Ans[1] = 1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=K;j++)
		{
			if(i<l[j]) continue;
			if(i>=r[j]) Ans[i] = (Ans[i] + (Ans[i-l[j]] - Ans[i-r[j]-1] + MOD)) % MOD;
			else Ans[i] = (Ans[i] + Ans[i-l[j]]) % MOD;
		}
		Ans[i] = (Ans[i] + Ans[i-1]) % MOD;
	}
	cout<<(Ans[n]-Ans[n-1]+MOD)%MOD;
	return 0;
}

Measured memory_bytes: 5332
#define _CRT_SECURE_NO_WARNINGS


#include<iostream>
#include<string>
#include<vector>
#include<algorithm>


using namespace std;

int euclid_gcd(int a, int b) {
	int tmp_a, tmp_b;//tmp_a>tmp_b	

	if (a < b) {
		tmp_a = b;
		tmp_b = a;
	}
	else {
		tmp_a = a;
		tmp_b = b;
	}

	if (tmp_b == 0) {
		return tmp_a;
	}
	else {
		return euclid_gcd(tmp_b, tmp_a%tmp_b);
	}
}


int gcd_multi(vector<int> x) {

	vector<int> gcds(x.size() / 2 + (x.size() % 2));

	if (x.size() == 1) {
		return x.front();
	}

	if (x.size() == 2) {
		return euclid_gcd(x[0], x[1]);
	}

	for (int i = 0; i < x.size() / 2; ++i) {
	
		gcds[i] = euclid_gcd(x[i * 2], x[i * 2 + 1]);
	
	}

	if (x.size() % 2 == 1) {

		gcds.back() = x.back();
	}


	return gcd_multi(gcds);
}

int main(void) {

	int n, start;

	cin >> n >> start;

	vector<int> x(n);

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

		std::cin >> x[i];
	}

	x.push_back(start);

	sort(x.begin(), x.end());

	vector<int> w(n);

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

		w[i] = abs(x[i] - x[i + 1]);
	}

	cout << gcd_multi(w);

	return 0;
}


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

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}

#define PRINT_VECTOR_MAX 100
template <class S> void print(vector<S> &v){for(ll i=0; i<(ll)min(v.size(),PRINT_VECTOR_MAX); i++){cerr << v[i] << ' ';}cerr << endl;}
template <class S> void print(vector<vector<S>> &v) {for (ll i = 0; i < (ll)min(v.size(),PRINT_VECTOR_MAX); i++) {for (ll j = 0; j < (ll)min(v[i].size(),PRINT_VECTOR_MAX); j++) {cerr << v[i][j] << ' ';}cerr << endl;}}

void Main();
int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	Main();
	return 0;
}

void Main(){
	int n; cin >> n;
	vector<int> c(n-1), f(n-1), s(n-1);
	rep(i,n-1) cin >> c[i] >> s[i] >> f[i];
	rep(start, n-1){
		int time = s[start] + c[start];
		for(int i = start + 1; i < n-1; i++){
			if(time < s[i]){
				time = s[i];
			}else{
				time = (time + f[i] - 1) / f[i] * f[i];
			}
			time += c[i];
		}
		cout << time << endl;
	}
	cout << 0 << endl;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 998244353
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;

#define N 3005

ll dp[N][N];
ll a,b;
ll get(ll i, ll j)
{
    if(i<a || j<b)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(i == a && j == b)
        return dp[i][j] = 1;
    return dp[i][j] = ((get(i-1,j)*(j))%mod + (get(i,j-1)*(i))%mod - (get(i-1,j-1)*(i-1)*(j-1))%mod + mod)%mod;    
}

int main()
{
  FAST/**/
   
   memset(dp,-1,sizeof(dp));
   ll c,d;
   cin>>a>>b>>c>>d;
   
   ll ans = get(c,d);
   cout<<ans;
   return 0;        
}  
  
          
   

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

#define si(v) int(v.size())
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep2(i, n, m) for (ll i = n; i <= (m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (m); --i)

template<class T, class U> void chmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> void chmin(T &a, U b) { if (b < a) a = b; }

using ll = long long;
using ld = long double;
using namespace std;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);

  string s; cin >> s;

  if (s[0] == s[1] && s[1] == s[2]) cout << "Yes\n";
  else if (s[1] == s[2] && s[2] == s[3]) cout << "Yes\n";
  else cout << "No\n";
  
  return (0);
}

Measured memory_bytes: 3604
package main

import (
	"bufio"
	_ "container/heap"
	"fmt"
	"os"
	_ "sort"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
const MOD = int(1e+9) + 7
const INF = 1 << 60

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	defer wtr.Flush()
	S := sc.nextStr()
	ans := 0
	var dp [2019]int
	for i := 1; i < len(S)+1; i++ {
		var ndp [2019]int
		d := int(S[i-1] - '0')
		for j := 0; j < 2019; j++ {
			ndp[(j*10+d)%2019] += dp[j]
		}
		ans += ndp[0]
		ndp[d] += 1
		dp = ndp
	}

	fmt.Fprintln(wtr, ans)
}


Measured memory_bytes: 2564
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

constexpr ll MOD = 1e9+7;
constexpr ll LIM = 1e5+10;

ll mod_pow(ll x, ll exp) {
  if(exp == 1) {
    return x;
  }
  if(exp % 2) {
    return (mod_pow(x, exp - 1) * x) % MOD;
  }
  ll y = mod_pow(x, exp / 2);
  return (y * y) % MOD;
}

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  VL as(n);
  FOR(a,as) {
    cin >> a;
  }
  ll fact_n = 1;
  REP(i,1,n+1) {
    fact_n = (fact_n * i) % MOD;
  }
  VL inv(LIM);
  REP(i,1,LIM) {
    inv[i] = mod_pow(i, MOD-2);
  }
  VL inv_sum(LIM);
  inv_sum[0] = 0;
  REP(i,1,LIM) {
    inv_sum[i] = (inv_sum[i-1] + inv[i]) % MOD;
  }
  ll ans = 0;
  REP(i,0,n) {
    ll expect = (inv_sum[i+1] + inv_sum[n-i] - 1) % MOD;
    ll count = (expect * fact_n) % MOD;
    ll cost = (as[i] * count) % MOD;
    ans = (ans + cost) % MOD;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2560
#include<stdio.h>
int main(void)
{
  	int i,K,N,M;
  	if((scanf("%d %d",&K,&N)) == 1);
  ;
  int A[N];
  	for(i=0;i < N ; i++){
  	  if((scanf("%d",&A[i])) == 1);
      ;
    }
  	M = K - A[N-1] + A[0];
  	for(i=0;i < N-1;i++){
      if((A[i+1] - A[i]) > M)
        M = A[i+1] - A[i];
    }
  	printf("%d",K - M);
}


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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}
long long fast_exp(long long base, long long exp, long long mod = MOD) {
    long long tot = 1;
    for(;exp > 0;exp >>= 1) {
       if((exp & 1) == 1) tot = tot * base % mod;
       base = base * base % mod;
    }
    return tot;
}

long long dp[100005][13];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    // help i dont know digit dp

    string s; cin >> s;
    int n = s.size();

    dp[0][0] = 1;

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

        for(int rem = 0; rem < 13; ++rem){

            if(s[i] != '?'){
                //cout << "USING " << (rem + (s[i] - '0') * fast_exp(10, n - i, 13)) % 13 << " " << dp[i][rem] << endl;
                dp[i + 1][(rem + (s[i] - '0') * fast_exp(10, n - i - 1, 13)) % 13] = dp[i][rem];
                dp[i + 1][(rem + (s[i] - '0') * fast_exp(10, n - i - 1, 13)) % 13] %= MOD;
            } else {
                for(int dig = 0; dig < 10; ++dig){
                    dp[i + 1][(rem + dig * fast_exp(10, n - i - 1, 13)) % 13] += dp[i][rem];
                    dp[i + 1][(rem + dig * fast_exp(10, n - i - 1, 13)) % 13] %= MOD;
                    //cout << i + 1 << " " << rem << " " << dp[i + 1][(rem + dig * fast_exp(10, n - i, 13)) % 13] << endl;
                }
            }

        }

    }

    cout << dp[n][5] << "\n";


    return 0;

}


Measured memory_bytes: 10604
/**
*    created: 13.06.2020 20:56:30
**/

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

int main() {
    ll a, b, v, w, t;
    cin >> a >> v >> b >> w >> t;
    if(a<b){
        if(v*t+a>=w*t+b) cout << "YES" << endl;
        else cout << "NO" << endl;
    }else{
        if(-v*t+a<=-w*t+b) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(){
   int m,n;
   scanf("%d %d",&m,&n);
   int a[n];
    int max=m;
   for(int i=0;i<n;i++){
      scanf("%d",&a[i]);
   }

   for(int i=0;i<n;i++){
      max-=a[i];
   }
   if(max<0){
      printf("%d",-1);
   }else{
      printf("%d",max);
   }
   
   return 0;
}


Measured memory_bytes: 1700
#include <bits/stdc++.h>
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; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

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

ll pow(ll a, ll n, ll m) {
	ll ret = 1LL;
	for (; n > 0LL; n >>= 1LL, a = a * a % m) {
		if (n % 2LL == 1LL) {
			ret = ret * a % m;
		}
	}
	return ret;
}

int main(){
    ll K;
    string S;
    cin>>K>>S;
    ll N = S.size();
    ll ans = 0LL;
    ll t = pow(26LL,K,mod);
    ll s = 1;
    for(ll i = N-1; i < N+K; i++){
        ans= (ans + t*s)%mod;
        t = (((t*25LL)%mod)*pow(26LL,mod-2,mod))%mod;
        s = (((s * (i+1))%mod)*pow(i-N+2,mod-2,mod))%mod;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5336
package main

import (
	"fmt"
	"strings"
)

func main() {
	var a, b int
	var s string
	fmt.Scan(&a, &b, &s)

	if len(s) == a+b+1 && s[a] == '-' && !strings.Contains(s[:a], "-") && !strings.Contains(s[a+1:], "-") {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;
int main(void)

{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, A, B;
	cin >> A >> B >> N;
	int min = (A <= B) ? A : B;
	vector<int> result;
	for (int i = 1; i <= min; i++)
	{
		if (A % i == 0 && B % i == 0)
			result.push_back(i);
	}
	sort(result.begin(), result.end());

	cout << result[result.size() - N];
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {

        //solve_148_A();
        //solve_148_B();
        //solve_148_C();
        solve_148_D();
        return;
    }

    private static void solve_148_D() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N+1];
        int counter = 0;

        for(int i=1; i<=N; i++){
            A[i] = sc.nextInt();
        }

        for(int i=1; i<=N; i++){
            if(A[i] == (counter+1)){
                counter++;
            }else{
                //  Nothing
            }
        }
        if(counter == 0){
            counter = -1;
        }else{
            counter = N - counter;
        }
        System.out.println(counter);
    }
}

Measured memory_bytes: 82672
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))//b=0x3f max
typedef long long LL;
using namespace std;
const int INF =0x3f3f3f3f;

int i,n,m;


int main()
{
    LL x,y;
    scanf("%lld%lld",&x,&y);
    if(x==1||y==1){
        if(x==y)
            printf("1\n");
        else
        printf("%lld\n",x+y-1-2);
    }
    else if(x==2||y==2){
        printf("0\n");
    }
    else{
        LL m=(x-2)*(y-2);
        printf("%lld\n",m);
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main(void){
    int n, m;
    int a[50+5], b[50+5];
    int c[50+5], d[50+5];
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)scanf("%d %d", &a[i], &b[i]);
    for(int i=0; i<m; i++)scanf("%d %d", &c[i], &d[i]);
    
    for(int i=0; i<n; i++){
        int min=abs(a[i]-c[0])+abs(b[i]-d[0]);
        int checkpoint=0;
        for(int j=1; j<m; j++){
            int dist=abs(a[i]-c[j])+abs(b[i]-d[j]);
            if(min>dist){
                min=dist;
                checkpoint=j;
            }
        }
        printf("%d\n", checkpoint+1);
    }
    return 0;
}


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

#define endl '\n'
#define D(x) cout << #x << " = " << (x) << endl;

string ans;
void dfs (int i, vector<int> v, string s) {
  if (i == 4) {
    int t = v[0];
    string out;
    out += to_string(v[0]);

    for (int j = 1; j < 4; ++j) {
      out += s[j] + to_string(v[j]);
      if (s[j] == '+') t += v[j];
      else t -= v[j];
    }
    out += "=7";
    if (t == 7) ans = out;
    return;
  }

  dfs(i + 1, v, s + "+");
  dfs(i + 1, v, s + "-");
}

int main() {
  vector<int> v(4);

  string n;
  cin >> n;

  for (int i = 0; i < 4; ++i) {
    v[i] = n[i] - '0';
  }

  dfs(0, v, "");
  cout << ans << endl;

  return 0;
}

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

int main ()
{
    int n; cin>>n;
    string s; cin>>s;
    int i=0, j=s.size()-1;
    int count =0;
    while (i<n && j>=0 && i<j)
    {
        while (i<n && s[i]=='R')
            i++;
        while (j>=0 && s[j]=='W')
            j--;
        if (i<n && j>=0 && i<j)
        {
            swap(s[i],s[j]);
            count ++;
        }
    }
    cout <<count <<endl;
}


Measured memory_bytes: 3740