akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
int n,k;
int main(void){
scanf("%d%d",&n,&k);
for(int i=0;i<k;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x+y<=n)printf("%d\n",x<y?(x-1)%3+1:(y-1)%3+1);
else printf("%d\n",x>y?(n-x)%3+1:(n-y)%3+1);
}
return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define MD 1000000007
typedef long long int ll;

int main(){
    int n;
    cin>>n;
    vector<string> s(n);
    int data[51][26]={0};//アルファベットの出現回数格納
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i].size();j++){
            data[i][s[i][j]-'a']++;
        }
    }
    int m=0;
    for(int i=0;i<26;i++){
        for(int j=0;j<n;j++){
            if(j==0){
                m=data[j][i];
            }else{
                m=min(m,data[j][i]);
            }
        }
        for(int k=0;k<m;k++){
            char t='a';
            t+=i;
            cout<<t;
        }
    }
    cout<<endl;
           
    return 0;
}

Measured memory_bytes: 256
from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def main():

    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))

    AB = sorted(p, reverse=True)[:X] + sorted(q, reverse=True)[:Y]
    ans = sum(AB)
    AB_q = PriorityQueue(AB)
    ab_now = AB_q.pop()

    for r_ in r:
        if r_ > ab_now:
            ans = ans - ab_now + r_
            AB_q.push(r_)
            ab_now = AB_q.pop()
    print(ans)


if __name__ == '__main__':
    main()


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

#define rep(i,a,b) for(int i=a;i<b;i++)
#define INF INT_MAX/2

int main()
{
	while (1)
	{
		int a, b, d;
		cin >> a >> b >> d;
		if (a == 0) return 0;

		rep(sum, 1, 100000)
		{
			int _min = INF;
			int _x, _y;
			rep(x, 0, sum + 1)
			{
				int y = sum - x;

				if ((a*x + d == b*y || a*x == b*y + d) || a*x+b*y == d)
				{
					if (a*x + b*y < _min)
					{
						_min = a*x + b*y;
						_x = x;
						_y = y;
					}
				}
			}
			if (_min != INF)
			{
				cout << _x << " " << _y << endl;
				break;
			}
		}
	}
}

Measured memory_bytes: 3076
#include<stdio.h>

int main(void){
	int n,i,j,team[100],score[100],a,b,c,d;
	scanf("%d",&n);
	for(i=0; i<n; i++){
		team[i]=0;
	}
	for(i=0; i<n*(n-1)/2; i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(c>d){
			team[a-1]+=3;
		}else if(c<d){
			team[b-1]+=3;
		}else{
			team[a-1]++;
			team[b-1]++;
		}
	}
	for(i=0; i<n; i++){
		score[i]=1;
		for(j=0; j<n; j++){
			if(team[i]<team[j]){
				score[i]++;
			}
		}
	}
	for(i=0; i<n; i++){
		printf("%d\n",score[i]);
	}
	return 0;
}

