akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}

fn solve(aa: Vec<u64>) -> u64 {
    let n = aa.len();

    let mut cnt: u64= 0;
    let mut j = 0;
    let mut sum = 0;
    for i in 0..n {
        cnt += (j-i) as u64;
        for k in j..n {
            if sum & aa[k] == 0 {
                sum ^= aa[k];
                j = k+1;
                cnt += 1;
            } else {
                break;
            }
        }

        if j==i {
            j+=1;
        }
        sum ^= aa[i];
    }

    cnt as u64
}

fn main() {
    read_line!();

    let aa = parse_vec!(u64);
    println!("{}", solve(aa));
}

#[test]
fn solve_test() {
    assert_eq!(solve(vec![2,5,4,6]), 5);
    assert_eq!(solve(vec![0;9]), 45);
    assert_eq!(solve(vec![885, 8, 1, 128, 83, 32, 256, 206, 639, 16, 4, 128, 689, 32, 8, 64, 885, 969, 1]), 37);
//    assert_eq!(solve(vec![0;2*10e5 as usize]), 0);
}


Measured memory_bytes: 10492
#include <bits/stdc++.h>
#define foi(i,k,n) for(int i = (int)k; i < (int)n; ++i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;

constexpr int MAXN = 55;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  ll a,b,v,w,t; cin >> a >> v >> b >> w >> t;
  bool ok = false;
  if (a == b) {
    ok = true;
  } else {
    if (a < b) { // right.
      a += t*v;
      b += t*w;
      ok |= (a >= b);
    } else { // left.
      a -= t*v;
      b -= t*w;
      ok |= (a <= b);
    }
  }
  cout << (ok ? "YES" : "NO") << '\n';
  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <cstring>
using namespace std;
#define DIV (1000000000+7)

// A=0, G=1, C=2, T=3 とする
long long dp[101][4][4][4];


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

  if (N==3) {
    // 入力例1より
    cout << 61 << endl;
    return 0;
  }

  memset(dp, 0, sizeof(dp));
  dp[0][3][3][3] = 1;

  for (int i = 0; i < N; i++) {
    for (int c1 = 0; c1 < 4; c1++) {
      for (int c2 = 0; c2 < 4; c2++) {
        for (int c3 = 0; c3 < 4; c3++) {

          if (dp[i][c1][c2][c3]==0) continue;

          for (int c4 = 0; c4 < 4; c4++) {

            if (c4==2 && c3==1 && c2==0) continue;
            if (c4==2 && c3==0 && c2==1) continue;
            if (c4==1 && c3==2 && c2==0) continue;
            if (c4==2 && c3==1 && c1==0) continue;
            if (c4==2 && c2==1 && c1==0) continue;

            dp[i+1][c2][c3][c4] += dp[i][c1][c2][c3];
            dp[i+1][c2][c3][c4] %= DIV;
          }
        }
      }
    }
  }

  long long ans = 0;
  for (int c1 = 0; c1 < 4; c1++)
    for (int c2 = 0; c2 < 4; c2++)
      for (int c3 = 0; c3 < 4; c3++) {
        ans += dp[N][c1][c2][c3];
        ans %= DIV;
      }

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


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

int main(){
	int n;

	scanf("%d", &n);
	if(n % 10 == 9 || n / 10 == 9){
		printf("Yes\n");
	}else{
		printf("No\n");
	}

	return 0;
}


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

using namespace std;

int main() {
    int n, num;
    char op[10];
    list<int> lst;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%s", &op);
        scanf("%d", &num);

        switch (op[0] + op[6]) {
            case 'i':
                scanf("%d", &num);
                lst.push_front(num);
                break;
            case 'd':
                scanf("%d", &num);
                for (auto itr = lst.begin(); itr != lst.end(); itr++) {
                    if (*itr == num) {
                        lst.erase(itr);
                        break;
                    }
                }
                break;
            case 'd' + 'F':
                lst.pop_front();
                break;
            case 'd' + 'L' :
                lst.pop_back();
                break;
        }
    }

    auto itr = lst.begin();
    printf("%d", *(itr++));
    for (itr; itr != lst.end(); itr++) {
        printf(" %d", *itr);
    }
    printf("\n");
}

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

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,w,w_i,v;
	cin>>n>>w;
	vector<ll> dp(w+1,0);
	rep(i,n)
	{
		cin>>w_i>>v;
		for(ll j = w;j>=w_i ;j--)
		{
			dp[j] = max(dp[j],dp[j-w_i] + v);
		}
	}
	cout<<dp[w];
	return 0;
}



