akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

#define NIL -1
#define N 500001

int A[N], n;

void maxHeap(int i){
	int ma = A[i];
	int l = 2 * i;     if (l <= n) ma = std::max(ma, A[l]);
	int r = 2 * i + 1; if (r <= n) ma = std::max(ma, A[r]);

	if (ma != A[i]){
		int idx = (ma == A[l]) ? l : r;
		swap(A[i], A[idx]);
		maxHeap(idx);
	}
}

int main(){
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> A[i];

	for (int i = n / 2; i >= 1; --i) maxHeap(i);

	for (int i = 1; i <= n; ++i) cout << " " << A[i];
	cout << endl;

	return 0;
}

//node 1: key = 7, left key = 8, right key = 1,
//node 2 : key = 8, parent key = 7, left key = 2, right key = 3,
//node 3 : key = 1, parent key = 7,
//node 4 : key = 2, parent key = 8,
//node 5 : key = 3, parent key = 8,

Measured memory_bytes: 5040
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<vector<int>> dp(s.size() + 1, vector<int>(13, 0));
    dp[0][0] = 1;

    for (long long i = 0, d = 1; i < static_cast<int>(s.size()); i++, d = d * 10 % 13) {
        for (int j = 0; j < 13; j++) {
            for (int k = 0; k < 10; k++) {
                if (s[s.size() - i - 1] == '?' || s[s.size() - i - 1] - '0' == k) {
                    dp[i + 1][(k * d + j) % 13] = (dp[i + 1][(k * d + j) % 13] + dp[i][j]) % 1000000007;
                }
            }
        }
    }

    cout << dp[s.size()][5] << endl;
}


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

using namespace std;

int main(){
    string in_s,in_t;
    cin>>in_s>>in_t;
    int c=0;
    for(int i=0;i<(int)in_s.size();i++){
        if(in_s[i]==in_t[i])c++;
    }
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 256
import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {
  val Array(w, h) = readLine.trim.split(' ').map(_.toInt)
  val arg = Array.tabulate(h){ _ ⇒ readLine.trim}
  val start = (0 until h).flatMap(y ⇒ (0 until w).find(x ⇒ arg(y)(x) == 's').map(x ⇒ Coordinate(x, y))).head
  val goal = (0 until h).flatMap(y ⇒ (0 until w).find(x ⇒ arg(y)(x) == 'g').map(x ⇒ Coordinate(x, y))).head
  val state = arg.map{line ⇒ line.map{
    case '#' ⇒ Wall
    case '.' | 's' ⇒ Empty
    case 'g' ⇒ Stair
    case '*' ⇒ Spring
    case _ ⇒ ???
  }.toArray}
  val minFromGoal = Array.fill(h){Array.fill(w){Double.MaxValue / 3}}
  minFromGoal(goal.y)(goal.x) = 0
  val queue = mutable.Queue[Coordinate](goal)
  while (queue.nonEmpty) {
    val current = queue.dequeue()
    for (next ← current.neighbor if (0 until h).contains(next.y) && (0 until w).contains(next.x) && state(next.y)(next.x) == Empty) {
      if (minFromGoal(next.y)(next.x) > minFromGoal(current.y)(current.x) + 1) {
        minFromGoal(next.y)(next.x) = minFromGoal(current.y)(current.x) + 1
        queue.enqueue(next)
      }
    }
  }
  val minToSpring = Array.fill(h){Array.fill(w){Double.MaxValue / 3}}
  for (spring ← (0 until h).flatMap(y ⇒ (0 until w).collect{case x if state(y)(x) == Spring ⇒ Coordinate(x, y)})){
    minToSpring(spring.y)(spring.x) = 0
    queue.enqueue(spring)
  }
  while(queue.nonEmpty) {
    val current = queue.dequeue()
    for (next ← current.neighbor if (0 until h).contains(next.y) && (0 until w).contains(next.x) && state(next.y)(next.x) == Empty) {
      if (minToSpring(next.y)(next.x) > minToSpring(current.y)(current.x) + 1) {
        minToSpring(next.y)(next.x) = minToSpring(current.y)(current.x) + 1
        queue.enqueue(next)
      }
    }
  }
  val empties = (0 until h).flatMap(y ⇒ (0 until w).collect{case x if state(y)(x) == Empty ⇒ Coordinate(x, y)})
  var min = 0d
  var max = Double.MaxValue / 2
  while (min * 1.000000000000001d < max) {
    val mid = (min + max) / 2
    if (canReach(mid)) max = mid
    else min = mid
  }
  println(f"${math.min(minToSpring(start.y)(start.x) + max, minFromGoal(start.y)(start.x))}%.12f")
  def canReach(estimated: Double): Boolean = empties.map{case Coordinate(x, y) ⇒ math.min(minToSpring(y)(x) + estimated, minFromGoal(y)(x))}.sum <= estimated * empties.length
  sealed trait State
  case object Spring extends State
  case object Wall extends State
  case object Empty extends State
  case object Stair extends State
  case class Coordinate(x: Int, y: Int) {
    def neighbor: List[Coordinate] = List(Coordinate(x + 1, y), Coordinate(x - 1, y), Coordinate(x, y + 1), Coordinate(x, y - 1))
  }
}









Measured memory_bytes: 585284
N,H = (int(i) for i in input().split())
a = []
b = [0]
for i in range(N):
    A,B = (int(i) for i in input().split())
    a.append(A)
    b.append(B)
    

count = 0
biga = max(a)
bigb = max(b)
b.sort(reverse = True)

while H > 0:
    if bigb > biga:
        count += 1
        H -= bigb
        b.remove(bigb)
        bigb = b[0]        
    else:
        count += H//biga
        H -= (H//biga)*(biga)
        if H != 0:
            count += 1
        break
        

print(count)

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<P, ll> Pl;
const ll mod = (ll)1e9 + 7;
const int N = 3005;

int n,q;
int num[N];
int a[N], b[N];

ll dp[N][N];

ll fac[N], facinv[N];
ll inv[N];

ll fp(ll x, ll k){
    if(k == 0) return 1;
    ll hf = fp(x, k/2);
    return k % 2 ? hf * hf % mod * x % mod: hf * hf % mod;
}

int main(){
    inv[1] = 1;
    for(int i = 2; i < N; i++) inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod;
    fac[0] = 1;
    for(int i = 1; i <= N-1; i++) fac[i] = fac[i-1] * i % mod;
    facinv[N-1] = fp(fac[N-1], mod - 2);
    for(int i = N-1 - 1; i >= 0; i--) facinv[i] = facinv[i+1] * (i+1) % mod;

    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> num[i];
    for(int i = 0; i < q; i++) cin >> a[i] >> b[i], a[i]--, b[i]--;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            dp[i][j] = (num[i] > num[j]);
        }
    }
    for(int i = 0; i < q; i++){
        for(int k = 0; k < n; k++){
            if(k != a[i] && k != b[i]) {
                ll sum1 = inv[2] * (dp[k][a[i]] + dp[k][b[i]]) % mod;
                ll sum2 = inv[2] * (dp[a[i]][k] + dp[b[i]][k]) % mod;
                dp[k][a[i]] = dp[k][b[i]] = sum1;
                dp[a[i]][k] = dp[b[i]][k] = sum2;
            }
        }
        ll sum = inv[2] * (dp[b[i]][a[i]] + dp[a[i]][b[i]]) % mod;
        dp[a[i]][b[i]] = dp[b[i]][a[i]] = sum;
    }
    ll res = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            res += dp[i][j];
            res %= mod;
        }
    }
    for(int i = 0; i < q; i++) res = (res * 2) % mod;
    cout << res << endl;
}