Measured memory_bytes: 600
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define rrep(i,a,n) for(ll i=n;i>=a;i--)
#define elif else if
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF = 1e+17;
const ll MODcdf = 998244353;
bool pairCompare(const P& firstElof,const P& secondElof){
    return firstElof.first<secondElof.first;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n,m;cin>>n>>m;
    vector<P> ab(n);
    rep(i,0,n)cin>>ab[i].first>>ab[i].second;
    sort(ab.begin(),ab.end(),pairCompare);
    //cout<<"DEBUG START"<<endl;
    //rep(i,0,n)cout<<ab[i].first<<" "<<ab[i].second<<endl;
    ll ans=0;
    rep(i,0,n){
        if(m>ab[i].second){
            //cout<<"can"<<" "<<m<<"→";
            m-=ab[i].second;
            ans+=ab[i].first*ab[i].second;
            //cout<<m<<endl;
        }else{
            //cout<<"couldn't"<<" "<<m<<"→";
            ans+=ab[i].first*m;
            break;
            //cout<<m<<endl;
        }
    }
    //cout<<"DEBUG END"<<endl;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
//我是菜鸡
#include <bits/stdc++.h>
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _defor(i,a,b) for((i) = (a);(i)<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto p:st)
#define debug(q,x) cout<<q<<x<<endl
//#define _LOCAL_
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 10+5;
const int MOD = 1e9+7;
const double exps = 1e-6;
void deprint() {
	ofstream cout("E:\\acm dream\\debug.txt");
	return;
}
ll qpow(ll x, ll y) {
	ll ans = 1;
	while (y) {
		if (y & 1)ans = ans * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return ans;
}
ll comb(int n, int m) {
	ll ans = 1;
	if (m > n - m)m = n - m;
	_for(i, n - m + 1, n + 1)ans = (ans % MOD) * i % MOD;
	_for(i, 1, m + 1)ans = ans * qpow(i, MOD - 2) % MOD;
	return ans;
}
int main() {
#ifdef _LOCAL_
	ifstream cin("E:\\acm dream\\in.txt");
	ofstream cout("E:\\acm dream\\out.txt");
#endif
	//srand((unsigned)time(nullptr));
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n, a, b;
	while (cin >> n >> a >> b) {
		cout << (qpow(2, n) - 1 - comb(n, a) - comb(n, b) + MOD + MOD) % MOD << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
 
static const int N = 500;
static const int INFTY = (1<<21);
 
#define NIL -1
 
int p[100];
int key[100];
int n;
 
 
main(){
  int i,j,a,b,c,sum;
  int M[100][100];
  int l[100];
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    for (j=0;j<n;j++){
      scanf("%d",&a);
      M[i][j] = (a==-1)?INFTY:a;
    }
  }
 
 
 
  for(c=0;c<n;c++){
    key[c]=100000000;
 
    p[c]=NIL;
 
    l[c]=NIL;
  }
  key[0]=0;
 
  while(1){
    int c=NIL;
    int b=100000000;
 
 
    for(i=0;i<n;i++){
      
 
      if(key[i]<b && l[i]==NIL){
    b=key[i];
    c=i;
      }
    }
     
       
     
    if(c==NIL){
      break;
    }
 
    for(b=0;b<n;b++){
      if(M[c][b] < key[b] && l[b]==NIL){
    key[b]=M[c][b];
    p[b]=c;
      }
    }
    l[c]=0;
  }
 
 
  sum = 0;
 
  for ( i = 0; i < n; i++ ){
    if ( p[i] != -1 ) sum += M[i][p[i]];
  }
 
  printf("%d\n", sum);
 
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int         long long   
#define double      long double
#define endl        "\n"
#define pb          push_back
#define PI          3.1415926535897932384626433832795l
#define F           first
#define S           second
#define mp          make_pair
#define f(i,n)      for(int i=0;i<n;i++)
#define fastio      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(v)      (v).begin(),(v).end()
#define sort(v)     sort((v).begin(),(v).end())
#define rall(v)     (v).rbegin(),(v).rend()
#define rsort(v)     sort((v).rbegin(),(v).rend())
#define gcd(a,b)    __gcd((a),(b))
#define minn(v)     *min_element(v.begin(), v.end());
#define maxx(v)     *max_element(v.begin(), v.end());
#define print(x)    cout<<(x)<<endl;
typedef pair<int,int> pii;  
typedef vector<int> vi;
//x.substr(start, length);
/*
// Create a vector containing n 
//vectors of size m.  
    vector<vector<int> > vec( n , vector<int> (m, 0));  
*/
struct type{
    int k, i, j;
};
//to check if a no is prime or not?
bool isPrime(int n) 
{ 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
}

// minimum subaaray sum of size k-sliding window approach
int findSubarray(int arr[], int n, int k)
{
	int window_sum = 0;
	int min_window = INT_MAX;
	int last = 0;
	for (int i = 0; i < n; i++)
	{
		window_sum += arr[i];
		if (i + 1 >= k)
		{
			if (min_window > window_sum)
			{
				min_window = window_sum;
				last = i;
			}
			window_sum -= arr[i + 1 - k];
		}
	}
	int sum=0;
	for(int i=last-k+1;i<=last;i++)
	{
	    sum+=arr[i];
	}
	return sum;
}
signed main() 
{
    fastio;
    //cout << fixed << setprecision(0);
    int n,m;
    cin>>n>>m;
    vi a(n+1,0);
    int wr=0;
    int ac=0;
    vi b(n+1,0);
    f(i,m)
    {
        int z;
        string s;
        cin>>z>>s;
    
        if(a[z]==0 and s=="WA")
        {
            b[z]++;
        }
        else if(s=="AC" and a[z]==0)
        {
            ac++;
            a[z]=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]==1)
        {
            wr+=b[i];
        }
    }
    cout<<ac<<" "<<wr<<endl;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define INF 1'000'000'000


int main() {
    i64 N; cin >> N;
    vector<i64> A(N);
    REP(i, N) cin >> A[i];
    REP(i, N) A[i] -= i;

    auto f = [&](i64 b) {
        i64 v = 0;
        REP(i, N) v += abs(A[i] - b);
        return v;
    };

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

    i64 median = A[N / 2];
    cout << f(median) << endl;

    return 0;
}

Measured memory_bytes: 1792
using System;
using System.Linq;

namespace ABC
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			//var a = Console.ReadLine ().Split().Select(x=>int.Parse(x)).ToArray();
			int sum = 0;
			int N = int.Parse(Console.ReadLine ());
			int K = int.Parse(Console.ReadLine ());
			int X = int.Parse(Console.ReadLine ());
			int Y = int.Parse(Console.ReadLine ());
			if (N - K >= 0)
				sum = X * K + Y * (N - K);
			else
				sum = X * Math.Min(N,K);
			Console.WriteLine (sum);
		}
	}
}


Measured memory_bytes: 2648
<?php

class Scanner
{
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next()
    {
        if ($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(" ", $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }

    public function hasNext()
    {
        return $this->pointer < $this->count;
    }

    public function nextInt()
    {
        return (int)$this->next();
    }

    public function nextDouble()
    {
        return (double)$this->next();
    }
}

class out
{
    public static function printIn($str = "")
    {
        echo $str . PHP_EOL;
    }
}

$sc = new Scanner;

$N = $sc->nextInt();
$ans = 1000000;
for ($A = 1; $A <= $N / 2 ; $A++) {
  $B = $N - $A;
  $a = array_sum(str_split($A));
  $b = array_sum(str_split($B));
    if ($a + $b < $ans) {
        $ans = $a + $b;
    }
}

echo $ans;

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

using namespace std;

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long

#define for(i,a,b) for (i=a; i<b; i++)
#define forb(i,a,b) for (i=a; i>b; i--)
#define all(S) S.begin(),S.end()
#define sort(S) sort(all(S))

const int inf = 1e9;
const ll INF = 1e18;

ll k,dp[10][10];

void go(ll s, ll c, ll cur, ll ans)
{
    ll ans1 = ans*10+c;
    if (s==0)
    {
        cout << ans1 << endl;
        return;
    }
    ll cur1 = cur;
    if (c>0)
        cur1+=dp[s-1][c-1];
    if (cur1>=k)
    {
        cur1-=dp[s-1][c-1];
        go(s-1,c-1,cur1,ans1);
        return;
    }
    cur1+=dp[s-1][c];
    if (cur1>=k)
    {
        cur1-=dp[s-1][c];
        go(s-1,c,cur1,ans1);
        return;
    }
    go(s-1,c+1,cur1,ans1);
    return;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i,j,p=0;
    cin >> k;
    for (i,0,10)
        dp[0][i]=1;

    for (i,1,10)
    {
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][9]=dp[i-1][9]+dp[i-1][8];
        for (j,1,9)
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];
    }

    for (i,0,10)
    {
        for (j,1,10)
        {
            p+=dp[i][j];
            if (p>=k)
            {
                go(i,j,p-dp[i][j],0);
                break;
            }
        }
        if (p>=k)
            break;
    }
    return 0;
}


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

int main() {
  int a , b , c , k ;
  cin >> a >> b >> c>> k;
  
  if(a+b>=k){
    if(a>=k){
      cout << k << endl;
    }
    else{
      cout << a << endl;
    }
  }
  
  else{
    cout << a-k+a+b << endl;
  }
}

Measured memory_bytes: 3596
import scala.math.{min,max}

object Main {
  val sc = new java.util.Scanner(System.in)
  def main(args: Array[String]) {
    while(true) {
      val s = sc.nextInt
      if(s == 0) return
      println(s - (1 to 9).map(_ => sc.nextInt).sum)
    }
  }
}

Measured memory_bytes: 45128
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    vector<int> A(200);
    int N;
    cin >> N;
    rep(i, N){
        int a;
        cin >> a;
        A[a]++;
    }
    int ans = 0;
    rep(i, 200){
        if(A[i] > 0) ans++;
    }
    output(ans);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#pragma GCC optimize("Ofast")
using namespace std;
const long long INF=20000000000;
//setprecision(2) <<

const int MOD = 1000000007;

long long max(long long a,long long b){
	if(a<b)return b;
	else return a;	
}
long long min(long long a,long long b){
	if(a>b)return b;
	else return a;	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;cin>>n;
	int A[n];
	for(int i=0;i<n;i++)cin>>A[i];
	int count=0;
	long long  ans=0;
	long long minv=INF; 
	for(int i=0;i<n;i++){
			ans+=abs(A[i]);
			minv = min(minv,abs(A[i]));
		if(A[i]<=0){
			count++;
		}
	}
	//cout<<ans<<endl;
	
	if(count%2==0)cout<<ans<<endl;
	else cout<<ans-2*minv<<endl;
}
	


Measured memory_bytes: 640
#include <iostream>

int main(){
    int a;
    std::cin >> a;
    for(int i=1;i<=a;i++){
        int b,c;
        std::cin >> b >> c;
        if(b%c!=0){
        std::cout << b%c << std::endl;
        }
        else if(b%c==0){
            std::cout <<c << std::endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1160
// Problem : C - Digits in Multiplication
// Contest : AtCoder - AtCoder Beginner Contest 057
// URL : https://atcoder.jp/contests/abc057/tasks/abc057_c
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
int n;cin>>n;
int ans=INF;
for(int i=1;i*i<=n;i++)
{
	if(n%i==0)
	{
		int a=size(to_string(i));
		int b=size(to_string(n/i));
		ans=min2(ans,max2(a,b));
	}
}
cout<<ans;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

//a <= b
i64 calc (i64 a, i64 b) {
  if (a + 1 >= b) {
    return 2 * a - 2;
  }
  i64 l = 1;
  i64 r = b - a;
  while (r - l > 1) {
    i64 m = (l + r) / 2;
    i64 t = m / 2;
    if ((a + t) * (a + m - t) < a * b) {
      l = m;
    } else {
      r = m;
    }
  }
  return 2 * a - 2 + l;;
}

void run (void) {
  i32 q;
  scanf ("%" SCNi32, &q);
  while (q--) {
    i32 a, b;
    scanf ("%" SCNi32 "%" SCNi32, &a, &b);
    i64 ans = calc (MIN(a, b), MAX(a, b));
    printf ("%" PRIi64 "\n", ans);
  }
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
ll mod = 1000000007;
ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);

//二分累乗法 modを設定すること

ll dp[2100][2100];

signed main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> s(n,0),t(m,0);

    for(int i=0;i < n;i++)
    {
        cin>>s.at(i);
    }
    for(int i=0;i < m;i++)
    {
        cin>>t.at(i);
    }

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

    for(int i=0;i < n+1;i++)
    {
        for(int j=0;j < m+1;j++)
        {
            if(j>0)dp[i][j]+=dp[i][j-1];

            if(i>0)dp[i][j]+=dp[i-1][j];
            
            if(j>0 && i>0 && s[i-1]!=t[j-1]) dp[i][j]+=mod-dp[i-1][j-1];
          
            dp[i][j]%=mod;
        }
    }
    cout << dp[n][m]%mod << endl;
}
/*共通文字列のDPは、それぞれの文字列をどこまで見たかに対応する二つの添え字をもってやる */


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

using namespace std;

#define ll long long
#define vi  vector<int>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD 1e9 + 7
#define PAI  3.1415
#define all(x) (x).begin(),(x).end()
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i,n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

ll gcd(ll a,ll b){
  if(a < b)swap(a , b);
  if(a % b == 0) return b;
  else gcd(b, a%b);
}

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a/gcd(a , b))*b;
}

struct UnionFind {
  vi par; //par[i] : iの親番号（例）par[3] = 2 : 3の親は2

  UnionFind(int N) : par(N) { //最初は全てが根として初期化
    rep(i,N) par[i] = i;
  }

  int root(int x){ //データxが属する木の根を再帰で得る : root(x) = {xの木の根}
    if(par[x] == x)return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y){ //xとyの木を併合
    int rx = root(x); //xの根をrx
    int ry = root(y); //yの根をry
    if(rx == ry)return; //xとyの根が同じ
    par[rx] = ry; //xとyの根が同じでない時、xの根rxをyの根にryにつける。
  }

  bool same(int x, int y){//2つのデータx，yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

int main(){
  int n;
  char c;

  while(cin >> n,n){

    vector< pair<int, char> > vic;
    rep(i,26)vic.pb(mp(0, 'A' + i));

    string anscap = "TIE";
    bool overlap = true;
    int ans;

    rep(i,n){
      cin >> c;
      bool jud = false;

      rep(j,26)
        if(c == vic[j].second)vic[j].first++;

      sort(all(vic));

      if(vic[25].first > vic[24].first + n - i - 1)
        jud = true;

      if(jud and anscap == "TIE"){
        overlap = false;
        anscap = vic[25].second;
        ans = i + 1;
      }
     }

    if(overlap)cout << anscap << endl;
    else cout << anscap << ' ' << ans << endl;

  }

  return 0;

}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
int dp[105][4][2];//dp[上から何桁][０の個数][未満フラグ]
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int K;

    cin >> K;
    dp[0][0][0] = 1;
    rep(i,n)rep(j,4)rep(k,2){
        int nd = s[i] - '0';
        rep(d,10){
            int ni = i+1,nj = j,nk = k;
            if(d!=0)nj++;
            if(nj > K)continue;
            if(k == 0){
                if(d > nd)continue;
                if(d < nd)nk = 1;
            }
            dp[ni][nj][nk] += dp[i][j][k];
        }


    }
    int ans = dp[n][K][0]+dp[n][K][1];
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007


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

    // input
    int N;
    int d[110];
    cin >> N;
    REP(i, N) cin >> d[i];
    
    int num[110] = {0};  // bucket
    for (int j = 0; j < N; ++j) {
        num[d[j]]++;
    }
    
    int res = 0;
    REPN(i, 100) {
        if (num[i] > 0) {
            res++;
        }
    }
    cout << res << "\n";
    
    return 0;
}


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

int main() {
  string N;
  cin >> N;
  bool a=false;
  for(int i=0;i<2;i++){
    if(N.at(i)==N.at(i+1) && N.at(i+1)==N.at(i+2)){
      a=true;
    }
  }
  if(a){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void) {
  int N,B[100],i,j,ans=0,M[100],A[100];
  for(i=0;i<100;i++)M[i]=0;
  scanf("%d",&N);
  for(i=0;i<N;i++)scanf("%d",&B[i]);
  for(i=0;i<N;i++) {
    if(B[i] > i+1)ans++;
  }
  if(ans)printf("%d\n",-1);
  else {
    for(i=0;i<N+1;i++) {
      for(j=0;j<N-i;j++) {
        if(B[j] == j+1) {
          M[i]=j+1;
        }
      }
      for(j=M[i]-1;j<N-i-1;j++) {
        B[j] = B[j+1];
      }
    }
    for(i=N-1;i>-1;i--)printf("%d\n",M[i]);
  }
}

Measured memory_bytes: 128
k,a,b=map(int,input().split())
bis=1
total=0
mon=0
if a+2>=b or k<=a-1:
    total=k+1
else:
    x=k-a+1
    total+=a
    total+=(x//2)*(b-a)
    if (k-a+1)%2==1:
        total+=1
    
print(total)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
constexpr lnt INF = 2e18;
/*-*/

constexpr lnt MOD = 998244353;
struct mint
{
    lnt v;
    mint():v(0){}
    mint(lnt v):v((v+MOD)%MOD){}
    mint operator-()const{ return mint(0) - *this; }
    mint& operator+=(const mint& a){ if((v+=a.v)>=MOD) v-=MOD; return *this; }
    mint& operator-=(const mint& a){ if((v+=MOD-a.v)>=MOD) v-=MOD; return *this; }
    mint& operator*=(const mint& a){ (v*=a.v)%=MOD; return *this; }
    mint& operator/=(const mint& a){ (*this) *= a.inv(); return *this; }
    mint operator+(const mint& a)const{ return mint(*this) += a; }
    mint operator-(const mint& a)const{ return mint(*this) -= a; }
    mint operator*(const mint& a)const{ return mint(*this) *= a; }
    mint operator/(const mint& a)const{ return mint(*this) /= a; }
    bool operator<(const mint& a)const{ return v < a.v; }
    bool operator==(const mint& a)const{ return v == a.v; }
    mint pow(lnt k)const{ mint r(1),t(v); while(k){ if(k&1) r*=t; t*=t; k>>=1; } return r; }
    mint inv()const{ return pow(MOD-2); }
    static mint comb(lnt n, lnt k) {
        if(n-k<k) k=n-k;
        mint num(1), dom(1);
        for(int i=0;i<k;i++) { num*=n-i; dom*=i+1; }
        return num/dom;
    }
    static std::vector<mint> construct_comb(int n) {
        std::vector<mint> c(n+1);
        mint a = 1; c[0] = a;
        for(int i=1;i<=n;i++) {
            a = a*mint(n+1-i)/i;
            c[i] = a;
        }
        return c;
    }
    static std::vector<mint> construct_fact(int n) {
        std::vector<mint> f(n+1,1);
        for(int i=2;i<=n;i++) f[i]=f[i-1]*i;
        return f;
    }
};
std::istream& operator>>(std::istream&i,mint&a){ lnt t; i>>t; a=mint(t); return i; }
std::ostream& operator<<(std::ostream&o,const mint&a){ o<<a.v; return o; }


int main() {
	lnt n,s;
	std::cin >> n >> s;
	std::vector<lnt> a(n);
	rep(i,n) std::cin >> a[i];
	std::vector<mint> dp(s+1,0);
	dp[0]=1;
	rep(i,n) {
		for(int j=s;j>=0;j--) {
			if(j-a[i]>=0) dp[j]+=dp[j-a[i]]/mint(2);
		}
	}
	print(dp[s]*mint(2).pow(n));
}


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

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (auto &e : a) {
    cin >> e;
  }
  vector<vector<int>> v(40, vector<int>(2));
  for (int i = 0; i < v.size(); i++) {
    for (auto e : a) {
      v[i][0] += (e >> i) & 1;
      v[i][1] += !((e >> i) & 1);
    }
  }
  vector<ll> s(v.size() + 1), m(v.size() + 1);
  for (int i = 0; i < v.size(); i++) {
    s[i + 1] = s[i] + v[i][(k >> i) & 1] * (1ll << i);
    m[i + 1] = m[i] + max(v[i][0], v[i][1]) * (1ll << i);
  }
  ll r = s.back();
  for (int i = 0; i < v.size(); i++) {
    if ((k + 1 >> i) & 1) {
      r = max(r, (s.back() - s[i + 1]) + v[i][0] * (1ll << i) + (m[i] - m.front()));
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 1024
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    let p: usize = sc.read();
    let a: Vec<usize> = sc.vec(p);
    let comb = Combination::new(p, p);

    // 1 - (x-j)^(p-1)
    let mut ans = vec![0; p];
    for i in 0..p {
        // for x^i
        let mut sum = 0;
        for j in 0..p {
            let a = a[j];
            let c = comb.get(p - 1, i);
            let j = mod_pow(j, p - 1 - i, p);
            sum += a * c * j;
            sum %= p;
        }
        if (p - 1 - i + 1) % 2 != 0 {
            sum = (p - sum) % p;
        }
        if i == 0 {
            for j in 0..p {
                sum += a[j];
            }
            sum %= p;
        }
        ans[i] = sum;
    }
    for i in 0..p {
        if i > 0 {
            print!(" ");
        }
        print!("{}", ans[i]);
    }
    println!();
}

fn mod_pow(mut cur: usize, mut e: usize, p: usize) -> usize {
    let mut result = 1;
    while e > 0 {
        if e & 1 == 1 {
            result = (result * cur) % p;
        }
        cur = (cur * cur) % p;
        e >>= 1;
    }
    result
}
pub struct Combination {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize,
}

impl Combination {
    pub fn new(max: usize, modulo: usize) -> Combination {
        let mut inv = vec![0; max + 1];
        let mut fact = vec![0; max + 1];
        let mut inv_fact = vec![0; max + 1];
        inv[1] = 1;
        for i in 2..(max + 1) {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..max {
            fact[i + 1] = fact[i] * (i + 1) % modulo;
        }
        for i in 0..max {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Combination {
            fact: fact,
            inv_fact: inv_fact,
            modulo: modulo,
        }
    }

    pub fn get(&self, x: usize, y: usize) -> usize {
        assert!(x >= y);
        self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
    }

    pub fn h(&self, n: usize, r: usize) -> usize {
        self.get(n + r - 1, r)
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
 
using namespace std;

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

//START OF CODE ->->->->->->->

void solve()
{
    int n;
    cin>>n;

    vector<int> a(n);

    rep(i,0,a.size())
    {
        cin>>a[i];
    }   

    vector<int> dp(n,0);
    // zero(dp);

    dp[n-1] = 0;

    repr(i,n-2,0)
    {
        if ( a[i] >= a[i+1] )
        {
            dp[i] = 1 + dp[i+1];
        }
        else
        {
            dp[i] = 0;
        }
    }

    // rep(i,0,n)
    // {
    //     out1(dp[i]);
    // }

    cout<<*max_element(all(dp))<<endl;
}

//END OF CODE ->->->->->->->->

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>
int main(void)
{
	char s[21];
	int i,n;
	scanf("%s",s);
	n=strlen(s);
	//printf("s=%s\n",s);
	for(i=n-1;i>=0;i--){
		printf("%c",s[i]);
	}
	printf("\n");
	return 0;
}



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

#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define ll  long long
#define ld	long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define endl "\n"

const ll MOD2 = 998244353;
const ll MOD = 1000*1000*1000 + 7;	
const ll N  = 1000*1000+5;
const double PI  = 3.14159265;

int main()
{
	int n;
	cin>>n;
	std::vector<pii> v;
	for (int i = 0; i < n; i++)
	{
		int a,b;
		cin>>a>>b;
		v.pb(mp(b,a));
	}
	sort(all(v));
	ll pref[n];
	pref[0]=v[0].ss;
	for (int i = 1; i < n; ++i)
	{
		pref[i]=pref[i-1]+v[i].ss;
	}
	int flag=0;
	for (int i = 0; i < n; ++i)
	{
		if(v[i].ff<pref[i])
			flag++;
	}
	if(flag)
		cout<<"No";
	else
		cout<<"Yes";
	return 0 ;
}

Measured memory_bytes: 6548
(function main() {
  const n = Number(require('fs').readFileSync('/dev/stdin', 'utf8')) + 1;
  const root5 = Math.sqrt(5);
  console.log(Math.round(1/root5 * (Math.pow((1 + root5) / 2, n) - Math.pow((1 - root5) / 2, n))));
})();



Measured memory_bytes: 15376
//
//  main.cpp
//  test
//
//  Created by イグノタスペベレル on 2020/04/18.
//  Copyright © 2020 イム. All rights reserved.
//

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

int main() {
    int N, A, B, i;
    int b_cnt = 0, passed = 0;
    cin >> N >> A >> B;
    int limit = A + B;
    vector<char> exnee(N);
    for (i = 0; i < N; i++) cin >> exnee.at(i);
    
    for (i = 0; i < N; i++) {
        if (passed < limit) {
            if (exnee.at(i) == 'a') {
                cout << "Yes" << endl;
                passed++;
            } else if (exnee.at(i) == 'b') {
                b_cnt++;
                if (b_cnt <= B) {
                    cout << "Yes" << endl;
                    passed++;
                } else cout << "No" << endl;
            } else cout << "No" << endl;
        } else cout << "No" << endl;
    }
}


Measured memory_bytes: 768
fun <T> permutation(sortedList: List<T>): List<List<T>> {
    val queue = mutableListOf<List<T>>()
    queue += arrayListOf<T>()
    val permutations = mutableListOf<List<T>>()
    while (queue.isNotEmpty()) {
        val p = queue.removeAt(0)

        if (p.size == sortedList.size) {
            permutations += p
            continue
        }

        for (item in (sortedList - p)) {
            queue += (p + item)
        }
    }

    return permutations
}

fun main(args: Array<String>) {
    val n = readInteger()
    val p = readIntegerList()
    val q = readIntegerList()

    val per = permutation((1..n).toList())
    Math.abs(per.indexOf(p) - per.indexOf(q)).let(::println)
}

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


Measured memory_bytes: 62032
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)

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

template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
	return left.second > right.second;
}

void init_global() {}

int main_() {
	string A, B;
	cin >> A >> B;
	
	int AL = A.size(), BL = B.size();
	if (AL > BL) {
		cout << "GREATER" << endl;
		return 0;
	} else if(AL < BL) {
		cout << "LESS" << endl;
		return 0;
	}

	FOR(i, 0, AL) {
		if (A[i] > B[i]) {
			cout << "GREATER" << endl;
			return 0;
		}
		else if (A[i] < B[i]) {
			cout << "LESS" << endl;
			return 0;
		}
	}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstdlib>
#include <queue>
using namespace std;


int main(){
	int N;
	cin>>N;
	int ans = 0;
	for(int i=0;i<262144;i++){
		int n = i;
		int a = 0;
		for(int j=0;j<9;j++){
			a*=10;
			switch(n%4){
				case 0:{
					a+=3;
					break;
				}
				case 1:{
					a+=5;
					break;
				}
				case 2:{
					a+=7;
					break;
				}
				case 3:{
					break;
				}
			}
			n/=4;
		}
		if(a>N)continue;
		int b = a;
		bool flag[3] = {};
		bool flag2 = false;
		bool flag3=false;
		bool flag4=false;
		while(true){
			if(a==0)break;
			flag2=true;
			if(a%10!=0&&flag3==true){
				flag4=true;
				break;
			}
			if(a%10==3)flag[0]=true;
			if(a%10==5)flag[1]=true;
			if(a%10==7)flag[2]=true;
			if(a%10==0){
				flag3=true;
			}
			a/=10;
		}
		if(!flag4&&flag[0]&&flag[1]&&flag[2]&&flag2){
			ans++;
		}
	}
	cout<<ans<<endl;	
	return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    rep(i,n) cin >> p[i];
    rep(i,n) cin >> q[i];
    vector<int> a(n);
    rep(i,n) a[i] = i+1;
    map<vector<int>, int> mp;
    do {
        mp[a] = mp.size();
    } while (next_permutation(a.begin(), a.end()));
    cout << abs(mp[p] - mp[q]) << endl;
    return 0;
}

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

using namespace std;
const int MAX_N = 2005; 
long long dp[MAX_N][MAX_N]; 
int n; 
int a[MAX_N]; 
pair <int, int> save[MAX_N]; 

bool comp(pair <int, int> a, pair <int, int> b) {
  return (a.first > b.first || (a.first == b.first && a.second < b.second)); 
}

int main () {
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout); 
  scanf("%d", &n); 
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);            
    save[i] = make_pair(a[i], i); 
  }
  sort(save + 1, save + n + 1, comp);   
  for (int l = 1; l <= n; l++) {
    dp[n][l] = 1LL * save[n].first * abs(save[n].second - l); 
  }
  for (int i = n - 1; i >= 1; i--) {
    for (int l = i; l >= 1; l--) {
      int r = l + n - i; 
      dp[i][l] = max(dp[i][l], dp[i + 1][l + 1] + 1LL * save[i].first * abs(save[i].second - l));
      dp[i][l] = max(dp[i][l], dp[i + 1][l] + 1LL * save[i].first * abs(save[i].second - r)); 
    }
  }
  long long res = -1;
  for (int l = 1; l <= n; l++) {
    if (res < dp[1][l]) {
      res = dp[1][l];
    } 
  }
  printf("%lld", res); 
  return 0;
}

Measured memory_bytes: 26364
using System;
using System.Linq;

namespace a
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine().Split();
            var a = s[0];
            var b = s[1];

            if(a.Equals("H")){
                if(b.Equals("H")){
                    Console.WriteLine("H");
                }else if(b.Equals("D")){
                    Console.WriteLine("D");
                }
            }else if(a.Equals("D")){
                if(b.Equals("H")){
                    Console.WriteLine("D");
                }else if(b.Equals("D")){
                    Console.WriteLine("H");
                }
            }
        }
    }
}


Measured memory_bytes: 11092
n, k, s = map(int,input().split())
if s == 10**9:
    ans = [1 for i in range(n)]
    for i in range(k):
        ans[i] = 10**9
else:
    ans = [10**9 for i in range(n)]
    for i in range(k):
        ans[i] = s

print(" ".join(map(str,ans)))


Measured memory_bytes: 12104
#include <iostream>
#include <cstdio>
#include <algorithm>

struct buc{
	int n, id;
	buc() : n(0){}
}b[2][100010];

int n, a[100010], ans;

bool cmp1(const buc &_, const buc &__){return _.n>__.n;}

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i]);
		b[i&1][a[i]].n++;	
	}
	for(int i=1; i<=100000; i++)	b[0][i].id=b[1][i].id=i;
	std::sort(b[0]+1, b[0]+100000+1, cmp1);
	std::sort(b[1]+1, b[1]+100000+1, cmp1);
	if(b[0][1].id==b[1][1].id)	ans=n-std::max(b[0][1].n+b[1][2].n, b[0][2].n+b[1][1].n);
	else ans=n-b[0][1].n-b[1][1].n;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 2176