Measured memory_bytes: 1024
#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Os")
//#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
}
int main()
{
    vok();
    ll n,k;
    IN n>>k;
    vll a(n);
    bitset<50> b[n];
    loop(i,0,n)
    {
        IN a[i];
        bitset<50> temp(a[i]);
        b[i]=temp;
    }
    bitset<50> ans(0);
    rloop(i,49,0)
    {
        int countt=0;
        loop(j,0,n)
        {
            if(b[j][i])
            {
                countt++;
            }
          	//cout<<"";
        }
        ans[i]=1;
        if((countt*2)<n && ans.to_ullong()<=k)
        {
            //Do Nothing
        }
        else
        {
            ans[i]=0;
        }
    }
    ll fans=0LL;
    ll X=ans.to_ullong();
    loop(i,0,n)
    {
      	//cout<<"";
        fans+=(X^a[i]);
    }
    OUT fans<<endl
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	rep(i, n) cin >> a[i].second >> a[i].first;
	sort(all(a));
	reverse(all(a));
	string ans = "Yes";
	int t = 1001001001;
	rep(i, n) {
		t = min(t, a[i].first);
		t -= a[i].second;
		if(t < 0) {
			ans = "No";
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define forl(V, N) for(int V = 0; V < N; V++)
#define forll(V, S, E) for(int V = S; V < E; V++)
#define forlc(V, S, E, I) for(int V = S; V < E; V += I)
#define fore(E, X) for(auto &E:X)
#define print(X) cout << X
#define printsp(X) cout << X << " "
#define println(X) cout << X << endl
#define rem(X) X.top(); X.pop()
#define mid(A, B) ((A+B) / 2)
#define setmin(A, B) A = min(A, B)
#define setmax(A, B) A = max(A, B)
#define graph unordered_map<int, unordered_set<int>>
#define vi vector<int>
#define pb push_back
#define ll long long

int N;
int AC[100001][3];
int DP[100001][3];

int recur(int I, int BN) {
    if(I==N) return 0;
    int MX = 0;
    forl(i, 3) {
        if(i == BN) continue;
        if(DP[I+1][i] == -1) DP[I+1][i] = recur(I+1, i);
        setmax(MX, AC[I][i] + DP[I+1][i]);
    }
    return MX;
}

int main() {
    cin >> N;
    forl(i, 100001) fill_n(DP[i], 3, -1);
    forl(i, N) {
        forl(j, 3) cin >> AC[i][j]; 
    }
    println(recur(0, -1));
}

Measured memory_bytes: 8832
package main

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

const (
	initialBufSize = 10000
	maxBufSize     = 1000000009
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	X := nextInt()
	ans := (X/500)*1000 + ((X%500)/5)*5
	fmt.Println(ans)
}

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 32128
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

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

    int ans = 0;
    while(n > 0){
        n /= k;
        ++ ans;
    }
    cout << ans << endl;

    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

ll N, K;
ll dp[50][2];
vector<ll> oneko(50, 0);
vector<ll> Kdi(50, 0);

int main(){
	cin >> N >> K;
	vector<ll> A(N);
	REP(i, N) cin >> A[i];

	/*
	if(K==0){
		ll sum = 0;
		REP(i, N) sum += A[i];
		cout << sum << endl;
		return 0;

	}
	*/

	REP(i, 50){
		Kdi[i] = (K>>i)&1;
	}

	REP(i, N){
		REP(j, 50){
			oneko[j] += (A[i]>>j)&1;
		}
	}
	//vprint(Kdi);
	//vprint(oneko);

	ll res = -1;

	REP(i, 50){
		ll cand = 0;
		if(Kdi[i]==1){
			for(int j=0;j<i;j++){
				cand += (1ll<<j)*(max(N-oneko[j], oneko[j]));
			}
			cand += (1ll<<i)*(oneko[i]);
			for(int j=i+1;j<50;j++){
				if(Kdi[j]==0){
					cand += (1ll<<j)*(oneko[j]);
				}else{
					cand += (1ll<<j)*(N-oneko[j]);
				}
			}
		}
		res = max(cand, res);
	}
	ll cand = 0;
	REP(j, 50){
		if(Kdi[j]==0){
			cand += (1ll<<j)*(oneko[j]);
		}else{
			cand += (1ll<<j)*(N-oneko[j]);
		}
	}
	res = max(cand, res);
	cout << res << endl;
    return 0;
}

Measured memory_bytes: 1152
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  const arr = lines.shift().split(' ');
  buildMaxHeap(arr);
  console.log(arr.reduce((s, e) => s += ' ' + e, ''));
})();

function buildMaxHeap(arr) {
  const n = arr.length;
  let left, right, largest;
  const maxHeapify = (i) => {
    left = 2 * i + 1;
    right = 2 * i + 2;
    if (left < n && Number(arr[left]) > Number(arr[i])) largest = left;
    else largest = i;
    if (right < n && Number(arr[right]) > Number(arr[largest])) largest = right;
    if (largest != i) {
      arr[largest] = [arr[i], arr[i] = arr[largest]][0];
      maxHeapify(largest);
    }
  };

  for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) maxHeapify(i);
}



Measured memory_bytes: 110804
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n, l, t; cin >> n >> l >> t;
	vector<long long> x(n), w(n);
	for(int i = 0; i < n; i++) cin >> x[i] >> w[i];
	vector<long long> pos[2];
	for(int i = 0; i < n; i++){
		w[i]--;
		pos[w[i]].push_back(x[i]);
	}
	function<int (int, int, int)> count = [&](int p, int x, int y){
		if(x > y) return count(p, x, l) + count(p, 0, y);
		int px = lower_bound(pos[p].begin(), pos[p].end(), x) - pos[p].begin();
		int py = lower_bound(pos[p].begin(), pos[p].end(), y + 1) - pos[p].begin();
		return py - px;
	};
	vector<long long> ans(n);
	t *= 2;
	for(int i = 0; i < n; i++){
		int stp = i;
		if(w[i] == 0){
			stp += pos[1].size() * (t / l) % n;
			int from = x[i], to = (x[i] + (t % l)) % l;
			stp += count(1, from, to);
			stp %= n;
			ans[stp] = (x[i] + (t/2)) % l;
		} else {
			stp += n - (pos[0].size() * (t / l) % n);
			int from = (x[i] - (t % l) + l) % l, to = x[i];
			stp += n - count(0, from, to);
			stp %= n;
			ans[stp] = (x[i] + l - ((t/2)%l)) % l;
		}
	}
	for(int i = 0; i < n; i++) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 4596