Measured memory_bytes: 70784
class UnionFind:
    def __init__(self, size):
        self.parents = [-1] * size

    def find(self, x):
        while self.parents[x] > 0:
            x = self.parents[x]
        return x

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi == pj:
            return
        if self.parents[pi] < self.parents[pj]:
            pi, pj = pj, pi
            i, j = j, i
        self.parents[pi] += self.parents[pj]
        self.parents[pj] = pi
        self.reconnect(j, pi)

    def reconnect(self, i, j):
        while self.parents[i] > 0:
            t = self.parents[i]
            self.parents[i] = j
            i = t


def main():
    n, m, *ab, = map(int, open(0).read().split())
    uf = UnionFind(n + 1)

    for i, j in zip(ab[::2], ab[1::2]):
        uf.union(i, j)

    print(-min(uf.parents))


if __name__ == '__main__':
    main()


Measured memory_bytes: 125548
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair <double,double> P;

int main() {
  int N,W;
  cin>>N>>W;
  vector<ll> vec[4];
  ll w0;
  rep(i,N) {
    ll w,v;
    cin>>w>>v;
    if (i==0) w0=w;
    vec[w-w0].push_back(v);
  }
  rep(i,4) {
    sort(vec[i].begin(),vec[i].end());
    reverse(vec[i].begin(),vec[i].end());
  }
  vector<ll> sum[4];
  rep(i,4) {
    ll add=0;
    sum[i].push_back(0);
    rep(j,vec[i].size()) {
      add+=vec[i][j];
      sum[i].push_back(add);
    }
  }
  ll ans=0;
  rep(i,sum[0].size()) {
    rep(j,sum[1].size()) {
      rep(k,sum[2].size()) {
	rep(l,sum[3].size()) {
	  if (w0*i+(w0+1)*j+(w0+2)*k+(w0+3)*l>W) break;
	  ans=max(ans,sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l]);
	}
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
const ll mod=1e9+7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=2000001;
    int k,x;
    cin>>k>>x;
    for(int i=-1000000;i<=1000000;i++){
        if(abs(x-i)<k){cout<<i<<" ";}
    }
    return 0;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

const ll MAX = 2000010;
ll fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll g(ll r, ll c){
    ll res = 0;
    for(int i = 1; i <= r+1; i++){
        res += COM(i+c, c);
        res %= MOD;
    }
    return res;
}

int main(){
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    r1--, c1--;
    COMinit();

    cout << (g(r2, c2) - g(r1, c2) - g(r2, c1) + g(r1, c1) + MOD) % MOD<< endl;

    return 0;
}


Measured memory_bytes: 47104
# 整数の入力
N = int(input())

# スペース区切りの整数の入力
if N%2 == 0:
    M = int(0.5*N**2-N)
    print(M)
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if i+j != N+1:
                print("{} {}".format(i, j))
else:
    N = N-1
    M = int(0.5*N**2-N)
    print(M+N)
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if i+j != N+1:
                print("{} {}".format(i, j))
        print("{} {}".format(i, N+1))

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

int res[100005];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int a;cin>>a;
    res[a - 1] = i + 1;
  }
  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<res[i];
  }
  cout<<endl;

  return 0;
}