/************************************/
/* NoobM							*/
/* File Name : abc.cpp				*/
/* Date : 25.07.2020 18:00:56 +06	*/
/************************************/

#include <bits/stdc++.h>

#define rr(i, b)    for (int i = 0; i < int(b); i++)
#define vi(n, a) vector <int> a(n); rr(i, n) cin >> a[i]
#define pvec(a) rr(i, a.size()) cout << a[i] << " "; cout << endl
#define bug(x) cout << #x << " " << x << endl
#define ll long long
#define vii vector <int>

using namespace std;

void solve() {
	int r, g, b;
	cin >> r >> g >> b;
	
	int k;
	cin >> k;
	
	while(r >= g && k) {
		k--;
		g *= 2;
	}
	while(g >= b && k) {
		k--;
		b *= 2;
	}
	
	
	if(g > r && b > g) cout << "Yes" << endl;
	else cout << "No" << endl;
	
}
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
	
	int t = 1;
	//cin >> t;
	
	while (t--) {
		solve();
	}
    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define int long long int

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout<<setprecision(30)<<fixed;
	
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	// for(int i=0;i<n;i++)
	// 	cout<<a[i]<<" ";
	// cout<<endl;
	int c=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if(a[i]!=a[j]&&a[i]!=a[k]&&a[j]!=a[k]&&a[i]+a[j]>a[k])
				{
					c++;
					//cout<<i<<" "<<j<<" "<<k<<endl;
				}
			}
		}
	}
	cout<<c<<endl;
	return 0;
}





Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