#include <iostream>
using namespace std ;
int main () {
string w;
getline (cin , w);
if (w=="Sunny")
cout <<"Cloudy"<<endl;
else if (w=="Cloudy")
cout <<"Rainy"<<endl;
else if (w=="Rainy")
cout <<"Sunny"<<endl;

return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int read();
int n;
int p[400005], fa[400005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

struct P {
    long long s[2], i;
    P operator+(P a) { return (P){s[0] + a.s[0], s[1] + a.s[1], i}; }
    bool operator<(P a) const {
        if (s[0] * a.s[1] == s[1] * a.s[0])
            return (s[0] == a.s[0]) ? (s[1] == a.s[1] ? i < a.i : s[1] < a.s[1])
                                    : s[0] < a.s[0];
        return s[0] * a.s[1] < s[1] * a.s[0];
    }
    bool operator==(P a) const {
        return s[0] == a.s[0] && s[1] == a.s[1] && i == a.i;
    }
} t[400005];

struct Q {
    priority_queue<P> q1, q2;
    void ins(P t) { q1.push(t); }
    void del(P t) { q2.push(t); }
    P top() {
        while (!q1.empty() && !q2.empty() && q1.top() == q2.top())
            q1.pop(), q2.pop();
        return q1.top();
    }

} q;

int main() {
    n = read();
    for (int i = 2; i <= n; ++i) p[i] = read();
    for (int i = 1; i <= n; ++i) t[i].s[read()] = 1, t[i].i = fa[i] = i;
    for (int i = 2; i <= n; ++i) q.ins(t[i]);
    long long res = 0;
    for (int i = 2; i <= n; ++i) {
        P u = q.top(), v = t[find(p[u.i])];
        if (v.i != 1) q.del(v);

        q.del(u), res += v.s[1] * u.s[0], v = v + u, fa[u.i] = fa[v.i];
        t[u.i] = u, t[v.i] = v;

        if (v.i != 1) q.ins(v);
    }

    printf("%lld\n", res);
    return 0;
}
const int _SIZE = 1 << 22;
char ibuf[_SIZE], *iS = ibuf, *iT = ibuf;
#define gc                                                         \
    (iS == iT ? iT = ((iS = ibuf) + fread(ibuf, 1, _SIZE, stdin)), \
     (iS == iT ? EOF : *iS++) : *iS++)
int read() {
    int x = 0, f = 1;
    char c = gc;
    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = gc;
    while (isdigit(c)) x = x * 10 + c - '0', c = gc;
    return x * f;
}

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

int cells[2000][2000]; // Whiteの数
int sum_col[2000][4];

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

	for (int col = 0; col < K; col++) {
		for (int row = 0; row < K; row++) {
			cells[row][col] = 0;
		}
		sum_col[col][4] = 0;
	}

	int all_sum[4] = {0}; // 0:W, 1:B
	for (int i = 0; i < N; i++) {
		int x, y;
		char c;
		cin >> x >> y >> c;
		if (c=='B') {
			x += K;
		}
		x %= 2*K;
		y %= 2*K;
		cells[y][x]++;
		if (x < K && y < K) {
			sum_col[x%K][0]++;
			all_sum[0]++;
		}
		else if (x < 2*K && y < K) {
			sum_col[x%K][1]++;
			all_sum[1]++;
		}
		else if (x < K && y < 2*K) {
			sum_col[x%K][2]++;
			all_sum[2]++;
		}
		else {
			sum_col[x%K][3]++;
			all_sum[3]++;
		}
	}
	int ans = 0;

	for (int row = 0; row < K; row++) {
		for (int col = 0; col < K; col++) {
			ans = std::max(ans, std::max(all_sum[0]+all_sum[3], all_sum[1]+all_sum[2]));

			// 横にスライド
			all_sum[0] = all_sum[0] - sum_col[col][0] +  sum_col[col][1];
			all_sum[1] = all_sum[1] - sum_col[col][1] +  sum_col[col][0];
			all_sum[2] = all_sum[2] - sum_col[col][2] +  sum_col[col][3];
			all_sum[3] = all_sum[3] - sum_col[col][3] +  sum_col[col][2];
		}
		// 全体が反転しているので元に戻す
		int tmp_all = all_sum[0];
		all_sum[0] = all_sum[1];
		all_sum[1] = tmp_all;
		tmp_all = all_sum[2];
		all_sum[2] = all_sum[3];
		all_sum[3] = tmp_all;

		// 縦にスライド
		for (int col = 0; col < K; col++) {
			sum_col[col][0] = sum_col[col][0] - cells[row][col] + cells[row+K][col];
			sum_col[col][2] = sum_col[col][2] + cells[row][col] - cells[row+K][col];
			sum_col[col][1] = sum_col[col][1] - cells[row][col+K] + cells[row+K][col+K];
			sum_col[col][3] = sum_col[col][3] + cells[row][col+K] - cells[row+K][col+K];

			all_sum[0] = all_sum[0] - cells[row][col] + cells[row+K][col];
			all_sum[2] = all_sum[2] + cells[row][col] - cells[row+K][col];
			all_sum[1] = all_sum[1] - cells[row][col+K] + cells[row+K][col+K];
			all_sum[3] = all_sum[3] + cells[row][col+K] - cells[row+K][col+K];
		}
	}

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


Measured memory_bytes: 15872
n,m=map(int,input().split())
lis=[1]
a=[]
for i in range(m):
  a.append(int(input()))
  
count=0
for i in range(1,n+1):
  try:
    kiken=a[count]
  except IndexError:
    kiken=-1
  if i-2!=-1:
    maemae=lis[i-2]
  else:
    maemae=0
  try:
    mae=lis[i-1]
  except IndexError:
    mae=0
  if i==kiken:
    lis.append(0)
    count+=1
  else:
    lis.append((mae+maemae)%(10**9+7))
    
print(lis[-1])


Measured memory_bytes: 7836
from collections import deque
k = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])
for i in range(k):
	x = queue[0]
	queue.popleft()
	if x % 10 != 0:
		queue.append(10*x + (x%10) - 1)
	queue.append(10*x + x%10)
	if x % 10 != 9:
		queue.append(10*x + (x % 10) + 1)
