| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 374584 |
2021-03-07T13:35:49 Z |
Karliver |
Raisins (IOI09_raisins) |
C++14 |
|
1314 ms |
26988 KB |
#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(3)<<(x)
#define all(v) (v).begin(), (v).end()
using namespace std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 51;
const double eps = 1e-3;
template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
x = (x > y ? y : x);
}
ll power(ll a, ll b){
if(!b)
return 1;
ll c=power(a,b/2);
c=(1LL*c*c);
if(b%2)
c=(1LL*c*a);
return c;
}
int mul(int a, int b) {
return a * 1ll * b % mod;
}
int add(int a, int b) {
int s = (a+b);
if (s>=mod) s-=mod;
return s;
}
struct RMQ {
vector<vector<int>>st;
RMQ(vector<int> &a) {
int n = a.size();
int k = ceil(log2(n));
st.clear();
st = vector<vector<int>>(n, vector<int>(k + 1, INF));
for(int i = 0;i < n;++i) {
st[i][0] = a[i];
}
for(int j = 1;j <= k;++j) {
for(int i = 0;i + (1 << j) <= n;++i) {
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int rng_q(int l, int r) {
//if(l > r)return -1;
int j = log2(r - l + 1);
int ans = min(st[l][j], st[r - (1 << j) + 1][j]);
return ans;
}
};
template<long long mod = 1000000007>
struct modint{
long long a;
modint() : a(0){}
modint(long long t){
a = t % mod;
if(a < 0) a += mod;
}
operator long long() const{ return a; }
bool operator==(const modint &x) const{ return a == x.a; }
bool operator!=(const modint &x) const{ return a != x.a; }
modint operator-() const{ return modint(a ? (mod - a) : 0); }
modint operator~() const{ return pow(mod - 2); }
modint operator+(const modint &x) const{ return modint(*this) += x; }
modint operator-(const modint &x) const{ return modint(*this) -= x; }
modint operator*(const modint &x) const{ return modint(*this) *= x; }
modint operator/(const modint &x) const{ return modint(*this) /= x; }
modint &operator+=(const modint &x){
a += x.a;
if(a >= mod) a -= mod;
return *this;
}
modint &operator-=(const modint &x){
a -= x.a;
if(a < 0) a += mod;
return *this;
}
modint &operator*=(const modint &x){
a = a * x.a % mod;
return *this;
}
modint &operator/=(const modint &x){
a = a * (~x).a % mod;
return *this;
}
friend ostream &operator<<(ostream &os,const modint &x){
return os << x.a;
}
friend istream &operator>>(istream &is,modint &x){
long long t;
is >> t;
x = modint(t);
return is;
}
modint pow(long long x) const{
modint ret = 1,tmp = a;
for(;x;tmp *= tmp,x >>= 1){
if(x & 1) ret *= tmp;
}
return ret;
}
};
const ll MOD = 1e9 + 7;
using Mint = modint<MOD>;
template<class T>
struct Combination{
vector<T> fact,factinv;
Combination(int n) : fact(n + 1),factinv(n + 1){
fact[0] = 1;
for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
factinv[n] = ~fact[n];
for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
}
T nCr(int n,int r){
if(n < 0 || r < 0 || n < r) return 0;
return fact[n] * factinv[r] * factinv[n - r];
}
T factorial(int x) {
if(x < 0)return 0;
return fact[x];
}
};
void done() {
// -1
// 1 -2
// -2
}
void solve()
{
// 4 5 2 3 1
// 1 -3 1 -2
// 4 6 3 1 5 2
// 2 -3 -2 4 -3
int n, m;
cin >> n >> m;
int dp[N][N][N][N];
forn(i, N) forn(j, N) forn(l, N) forn(K, N)dp[i][j][l][K] = -1;
int pr[N][N];
forn(i, N)forn(j, N)pr[i][j] = 0;
vector<vector<int>> a(n + 1, vector<int>(m + 1));
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
cin >> a[i][j];
pr[i][j] = pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1] + a[i][j];
}
}
function<int(int, int, int, int)> dfs = [&](int p1, int o1, int p2, int o2) {
if(p1 == p2 && o2 == o1)return 0;
if(dp[p1][o1][p2][o2] > -1)return dp[p1][o1][p2][o2];
int best = INF;
for(int i = p1;i < p2;++i) {
ckmi(best, dfs(i + 1, o1, p2, o2) + dfs(p1, o1, i, o2));
}
for(int j = o1;j < o2;++j) {
ckmi(best, dfs(p1, j + 1, p2, o2) + dfs(p1, o1, p2, j));
}
best += pr[p2][o2] - pr[p1 - 1][o1] - pr[p1][o1 - 1] + pr[p1 - 1][o1 -1];
dp[p1][o1][p2][o2] = best;
return best;
};
cout << dfs(1, 1, n, m) << '\n';
}
void emer() {
}
void another() {
// 10011
//
int n, q;
cin>> n >> q;
vector<int> c(n);
for(int i = 0;i < n;++i) {
cin >> c[i];
}
vector<vector<pair<int, pairs>>> qur(n);
for(int i = 0;i < q;++i) {
int l, r;
cin>> l >> r;
--l;
--r;
qur[r].push_back({l, {i, 1}});
if(l) {
qur[l - 1].push_back({l, {i, -1}});
}
}
vector<int> f(n);
auto inc = [&](int x) {
for(; x < n;x = (x | (x + 1))) f[x]++;
};
auto get = [&](int x) {
int ans =0;
for(; x >= 0;x = (x & (x + 1)) - 1)
ans += f[x];
return ans;
};
vector<int> ret(q);
map<int, int> last;
vector<int> pev(n, -1);
for(int i = 0;i < n;++i) {
if(last.count(c[i])) {
pev[i] = last[c[i]];
}
last[c[i]] = i;
inc(pev[i] + 1);
for(auto c : qur[i]) {
ret[c.second.first] += get(c.first) * c.second.second;
//cout << ret[c.second.first] << '\n';
}
}
forn(i, q) cout << ret[i] << '\n';
// 1 6 4 1 2 2 8
// (1, 3) (2, 5)
// 3 0 0 0 0 0 0
}
void test_case() {
int t;
cin >> t;
while(t--)solve();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
26860 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
26860 KB |
Output isn't correct |
| 3 |
Incorrect |
20 ms |
26860 KB |
Output isn't correct |
| 4 |
Incorrect |
19 ms |
26860 KB |
Output isn't correct |
| 5 |
Incorrect |
19 ms |
26860 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
26860 KB |
Output isn't correct |
| 7 |
Incorrect |
20 ms |
26860 KB |
Output isn't correct |
| 8 |
Incorrect |
34 ms |
26828 KB |
Output isn't correct |
| 9 |
Incorrect |
44 ms |
26860 KB |
Output isn't correct |
| 10 |
Incorrect |
57 ms |
26860 KB |
Output isn't correct |
| 11 |
Incorrect |
54 ms |
26880 KB |
Output isn't correct |
| 12 |
Incorrect |
142 ms |
26860 KB |
Output isn't correct |
| 13 |
Incorrect |
230 ms |
26988 KB |
Output isn't correct |
| 14 |
Incorrect |
74 ms |
26860 KB |
Output isn't correct |
| 15 |
Incorrect |
286 ms |
26860 KB |
Output isn't correct |
| 16 |
Incorrect |
39 ms |
26860 KB |
Output isn't correct |
| 17 |
Incorrect |
122 ms |
26888 KB |
Output isn't correct |
| 18 |
Incorrect |
707 ms |
26860 KB |
Output isn't correct |
| 19 |
Incorrect |
1125 ms |
26988 KB |
Output isn't correct |
| 20 |
Incorrect |
1314 ms |
26988 KB |
Output isn't correct |