ll solve(ll a, ll b){
	if(a > b) swap(a, b);
	if(b % a == 0) return a * (2 * (b / a) - 1);
	return 2 * a * (b / a) + solve(b % a, a);
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	ll n, x; cin >> n >> x;
	cout << n + solve(x, n - x) << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    for (int i = 0; i < h; i++) {
        if(i < b){
            for (int j = 0; j < a; j++) {
                printf("0");
            }
            for (int j = a; j < w; j++) {
                printf("1");
            }
            printf("\n");
        }
        else{
            for (int j = 0; j < a; j++) {
                printf("1");
            }
            for (int j = a; j < w; j++) {
                printf("0");
            }
            printf("\n");
        }
    }
}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    for(int i=1; i <= n; i++){
        if(i % 3 == 0) continue;
        if(i % 5 == 0) continue;
        ans += i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
 
int N,R,T,p[101],A[1001],B[1001],ans;
int main(){
  cin>>N>>R>>T;
  for(int i=0;i<N;i++)cin>>p[i];
  for(int i=1;i<=T;i++){
    memset(A,0,sizeof(A));
    for(int j=0;j<N;j++)A[(p[j]*i)%R]++;
    for(int j=0;j<R;j++){
      if(i==1)ans+=A[j];
      else if(B[j]<A[j]){
        ans+=A[j]-B[j];
        B[j]=A[j];
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3100