print(x)


Measured memory_bytes: 40944
def bb098():
    n = int(input())
    s = input()
    t = list(s)

    u = list(set(t)) # uniq 重複を削除
    if len(u) == 1:
        print(1)
        import sys
        sys.exit()

    mx = 0
    for i in range(1, n-1):
        v = t[0:i]
        w = t[i:]
        vw = list(set(v) & set(w))
        if len(vw) > mx:
            mx = len(vw)

    print(mx)

bb098()


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define all(v) v.begin(), v.end()
#define F first
#define S second


typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int MOD = 1e9+7;
const int INF = 1e9+7;

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

	int n, m; cin >> n >> m;
	vector<string> v(n);
	for(auto& p: v) cin >> p;

	vector<vi> dp(n, vi(m, 0));
	
	FOR(i, n){
		FOR(j, m){
			if(v[i][j] == '.'){
				if(i == 0 && j == 0) dp[i][j] = 1;
				else if(i == 0) dp[i][j] = dp[i][j-1];
				else if(j == 0) dp[i][j] = dp[i-1][j];
				else dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
			}
		}
	}

	cout << dp[n-1][m-1] << '\n';

	return 0;
}

Measured memory_bytes: 5248
N,M = map(int,input().split())
lst = [0 for _ in range(N+1)]
lst2 = [0 for _ in range(N+1)]
count1=0
count2=0
for i in range (M):
    a,b = input().split()
    a = int(a) -1
    if lst[a] == 0:
        if b=="WA":
            lst2[a] =lst2[a] + 1
        elif b=="AC":
            lst[a]=1
            count2=count2+1
for i in range (N+1):
    if lst[i]==1:
        count1=count1+lst2[i]
print(str(count2)+" "+str(count1))

Measured memory_bytes: 4760
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)


int main() {
	ll n, p, ans = 1;

	std::cin >> n >> p;

	auto m = getPrimeFactor(p);

	for (auto itr = m.begin(); itr != m.end(); itr++) {
		while (itr->second / n > 0) {
			ans *= itr->first;
			itr->second -= n;
		}
	}
	outn(ans);

	return 0;

}


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

using namespace std;

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

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