Measured memory_bytes: 1280
program ARC086C
    implicit none
    integer(8)::N,K,valiation,i
    integer(8)::remove=0
    integer(8)::result=0
    integer(8),allocatable,dimension(:)::A,L
    read(5,*)N,K
    allocate(A(N))
    allocate(L(N))
    valiation=N
    L=0
    read(5,*)(A(i),i=1,N)

    do i=1,N
        L(A(i))=L(A(i))+1
    end do

    L=iqsort(L)

    do i=1,N
        if(L(i)==0)then
            valiation=valiation-1
        else
            exit
        end if
    end do

    remove=valiation-K

    if(remove>0)then
        do i=1,N
            if(L(i)/=0)then
                result=result+L(i)
                remove=remove-1
            end if

            if(remove==0)then
                exit
            end if
        end do
    end if

    print'(i0)',result

contains
    recursive function iqsort(ix) result(ires)
      integer(8), allocatable :: ires(:)
      integer(8), intent(in)  :: ix(:)
      integer :: k
      if (size(ix) <= 1) then 
        ires = ix
      else  
        k = ix(size(ix) / 2)
        ires = [iqsort(pack(ix, ix < k)), pack(ix, ix == k), iqsort(pack(ix, ix > k))] 
      end if
    end function iqsort
end program ARC086C

Measured memory_bytes: 8748
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

public class Program
{

    public void Proc()
    {
        long[] inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
        string ans = "Alice";
        if(Math.Abs(inpt[0]-inpt[1])<=1) {
            ans = "Brown";
        }
        Console.WriteLine(ans);
        
    }


    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"


5 0

";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}


Measured memory_bytes: 13396
a,b,c,x,y = map(int,input().split())
money1=a*x+b*y
money2=a*(x-min(x,y))+b*(y-min(x,y))+c*2*min(x,y)
money3=max(x,y)*c*2
print(min(money1,money2,money3))

Measured memory_bytes: 3188
#include "bits/stdc++.h"
#include <cmath>

#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;

struct __INIT {
    __INIT() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __init;

int main() {
    ll N;
    cin >> N;
    cout << N * (N - 1) / 2 << endl;
}

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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define INF       numeric_limits<int>::max()
#define NINF      numeric_limits<int>::min()
#define MOD       1000000007

using namespace std;
using Int = long long;

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

    string w;
    std::cin >> w;

    vector<int> table(26, 0);
    REP(i, w.size()) {
        table[w[i] - 'a']++;
    }

    bool is_beautiful = true;
    for(const auto& v : table) {
        if(v % 2 == 1) {
            is_beautiful = false;
            break;
        }
    }

    if(is_beautiful) {
        std::cout << "Yes" << std::endl;
    }
    else {
        std::cout << "No" << std::endl;
    }

    return 0;
}


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

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

#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)

class DCandyDistribution {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int n, m; in >> n >> m;
	    map<int, int> freq;
	    int prefix = 0, res = 0;
        freq[0] = 1;
        f(i, n){
            int x; in >> x; prefix += x;
            res += freq[prefix%m];
            freq[prefix%m]++;
        }
        out << res;
	}
};


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	DCandyDistribution solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 4224
#!/usr/bin/env python3
import itertools

(n, m, q), *r = [[*map(int, t.split())] for t in open(0)]
ans = 0
for i in list(itertools.combinations_with_replacement(range(1, m + 1), n)):
    sub = 0
    for a, b, c, d in r:
        sub += d * (i[b - 1] - i[a - 1] == c)
    ans = max(ans, sub)
print(ans)


Measured memory_bytes: 87364
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}



template< typename T >
struct BIT {
    vector< T > data;

    BIT (){
        int sz=500000;
        data.assign(++sz, 0);
    }

    T sum(int k) {
        T ret = 0;
        for(++k; k > 0; k -= k & -k) ret+=data[k];
        return (ret);
    }

    T get(int x,int y){

        return sum(y)-sum(x);
    }

    void add(int k, T x) {
        for(++k; k < data.size(); k += k & -k) data[k]+=x;
    }
};

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

    int n;
    cin>>n;
    string s;
    cin>>s;
    BIT<int> bit[30];
    rep(i,n){
        bit[s[i]-'a'].add(i,1);
    }

    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int i;
            char c;
            cin>>i>>c;
            i--;
            bit[s[i]-'a'].add(i,-1);
            bit[c-'a'].add(i,1);
            s[i]=c;
        }else{
            int l,r;
            cin>>l>>r;
            l--;r--;
            int ans=0;
            rep(i,30){
                //cout<<bit[i].sum(r)<<' '<<bit[i].sum(l)<<endl;
                ans+=(bit[i].get(l-1,r)>0);
            }
            cout<<ans<<endl;
        }
    }


}