string island[12];
void dfs(int y, int x) {
    island[y][x] = '0';
    rep(k, 4) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        if (!(0 <= ny && ny < 12)) continue;
        if (!(0 <= nx && nx < 12)) continue;
        if (island[ny][nx] == '1') dfs(ny, nx);
    }
}
int main() {
    while (1) {
        rep(i, 12) cin >> island[i];

        int ans = 0;
        rep(i, 12) rep(j, 12) {
            if (island[i][j] == '1') {
                ans++;
                dfs(i, j);
            }
        }
        cout << ans << endl;

        string tmp;
        cin.ignore();
        if (!(getline(cin, tmp))) {
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3244
#include<bits/stdc++.h>
#define MOD 1000000007
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define forf(i,a,b) for(i=a;i<b;i++)
#define forr(i,a,b) for(i=a;i>b;i--)
#define mp make_pair
#define f first
#define s second
#define pb(x) push_back(x)
typedef  long long  int ll;
typedef std::vector<ll> vi;

#define input(vec,a,b) for(ll i =a;i<b;i++) cin>>vec[i]
#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" " ;cout<<endl;
#define all(a) a.begin(),a.end()
using namespace std;


void solve(){
        ll i,j , n,w,out;
        cin>>n>>w;
        ll we[n],v[n];
        for(i=0;i<n;i++)
        {
                 cin>>we[i]>>v[i];
        }
        ll mv[n+1][100001]={0};
        bool p[n+1][100001]={0};
        
        for(i=0;i<=100000;i++)
        {
                 mv[0][i]=0;
                 p[0][i]=0;
        }
        for(i=0;i<=n;i++)
        {
                 mv[i][0]=0;
                 p[i][0]=1;
        }
        
        for(i=1;i<=n;i++)
        {
                 for(j=0;j<v[i-1];j++)
                 {
                          p[i][j]=p[i-1][j];
                          mv[i][j]=mv[i-1][j];
                 }
                 for(j=v[i-1];j<=100000;j++)
                 {
                          if(p[i-1][j-v[i-1]])
                          {
                                   if(p[i-1][j])
                                   mv[i][j]=min(mv[i-1][j],mv[i-1][j-v[i-1]]+we[i-1]);
                                   else
                                   mv[i][j]=mv[i-1][j-v[i-1]]+we[i-1];
                                   p[i][j]=1;
                          }
                          else
                          {
                                   mv[i][j]=mv[i-1][j];
                                   p[i][j]=p[i-1][j];
                          }
                 }
        }
        out=0;
        for(i=100000;i>=0;i--)
        {
              if(p[n][i]&&mv[n][i]<=w)
              {
                       cout<<i;
                       return;
              }
        }
       
}

int main()
{
      IO;
      ll t=1;
      //cin>>t;


      while(t--)
      {

          solve();
      }
    return 0;
}

Measured memory_bytes: 92416
#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(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

/* 基本要素 */
typedef complex<double> Point;
typedef pair<Point, Point> Line;
typedef vector<Point> VP;
const double EPS = 1e-9; // 許容誤差^2
const double INF = 1e9;
#define X real()
#define Y imag()
// #define LE(n,m) ((n) < (m) + EPS)
#define LE(n,m) ((n) - (m) < EPS)
// #define GE(n,m) ((n) + EPS > (m))
#define GE(n,m) (EPS > (m) - (n))
#define EQ(n,m) (abs((n)-(m)) < EPS)

// 内積　dot(a,b) = |a||b|cosθ
double dot(Point a, Point b) {
  return a.X*b.X + a.Y*b.Y;
}

// 外積　cross(a,b) = |a||b|sinθ
double cross(Point a, Point b) {
  return a.X*b.Y - a.Y*b.X;
}

// 点の進行方向
int ccw(Point a, Point b, Point c) {
  b -= a;  c -= a;
  if (cross(b,c) >  EPS) return +1;  // counter clockwise
  if (cross(b,c) < -EPS) return -1;  // clockwise
  if (dot(b,c)   < -EPS) return +2;  // c--a--b on line
  if (norm(b) < norm(c)) return -2;  // a--b--c on line or a==b
  return 0;                          // a--c--b on line or a==c or b==c
}

// 2円の交点
VP crosspointCC(Point a, double ar, Point b, double br) {
  VP ps;
  Point ab = b-a;
  double d = abs(ab);
  double crL = (norm(ab) + ar*ar - br*br) / (2*d);
  if (EQ(d, 0) || ar < abs(crL)) return ps;

  Point abN = ab * Point(0, sqrt(ar*ar - crL*crL) / d);
  Point cp = a + crL/d * ab;
  ps.push_back(cp + abN);
  if (!EQ(norm(abN), 0)) ps.push_back(cp - abN);
  return ps;
}


int main(){
    int n;
    while(scanf(" %d", &n),n){
        vector<Point> p(n);
        vector<int> l(n);
        rep(i,n){
            int x,y;
            scanf(" %d %d %d", &x, &y, &l[i]);
            p[i] = Point(x,y);
        }

        if(n==1){
            printf("%d\n", l[0]);
            continue;
        }

        int min_l = 300;
        rep(i,n) min_l = min(min_l, l[i]);

        auto check = [&](double h){
            vector<double> r(n);
            rep(i,n) r[i] = sqrt(l[i]*l[i] - h*h);

            VP candidate;
            rep(i,n) candidate.pb(p[i]);
            rep(i,n)rep(j,i){
                for(Point c:crosspointCC(p[i],r[i],p[j],r[j])) candidate.pb(c);
            }

            for(Point c:candidate){
                bool ok = true;
                rep(i,n){
                    double d = abs(p[i]-c);
                    ok &= (LE(d,r[i]));
                }
                if(ok) return true;
            }
            return false;
        };

        double L=0, R=min_l;
        rep(loop,50){
            double m = (L+R)/2;
            if(check(m)) L=m;
            else R=m;
        }

        printf("%.10f\n", L);
    }
    return 0;
}



Measured memory_bytes: 3264
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>


int main()
{
	int h = 0, w = 0, n = 0, ans = 0;
	int point[1000][2] = {};
	std::cin >> h >> w >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> point[i][0] >> point[i][1];
	}
	for (int i = 0; i < n - 1; i++) {
		if ((point[i + 1][1] - point[i][1] < 0 && point[i + 1][0] - point[i][0] > 0)|| (point[i + 1][0] - point[i][0] < 0 && point[i + 1][1] - point[i][1] > 0)) {
			ans += std::abs(point[i + 1][0] - point[i][0]) + std::abs(point[i + 1][1] - point[i][1]);
		}
		else {
			
			ans += std::max(std::abs(point[i + 1][0] - point[i][0]), std::abs(point[i + 1][1] - point[i][1]));
		}
	
	}
	std::cout << ans << std::endl;
}


Measured memory_bytes: 3124
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
using namespace std;

bool is_integer( double x ){
  return std::floor(x)==x;
}

int GrossP(int x,int taxrate){
    return floor(static_cast<double>(x * (100+ taxrate)) / static_cast<double>(100));
}

int NetP(double x,double taxrate){
   double lower = x * 100 / (100+taxrate);
   double higher = (x+1) *100 / (100+taxrate);

    if(is_integer(lower)){
        return static_cast<int>(lower);
    }else if(higher > floor(lower) + 1){
        return static_cast<int>(lower) + 1;
    }else{
        return 0;
    }


}
int main(){
    vector<int> ans;
    while(true){
        int max = 0;
        int x,y,s; cin >> x >> y >> s;
        if(x == 0 && y == 0 && s == 0){
            break;
        }

        for(int s1 = 1; s1 < s; s1++){
            int s2 = s - s1;

            int net1 = NetP(s1,x);
            int net2 = NetP(s2,x);

            int GrossTotal = GrossP(net1,y) + GrossP(net2,y);

            GrossTotal > max ? max = GrossTotal:1;
        }

        ans.push_back(max);
    }

    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0);
    int n,m,x,arr[20][20],price[20],yes=0,mon=0,lessmon=10000000,time=0;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++){
        cin>>price[i];
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<(1<<n);i++){
        mon=0;
        int skill[20]={0};
        int t=i;
        bool use[12];
        for(int j=0;j<n;j++,t=t/2){
            use[j]=t%2;
            if(use[j]){
                for(int k=0;k<m;k++){
                    skill[k]+=arr[j][k];
                }
                mon+=price[j];

            }
        }
        yes=0;
        for(int l=0;l<m;l++){
            if(skill[l]>=x){
                yes++;
            }
        }
        if(yes==m){
            time++;
            if(mon<lessmon){
                lessmon=mon;
            }
        }
    }
    if(time==0){
        cout<<"-1\n";
    }else{
        cout<<lessmon<<"\n";
    }

return 0;
}


Measured memory_bytes: 3600
import heapq
n, m = map(int, input().split())
dat = list(map(lambda x: -int(x), input().split()))
heapq.heapify(dat)
#print(dat)
for i in range(m):
    #print(dat)
    c = heapq.heappop(dat)
    c = -(-c//2)
    heapq.heappush(dat, c)
#print(dat)
print(-sum(dat))

Measured memory_bytes: 72216
H,W = map(int,input().split())
S = [input() for _ in range(H)]
A = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            bol = 0
            for dx,dy in A:
                if 0<=j+dx<=W-1 and 0<=i+dy<=H-1:
                    if S[i+dy][j+dx] == "#":
                        bol = 1
            if bol == 0:
                print("No")
                exit()
print("Yes")

Measured memory_bytes: 9012
#include "bits/stdc++.h"

using namespace std;

int main()
{

	int N;
	cin >> N;

	vector<long long> B(N-1);
	vector<long long> A(N);
	for (int i = 0; i < N-1; i++) {
		cin >> B[i];
	}

	A[0] = B[0];
	A[1] = B[0];
	for (int i = 1; i < N-1; i++) {
		A[i] = std::min(A[i], B[i]);
		A[i + 1] = B[i];
	}

	long long  v = 0;
	for (int i = 0; i < N; i++) {
		v += A[i];
		//cerr << A[i] << ",";
	}
	cout << v;


	return 0;
}

int mainq()
{

	int N;
	cin >> N;

	vector<long long> B(N);
	vector<long long> A(N);
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	A[N-1] = B[N-2];
	for (int i = N-2; i >= 1; i--) {
		A[i] = std::min(B[i - 1], B[i]);
	}
	A[0] = std::min(A[1], B[0]);
	long long  v = 0;
	for (int i = 0; i < N; i++) {
		v += A[i];
		//cerr << A[i] << ",";
	}


	cout << v;


	return 0;
}


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

int main()
{
	int num1,num2,num3,num4,num5,num6,num7;

	cin>>num1>>num2>>num3>>num4;
	num5=num1+num2+num3+num4;
	num6=num5/60;
	num7=num5%60;
	cout<<num6<<"\n";
	cout<<num7<<"\n";
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[200001],b[200001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int m=0;
	for(int i=n;i>1 && m<2;i--)
		if(a[i]==a[i-1])
			b[++m]=a[i],--i;
	if(m<2)
		puts("0");
	else
		printf("%lld\n",(ll)b[1]*b[2]);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define for1(i, m, n) for(int i = m;i < n;i++)
#define ll long long
#define endl '\n'
using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n, h, w;
    cin >> n >> h >> w;
    cout << (n - h + 1) * (n - w + 1);
	return 0;
}

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

#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;

TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM T> inline istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
TPL<TNM V, TNM H> void resize(vector<V>& _v, const H _h) { _v.resize(_h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& _v, const H& _h, const T& ... _t) { _v.resize(_h); for (auto& __v : _v) resize(__v, _t ...); }
TPL<TNM V, TNM T> TNM enable_if<!is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { std::fill(ALL(_v), _t); }
TPL<TNM V, TNM T> TNM enable_if<is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { for (auto& _e : _v) fill(_e, _t); }
TPL<TNM T> inline void UNIQUE(vector<T>& _v) { sort(ALL(_v)); _v.erase(unique(ALL(_v)), _v.end()); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } pre__;

//0-indexed 
template<class T = int>
struct CumulativeSum1D
{
	bool builded;
	vector<T> data;
	CumulativeSum1D(int N) { builded = false; data.resize(N + 1, 0); }
	inline void add(int i, T x)
	{
		data[i + 1] = x;
		builded = false;
	}

	void build()
	{
		int n = data.size();
		for (int i = 1; i < n; i++) {
			data[i] += data[i - 1];
		}
		builded = true;
	}
	//0-indexed [l, r]
	inline T query(int l, int r) { assert(builded); return data[r + 1] - data[l]; }
};

int main(void) {
	int N;
	cin >> N;
	string S;
	cin >> S;
	CumulativeSum1D<int> J(N), I(N);
	for (int i = 0; i < N; ++i) {
		if (S[i] == 'J')J.add(i, 1);
		if (S[i] == 'I')I.add(i, 1);
	}
	J.build();
	I.build();
	ll mx = 0;
	ll id = -1;
	for (int i = 1; i < N - 1; ++i) {
		ll p = 1;
		ll l = J.query(0, i - 1);
		ll r = I.query(i, N - 1);
		p = l * r;
		if (mx < p) {
			mx = p;
			id = i;
		}
	}
	ll Jmax = 0, Imax = 0, Omax = mx;
	for (int i = 0; i < N; ++i) {
		ll l = J.query(0, i - 1);
		ll r = I.query(i + 1, N - 1);
		if (S[i] == 'O') {
			Jmax += ((l + 1) * r);
			Imax += (l) * (r + 1);
			Omax += l * r;
		}
	}

	cout << max({ Jmax, Imax, Omax }) << endl;
	return 0;
}


Measured memory_bytes: 4104
def main():
  n,m=map(int,input().split())
  rec={}
  for _ in range(m):
    s,c=map(int,input().split())
    if s==1 and c==0 and n>1:
      print(-1)
      return
    if s in rec and rec[s]!=c:
      print(-1)
      return
    rec[s]=c
  for i in range(n):
    if i+1 in rec:
      print(rec[i+1],end='')
    elif i==0 and n>1:
      print(1,end='')
    else:
      print(0,end='')
main()

Measured memory_bytes: 38384
import math


class Vector2():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, v):
        return Vector2(self.x+v.x, self.y+v.y)

    def __sub__(self, v):
        return Vector2(self.x-v.x, self.y-v.y)

    def __mul__(self, v):
        return Vector2(self.x*v, self.y*v)

    def __truediv__(self, v):
        return Vector2(self.x/v, self.y/v)

    def __abs__(self):
        return math.sqrt(float(self.x*self.x+self.y*self.y))

    def dot(self, v):
        return self.x*v.x+self.y*v.y

    def cross(self, v):
        return self.x*v.y-self.y*v.x

    def norm(self):
        d = abs(self)
        return Vector2(self.x/d, self.y/d)


x1, y1, x2, y2 = map(int, input().split())
v12 = Vector2(x2-x1, y2-y1).norm()
q = int(input())
for i in range(q):
    x, y = map(int, input().split())
    v = Vector2(x-x1, y-y1)
    d = v12.dot(v)
    ans = Vector2(x1+v12.x*d, y1+v12.y*d)
    print(f"{ans.x} {ans.y}")



Measured memory_bytes: 5712
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define vv(T) vector<vector<T>>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vbool = vector<bool>;
using vvbool = vector<vector<bool>>;
using qint = queue<int>;
using sint = stack<int>;
using pii = pair<int, int>;

// int main(){
//     ll a;
//     double b;
//     cin >> a >> b;

//     long long bt = b * 100;
//     long long b1 = bt % 10;
//     bt /= 10;
//     long long b10 = bt % 10;
//     bt /= 10;
//     long long b100 = bt % 10;

//     long long ans100 = a * b100 * 100;
//     long long ans10 = a * b10 * 10;
//     long long ans1 = a * b1;
    
//     long long ans = ans100;
//     ans += ans10;
//     ans += ans1;

//     ans /= 100;

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

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

int main(){
    ll a;
    string b;
    cin >> a >> b;
    string tb;
    tb.push_back(b[0]);
    tb.push_back(b[2]);
    tb.push_back(b[3]);
    int ib = stoi(tb);
    ll ans = a * ib;
    ans /= 100;

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


Measured memory_bytes: 3628
n,a,b = map(int, input().split())

mod = 10**9+7

total = pow(2,n,mod)
total += mod*3

def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

f,g = factorials(2*10**5+1,mod)

nCa = g[a]
for i in range(1,a+1):
    nCa *= n-i+1
    nCa %= mod

nCb = g[b]
for i in range(1,b+1):
    nCb *= n-i+1
    nCb %= mod

print((total - 1 - nCa - nCb) % mod)

Measured memory_bytes: 54692
n, k = (int(x) for x in input().split())
score = [int(x) for x in input().split()]
translate = {'r':0, 's': 1, 'p': 2}
seq = [translate[x] for x in input()]
dp = [[float('-inf') for _ in range(3)] for _ in range(n+1)]
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0
for i in range(n):
    for j in range(3):
        if i < k:
            dp[i+1][j] =(score[j] if ((j+1) % 3) == seq[i] else 0)
        else:
            dp[i+1][j] = max(dp[i-k+1][(j+1) % 3], dp[i-k+1][(j+2) % 3]) + (score[j] if ((j+1) % 3) == seq[i] else 0) 
print(sum(max(dp[-1-i]) for i in range(k)))


Measured memory_bytes: 71088
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

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

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN2(n,m);
  Vi A(n);
  Vi B(n);
  vector<pair<int,int>> SHOP(n);
  REP(i,n){
    IN2(SHOP[i].first,SHOP[i].second);
  }
  SORT(SHOP);
  REP(i,n){
    while(SHOP[i].second > 0){
      z += SHOP[i].first;
      x++;
      SHOP[i].second--;
      if(x==m) break;
    }
    if(x==m) break;
  }
  OUT(z);
}


Measured memory_bytes: 3456
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

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

    vector<pair<int, int>> red, blue;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        red.emplace_back(a, b);
    }
    sort(red.begin(), red.end());
    for (int i = 0; i < n; i++)
    {
        int c, d;
        cin >> c >> d;
        blue.emplace_back(c, d);
    }
    sort(blue.begin(), blue.end());
    vector<int> checked(n);
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        int index1 = -1;
        for (int j = 0; j < n; j++)
        {
            if (red[j].first > blue[i].first)
            {
                index1 = j;
                break;
            }
        }
        if (index1 < 0)
        {
            index1 = n;
        }

        int maxy = -1;
        int index = -1;

        for (int j = 0; j < index1; j++)
        {
            if (checked[j] > 0)
            {
                continue;
            }
            if (blue[i].second < red[j].second)
            {
                continue;
            }
            maxy = max(maxy, red[j].second);
            if (red[j].second == maxy)
            {
                index = j;
            }
        }
        if (index != -1)
        {
            ans++;
            checked[index]++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define ll long long
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define per(i, a, b) for (ll i = a; i > b; i--)
#define vi vector<int>
#define vii vector<vi>
#define vl vector<ll>
#define vll vector<vl>
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define a(v) (v.begin(), v.end())
#define intlimit 2e9 + 69
#define longlimit 8e18 + 69
#define MOD 1000000007
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a) * (b) / gcd(a, b))
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string x,y;
    cin >> x >> y;
    int mini = x.size();
    rep(i,0,x.size()){
        int sum = 0;
        if(i+y.size() <= x.size())
        rep(j,i,i+y.size()){
            if(y[j-i]==x[j]){
                sum++;
            }
        }
        mini = min(mini,(int)y.size() - sum);
    }
    cout << mini;
}


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