Measured memory_bytes: 118172
#include <iostream>
using namespace std;
int main(void){
    int n,a[110000],b=0;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a[i];
    }
    
    for(int i=0;i<n;i++){
        if(i==0){
            b+=a[i];
        }
        else if(i==n-1){
            b+=a[i-1];
        }
            else{
                if(a[i-1]>=a[i]){
                    b+=a[i];
                }
                    else{
                        b+=a[i-1];
                    }
                }
            }   
    
    cout<<b<<endl;
}


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

using namespace std;

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

	string S;
	cin >> S;

	int white = 0, black = 0;

	for (int i = 0; i < N; i++) {
		if (S[i] == '.') {
			white++;
		}
	}

	int ans = white;
	for (int i = 0; i < N; i++) {
		if (S[i] == '.') {
			white--;
		}
		if (S[i] == '#') {
			black++;
		}
		ans = min(ans, white + black);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
int n,k,cnt,ans,p[4]={1,9,81,729};
char c[MAXN];
int cx (int x,int k) {
	if (k==0) {return 1;}
	if (k==1) {return x;}
	if (k==2) {return (x*(x-1))/2;}
	if (k==3) {return (x*(x-1)*(x-2))/6;}
	return 0;
}
int main () {
	scanf("%s%d",c+1,&k);
	int n=strlen(c+1);
	for (int i=1;i<=n;i++) {
		if (c[i]!='0') {
			cnt++;
			ans+=cx(n-i,k-cnt+1)*p[k-cnt+1];
			ans+=(c[i]-'0'-1)*cx(n-i,k-cnt)*p[k-cnt];
		}
	}
	printf("%d\n",ans+(cnt==k));
	return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Char
import Data.Int
import Data.Foldable
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Debug.Trace

solve :: Int -> VU.Vector Int -> Bool
solve !n !hn = go $ VU.toList hn
 where
  go (x:y:xs) | x == y    = go $ y : xs
              | x < y     = go $ (y - 1) : xs
              | otherwise = False
  go _ = True

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  n  <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  hn <- VU.unfoldrN n readInt <$> B.getLine
  putStrLn $ if solve n hn then "Yes" else "No"


Measured memory_bytes: 3964
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=500005;
int n,a[N];ll ans=0;char s[N];
inline ll c(int x){return 1ll*x*(x-1)/2;}
int main()
{
	scanf("%s",s+1);n=strlen(s+1)+1;a[1]=0;
	int p1=0,p2=0;
	for(int i=1;i<=n;i++)
	{
		int f1=i==1||s[i-1]=='>',f2=i==n||s[i]=='<';
		if(f1&&f2)
		{
			if(p1)
			{
				int l1=p2-p1,l2=i-p2;
				if(l1<l2)ans+=c(l1)+c(l2+1);else ans+=c(l1+1)+c(l2);
			}
			else ans+=c(i);
			p1=i;
		}
		f1=i==1||s[i-1]=='<',f2=i==n||s[i]=='>';
		if(f1&&f2)p2=i;
	}
	if(p2==n)ans+=c(p2-p1+1);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 768
def inpl(): return [int(i) for i in input().split()]

N,W = inpl()
H = {0: 0}
for i in range(N):
    w, v = inpl()
    for iw, iv in H.copy().items():
        if iw+w <=W:
            H[iw + w] = max(H.get(iw + w, 0),iv+v)
print(max(H.values()))

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N;
        public int[] C, S, F;
        public void Run()
        {
            N = Input.ReadInt() - 1;
            C = new int[N];
            S = new int[N];
            F = new int[N];
            for (int i = 0; i < N; i++)
            {
                var line = Input.ReadIntArray();
                C[i] = line[0];
                S[i] = line[1];
                F[i] = line[2];
            }

            for (int i = 0; i < N; i++)
            {
               Console.WriteLine(Calc(i));   
            }
            Console.WriteLine(0);

        }

        public long Calc(int x)
        {
            long ret = 0;
            for (int i = x; i < N; i++)
            {
                long tt = ret - S[i];
                long st;
                if (tt <= 0)
                {
                    st = S[i];
                }
                else
                {
                    st = S[i] + (tt / F[i]) * F[i] + (tt % F[i] == 0 ? 0 : F[i]);
                }

                ret = st + C[i];
            }

            return ret;
        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 13268
#include<unordered_map>
#include<unordered_set>
#include<iostream>
#include<vector>

using ll = long long;

std::unordered_map<int, std::vector<int>> adjecent;
std::unordered_map<int, ll> node2score;
std::vector<int> sol;
std::unordered_set<int> graph;

void solve(int prev, int n, ll pass) {

    sol[n] = node2score[n] + pass;
    // std::cout << n << ":" << sol[n] << std::endl;

    if (adjecent.count(n) != 0) {
     // has child
        for(int i : adjecent[n]) {
            if (prev != i) {
                solve(n, i, sol[n]);
            }
        }
    }
}

int main(void) {

    int N, Q;
    std::cin >> N >> Q;

    // std::vector<int> a, b;
    sol = std::vector<int>(N+1, 0);

    int a,b;
    graph.insert(1);
    for (int i = 0; i < N-1; ++i) {
        std::cin >> a >> b;
        adjecent[a].push_back(b);
        adjecent[b].push_back(a);

        // if(graph.count(a) != 0 && graph.count(b)) {
        //     adjecent[a].push_back(b);
        //     graph.insert({a,b});
        // } else {
        //     adjecent[b].push_back(a);
        //     graph.insert({a,b});
        // }

        // std::cout << "---graph---" << std::endl;
        // for(auto a : graph) {
        //     std::cout << a << std::endl;
        // }
        // std::cout << "---graph---" << std::endl;

        /*
        if(a<b) {
            adjecent[a].push_back(b);
        } else {
            adjecent[b].push_back(a);
        }
        */
    }

    int p,x;
    for(int i = 0; i < Q; ++i){
        std::cin >> p >> x;
        node2score[p] += x;
    }

    solve(-1, 1, 0);

    for(int i = 1; i < sol.size(); ++i) {
        std::cout << sol[i] << " ";
    }

    std::cout << std::endl;
    return 0;
}

Measured memory_bytes: 38472
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int A=sc.nextInt();
        int B=sc.nextInt();
        int C=sc.nextInt();
        int X=sc.nextInt();
        int res=0;
        for (int a=0;a<=A;a++){
            for(int b=0;b<=B;b++){
                int c=(X-500*a-100*b)/50;
                if (c>=0 && c<=C)
                res++;
            }
        }
        
        System.out.println(res);
    }
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
int dist[55][55];
int main(){
    int height,width;
    cin >> height >> width;
    vector<string> maze(height);
    for(int i=0;i<height;++i) cin >> maze[i];
    int ct=0;
    for(int h=0;h<height;++h){
        for(int w=0;w<width;++w){
            if(maze[h][w]=='.') ct++;
        }
    }
    for(int h=0;h<height;++h){
        for(int w=0;w<width;++w){
            dist[h][w]=-1;
        }
    }
    queue< pair<int,int> > que;
    dist[0][0]=0;
    que.push(make_pair(0,0));
    while(!que.empty()){
        pair<int,int> p=que.front();
        que.pop();
        int h=p.first;
        int w=p.second;
        for(int dir=0;dir<4;++dir){
            int ny=h+dy[dir];
            int nx=w+dx[dir];
            if(ny<0 || ny>=height || nx<0 || nx>=width) continue;
            if(maze[ny][nx]=='#') continue;
            if(dist[ny][nx]==-1){
                dist[ny][nx] = dist[h][w]+1;
                que.push(make_pair(ny,nx));
            }
        }
    }
    int ans = ct - (dist[height-1][width-1]+1);
    if(dist[height-1][width-1]==-1) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int N, M; cin >> N >> M;
    
    // N < M
    if(N > M) swap(N, M);
    if(N >= 3) {
        cout << (N-2) * (M-2) << endl;
    }
    else if(N == 2) {
        cout << 0 << endl;
    }
    else {
        if(M == 1) cout << 1 << endl;
        else cout << M - 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = str(input())
Ans = []
for i in range(len(S)):
  if ord(S[i]) + N <= 90:
    Ans.append(chr(ord(S[i]) + N))
  else:
    Ans.append(chr(ord(S[i]) + N - 90 + 64))
print(''.join(Ans))

Measured memory_bytes: 3060
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);

    int a, b;
    int c, d;
    cin >> a >> b >> c >> d;


    int l = max(a, c);
    int r = min(b - 1,  d - 1);

    int res = max(0, r - l + 1);

    cout << res << '\n';


    return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
//#include <algorithm>
#include <vector>
 
int main(int argc, char* argv[])
{
    const long NN=5;
    long p[NN] = {3, 5, 7, 11, 13};

    long n;
    scanf("%ld", &n );

    long count = 0;
    long i, j, k;
    for(i=0; i<NN; i++) {
        for(j=i+1; j<NN; j++) {
            for(k=j+1; k<NN; k++) {
                if(p[i]*p[j]*p[k] <= n) {
                    count ++;
                }
            }
        }
    }

    for(i=1; i<NN; i++) {
        if(3*3*3*p[i] <= n) {
            count ++;
        }
    }
 
    printf("%d\n", count);
 
    return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;
typedef long double LD;

const LD myPI = 3.141592653589793238;
const LD eps = 0.000000001;
int main()
{
	LD a, b, x;
	in >> a >> b >> x;

	x /= a;
	LD left = 0, right = 90;
	rep(loop, 60)
	{
		LD mid = (left + right) / 2, vol;
		LD rad = myPI * mid / 180;
		if (a >= b * tan(rad)) vol = b * b * tan(rad) / 2;
		else vol = (2 * b - a / tan(rad)) * a / 2;
		if (eps > x - vol) right = mid;
		else left = mid;
	}

	out << std::fixed << std::setprecision(10);
	out << 90 - left << std::endl;
}


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

using namespace std;

typedef long long ll;


ll N, K;


//vector <ull> A;

ll Am[200001] = { -1, };
ll vcount[200001] = { 0, };
ll istep[200001] = { -1, };
ll Dest[200001] = { -1, };

int main() {
	ll i, j;
	ll a;
	ll loop = 0;
	ll k_left;

	cin >> N >> K;
	for (i = 0; i < N; i++) {
		cin >> a;
		//A.push_back(a);
		Am[i] = a-1;
	}

	k_left = K;
	ll i_loop = -1;
	ll pos=0, new_pos;
	ll pos_loop;
	vcount[0] = 1;

	for (i = 0; i < K; i++) {
		istep[pos] = i;

		new_pos = Am[pos];
		Dest[i] = new_pos;
		if (vcount[new_pos] == 0) {
			vcount[new_pos] = 1;
			k_left--;
			pos = new_pos;
		}
		else if (i_loop == -1) {
			i_loop = i;
			pos_loop = istep[new_pos];
			break;
		}

	}
#ifdef DEBUG
	for (i = 0; i < N; i++) {
		cout << Dest[i] + 1 << " ";
	} 
	cout << endl;
	cout << "k_left=" << k_left << " i_loop=" << i_loop << " pos_loop=" << pos_loop << endl;
#endif

	if (k_left == 0) {
		cout << (Dest[K-1] + 1) << endl;
	}
	else {
		ll km = (K-pos_loop) % (i_loop - pos_loop + 1);
		//cout << km << endl;
		cout << (Dest[pos_loop+km-1] + 1) << endl;
	}


}

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

using namespace std;

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

	string s;
	cin >> s;

	int n1 = (s[0] - '0') * 10 + (s[1] - '0'); 
	int n2 = (s[2] - '0') * 10 + (s[3] - '0'); 

	if((n1 == 0 and n2 == 0) or (n1 > 12 and n2 > 12) or (n1 == 0 and n2 > 12) or (n2 == 0 and n1 > 12)) cout << "NA";
	else if((n1 > 0 and n1 <= 12) and (n2 == 0 or n2 > 12)) cout << "MMYY";
	else if((n2 > 0 and n2 <= 12) and (n1 == 0 or n1 > 12)) cout << "YYMM";
	else cout << "AMBIGUOUS";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n; cin >> n;
    vector<pair<int,int>> x(n);
    for(int i=0; i<n; ++i){
        cin >> x[i].second >> x[i].first;
    }
    sort(x.begin(),x.end());

    int s=0;
    bool flg=1;
    for(int i=0; i<n; ++i){
        s += x[i].second;
        if(s>x[i].first){
            flg = 0;
            break;
        }
    }
	cout << (flg ? "Yes" : "No") << endl;
}

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

main() {
  double r, s, l, pai = acos(-1.0);

  scanf("%lf", &r);

  s = r * r *  pai;
  l = 2 * pai * r;

  printf("%f %f\n", s, l);

  return 0;
}

Measured memory_bytes: 648
N,X = map(int,input().split())
L = list(map(int,input().split()))
DA = 0
D = [0]
for i in range(N):
  DA = DA + L[i]
  D.append(DA)
ANS = 0
for i in range(len(D)):
  if D[i] <= X:
    ANS += 1
  else:
    break
print(ANS)

Measured memory_bytes: 3064
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())

r, d, x = tuple(li())

def grow(x):
    return r * x - d
for i in range(10):
    x = grow(x)
    print(x)


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

#define     FasterIO        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     bug(a,b)        cout<<a<<"\t"<<b<<"\n";
#define     Case(a,b)       cout<<"Case "<<a<<": "<<b<<"\n";
#define     precision(a,b)  fixed<<setprecision(a)<<b
#define     lp(i,a,b)       for(int i=a;i<b;i++)
#define     Endl            "\n"
#define     tab             "\t"
#define     reset(a,b)      memset(a,b,sizeof(a));
#define     sf(a)           scanf(" %d", &a);
#define     sfl(a)          scanf(" %lld", &a);
#define     srt(a)          sort(a.begin(),a.end());
#define     ALL(a)          a.begin(),a.end()
#define     pi              2*acos(0.0)

typedef long long int ll;
typedef unsigned long long int ull;

const int sz=1e5+9 , inf=INT_MAX ,mod=1e9+7;


void solve(){
    ll n ,m , k , l , r ,d , x , y , ans=0 ;
    cin>>l>>r>>d;

    ans=r/d;
    if(l%d==0){
        ans-=(l/d)-1;
    }else{
        ans-=(l/d);
    }
    cout<<ans<<Endl;

    
}

int main(){
    FasterIO;
    #ifndef ONLINE_JUDGE
        freopen("input.in","r",stdin);
        freopen("output.in","w",stdout);
    #endif
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}


Measured memory_bytes: 3584
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define rep(i, f, n) for (int i = (f); i < (int)(n); i++)
#define repe(i, f, n) for (int i = (f); i <= (int)(n); i++)
using namespace std;
using ll = long long;
using pint = pair<int, int>;

int main() {
  int D, N;
  cin >> D >> N;
  int s = 1;
  rep(i, 0, D) s *= 100;
  if (N <= 99)
    cout << s * N << endl;
  else
    cout << s * 101 << endl;
  return 0;
}


Measured memory_bytes: 3600
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//typedef pair<int,int> P;



int main(){
	int N;
	int a[100000];

	scanf("%d", &N);
	for(int i=0;i<N;i++){
		scanf("%d", &a[i]);
	}

	int num[100000];
	memset(num,0,sizeof(num));
	for(int i=0;i<N;i++){
		num[a[i]-1]++;
	}

	int n1 = 0;
	int n2 = 0;
	for(int i=0;i<100000;i++){
		if(num[i]>0) n1++;
		if(num[i]>0 && num[i]%2==0){
			num[i] = 2;
			n2++;
		}
		if(num[i]>0 && num[i]%2==1) num[i] = 1;
	}

	int ans = 0;
	if(n2%2==0){
		ans = n1;
	}else{
		ans = n1-1;
	}

	printf("%d\n", ans);


	return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a, b, ans;
	cin >> a >> b;
	float x = 0.08;
	float y = 0.10;
	bool flag = false;
	for(int i = 1; i < 10000; i++)	
	{
		int z = floor(x*i);
		int w = floor(y*i);
		if((z==a) && (w==b))
		{
			ans =  i;
			flag = true;
			break;
		}
	}
	if(flag == false)
	{
		cout << "-1";
	}
	else
	{
		cout << ans;
	}
}

Measured memory_bytes: 256
import bisect
N,M,K = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

A.append(float("inf"))
B.append(float("inf"))
bs = [0]
for i in B:
    bs.append(bs[-1]+i)

ans = 0
now = 0

for i in range(N+1):

    ind = bisect.bisect_right(bs,K-now)-1

    ans = max(ans , i + ind)
    
    now += A[i]
    if now > K:
        break

print (ans)


Measured memory_bytes: 124052
#include<bits/stdc++.h>
using namespace std;
double dp[3001][3001];
double solve(vector<double>& arr, int i, int x)
{
	if(x == 0)return 1;
	if(i == 0)return  0;
	if(dp[i][x] > -0.9)return dp[i][x];
	return dp[i][x] = arr[i]*solve(arr,i-1,x-1) + (1-arr[i])*solve(arr,i-1,x);
}
int main()
{
	int n;
	cin >> n;
	vector<double> arr(n + 1);
	memset(dp, -1, sizeof dp);
	for(int i = 1; i <= n; i++)cin >> arr[i];
	double x = solve(arr, n, (n+1)/2);
	cout << fixed << setprecision(10) << x;
	return 0;
}

Measured memory_bytes: 74356
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

bool check(ll n) {
    cout << "? " << n << endl << flush;
    string ans;
    cin >> ans;
    return (ans == "Y");
}

int main(void)
{
    // cin.sync_with_stdio(false);
    ll MAX = 1000000000;
    if (check(MAX * 10)) {
        ll query = MAX / 10;
        bool found = false;
        while(query >= 1) {
            if (check(query + 1)) {
                query /= 10;
            }
            else {
                found = true;
                break;
            }
        }
        ll ans = 1;
        if (found) ans = query * 10;
        cout << "! " << ans << endl << flush;
        return 0;
    }


    ll query = 1;
    while(1) {
        if (check(query)) {
            query *= 10;
        }
        else break;
    }
    
    ll lo = query;
    ll hi = query * 10 - 1;
    while(lo < hi) {
        ll k = (lo + hi) / 2;
        if (check(k)) {
            hi = k;
        }
        else {
            lo = k + 1;
        }
    }
    cout << "! " << lo / 10 << endl << flush;

    return 0;
}


Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
using ld = long double;
#define vpl vector<pair<long long,long long>>
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
long long MOD = 1000000007;
const long double pi = 3.1415926535897932;
#define pb push_back
#define mp make_pair
#define mt make_tuple
using Grid = vector<vector<char>>;
#define vc vector<char>
//(mod m)でのaの逆元を計算する
//a/b(mod m)=a(mod m)*modinv(b,m)
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;
}

//最大最小の入れ替え
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;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる

//ここから
int main(){
    ll N;
    cin>>N;
    vl vec(N);
    rep(i,N)cin>>vec[i];
    vl dp(N,0);
    dp[0]=1;
    map<ll,ll> m;
    m[vec[0]]=1;
    rep2(i,1,N){
        ll x=vec[i];
        if(m[x]!=i&&m[x]!=0){
            dp[i]=dp[m[x]-1];
        }
        dp[i]+=dp[i-1];
        dp[i]%=MOD;
        m[x]=i+1;
    }
    cout<<dp[N-1]<<endl;
}

Measured memory_bytes: 15872
import itertools

bingo = []

for _ in range(3):
    array = list(map(int, input().split()))
    bingo.append(array)

bingo = list(itertools.chain.from_iterable(bingo))

bingo_bi = [False for _ in range(9)]

n = int(input())

nums = []

for _ in range(n):
    num = int(input())
    if num in bingo:
        bingo_bi[bingo.index(num)] = True

correct = [True, True, True]

if bingo_bi[0:3] == correct or bingo_bi[3:6] == correct or bingo_bi[6:9] == correct:
    print('Yes')
elif bingo_bi[0::3] == correct or bingo_bi[1::3] == correct or bingo_bi[2::3] == correct:
    print('Yes')
elif bingo_bi[0] == True and bingo_bi[4] == True and bingo_bi[8] == True:
    print('Yes')
elif bingo_bi[2:8:2] == correct:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
import java.util.Scanner;

//Planetary Exploration
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt(), w = sc.nextInt(), k = sc.nextInt();
		char[][] m = new char[h][];
		for(int i=0;i<h;i++)m[i]=sc.next().toCharArray();
		int[][] sj = new int[h+1][w+1], so = new int[h+1][w+1], si = new int[h+1][w+1];
		for(int i=0;i<h;i++)for(int j=0;j<w;j++){
			sj[i+1][j+1] = sj[i][j+1]+sj[i+1][j]-sj[i][j]+(m[i][j]=='J'?1:0);
			so[i+1][j+1] = so[i][j+1]+so[i+1][j]-so[i][j]+(m[i][j]=='O'?1:0);
			si[i+1][j+1] = si[i][j+1]+si[i+1][j]-si[i][j]+(m[i][j]=='I'?1:0);
		}
		while(k--!=0){
			int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt();
			int rj = sj[c][d]-sj[a-1][d]-sj[c][b-1]+sj[a-1][b-1];
			int ro = so[c][d]-so[a-1][d]-so[c][b-1]+so[a-1][b-1];
			int ri = si[c][d]-si[a-1][d]-si[c][b-1]+si[a-1][b-1];
			System.out.println(rj+" "+ro+" "+ri);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 27000
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace A
{
    class Program
    {
        /// <summary>
        ///   The main entry point for the application
        /// </summary>
        [STAThread]
        public static void Main(string[] args)
        {
            string str_n = Console.ReadLine();//2つ以上のスペース区切り入力の取得
            string[] str_h = Console.ReadLine().Split(' ');
            int count = int.Parse(str_n);
            int end = 0;
            int start = 0;
            int high = int.Parse(str_h[0]);
            int max = 0;
            for (int i = 1; i < count; i++) {
                if(high < int.Parse(str_h[i])) {
                    end = i - 1;
                    if(end - start > max) {
                        max = end - start;
                    }
                    start = i;
                }
                high = int.Parse(str_h[i]);
            }
            end = count - 1;
            if(end - start > max) {
                max = end - start;
            }
            Console.Write("{0}", max);
        }
    }
}

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

int main(){
    string n;
    cin >> n;
    if((n.at(0)==n.at(1) && n.at(1)==n.at(2)) || (n.at(1)==n.at(2) && n.at(2)==n.at(3)))
      cout << "Yes" << endl;
    else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
G = {}
for node in range(1,N+1):
	G[node] = set()
for _ in range(M):
	x,y = map(int,input().split())
	G[x].add(y)

maxpath = [-1 for _ in range(N+1)]

def maxpa(G,source,maxpath):
	if maxpath[source] != -1:
		return maxpath[source]
	else:	
		if len(G[source]) == 0:
			maxpath[source] = 0
			return maxpath[source]
		else:	
			for ngbr in G[source]:
				maxpath[source] = max(maxpath[source],1+maxpa(G,ngbr,maxpath))
			return maxpath[source]

for i in range(1,N+1):
	if maxpath[i]==-1:
		maxpa(G,i,maxpath)

print(max(maxpath))

Measured memory_bytes: 163520
// https://atcoder.jp/contests/abc151/tasks/abc151_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)

const int MOD = 1e9 + 7;
template <int mod> struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod)
            x -= mod;
    }
    ModInt &operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod)
            x -= mod;
        return *this;
    }
    ModInt &operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0)
            x += mod;
        return *this;
    }
    ModInt &operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt &operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }
    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }
    friend ostream &operator<<(ostream &s, ModInt<mod> a) {
        s << a.x;
        return s;
    }
    friend istream &operator>>(istream &s, ModInt<mod> &a) {
        s >> a.x;
        return s;
    }
};
using mint = ModInt<MOD>;
vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};

void check_fact(int n) {
    for (int i = I_.size(); i <= n; i++) {
        I_.push_back(I_[MOD % i] * (MOD - MOD / i));
        F_.push_back(F_[i - 1] * i);
        R_.push_back(R_[i - 1] * I_[i]);
    }
}

mint I(int n) {
    check_fact(abs(n));
    return n >= 0 ? I_[n] : -I_[n];
}
mint F(int n) {
    check_fact(n);
    return n < 0 ? 0 : F_[n];
}
mint R(int n) {
    check_fact(n);
    return n < 0 ? 0 : R_[n];
}
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i, N) { cin >> A[i]; }
    sort(ALL(A));
    mint ans = 0;
    // Σ max_S を求める
    FOR(i, K - 1, N) {
        // 最大値がA[i]になる組み合わせはA[i-1]以下からK-1個選ぶ
        ans += C(i, K - 1) * A[i];
    }
    reverse(ALL(A));
    // Σ min_S を求める
    FOR(i, K - 1, N) {
        // 最小値がA[i]になる組み合わせはA[i+1]以上からK-1個選ぶ
        ans -= C(i, K - 1) * A[i];
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 6552