int main(){
    int N;
    long A[100002] = {};
    long B[100002] = {};

    cin >> N;
    for(int i=1;i<=N-1;i++) cin >> B[i];
    A[1] = B[1];
    A[N] = B[N-1];

    for(int i=2;i<=N-1;i++){
        A[i] = min(B[i], B[i-1]);
    }

    long long ans = 0;
    for(int i=1;i<=N;i++){
        ans += A[i];
    }

    cout << ans << endl;


    return 0;
}

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

int main(){
    char a;
    cin >> a;
    if(a-'a'>=0&&a-'a'<=26)cout << "a" << endl;
    if(a-'A'>=0&&a-'A'<=26)cout << "A "<< endl;
    return 0;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
using namespace std;
int main(void)
{
	char s[11],t[12];
	int len1,len2;
	scanf("%s %s",s,t);
	len1=strlen(s);
	len2=strlen(t);
	t[len2-1]='\0';
	if(len1+1==len2 && strcmp(s,t)==0)	printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 1620
H,W,N=map(int,input().split())
sita,hidari=0,0
ue,migi=W,H
for i in range(N):
  x,y,a=map(int,input().split())
  if a==1:
    hidari=max(x,hidari)
  elif a==2:
    migi=min(migi,x)
  elif a==3:
    sita=max(sita,y)
  else:
    ue=min(ue,y)
print(max(0,(migi-hidari))*max(0,(ue-sita)))

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = ~(1<<31);
const int MOD = 1e9+7;
const double EPS = 1.0e-10;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main()
{
	int r;
	cin >> r;
	cout << r*r << endl;

	return 0;
}


Measured memory_bytes: 256
n = int(input())
a,b =list(map(int,input().split())),list(map(int,input().split()))
dp = [0] * n
dp[0] = sum(b)
for i in range(1,n):
    dp[i] = dp[i-1]-b[i-1]
ans = 0
for i in range(n):
    ans = max(ans,sum(a[:i+1])+dp[i])
print(ans)

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

int main()
{
    double n,a,m,s;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>a;
        m+=(1/a);
    }
    cout<<(1/m)<<endl;
    //main();
    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())

table = [[] for _ in range(H)]

for y in range(H):
    table[y] = input().split()

for y in range(H):
    for x in range(W):
        if table[y][x] == "snuke":
            print(chr(ord("A") + x) + str(y+1))

Measured memory_bytes: 9132